Problema di posizionamento dei pedaggi (teoria dei grafi)

Question

Problema di posizionamento dei pedaggi (teoria dei grafi)

#1 da (2 voti)

6

Sto lavorando su un problema che si riduce a qualcosa come il piazzamento di un casello su una serie di autostrade. Dato un grande grafo non orientato e un elenco di coppie di nodi con un valore di pedaggio tra di loro, ho bisogno di trovare l'insieme minimo di nodi di pedaggio che possono riscuotere i pedaggi (ogni nodo di piazza può prelevare un insieme arbitrario di pedaggi). Ogni nodo avrebbe un peso che definiva quanto è adatto essere un casello.

Questo sembra un algoritmo comune, ma non ho mai preso la teoria dei grafi e le mie ricerche non si sono rivelate molto. Qualsiasi suggerimento su come risolvere questo sarebbe apprezzato!

Graph:

[A]----[1]-----[2]----[3]------[C]
        |              |
        |              |
       [B]            [D]

Per esempio, in questo grafico, se ci sono pedaggi per (A, D) e (B, C), i nodi 1,2,3 saranno tutti ugualmente adatti per riscuotere i pedaggi, e potrei sceglierne uno dopo ordinandoli in base al peso. Se invece la lista del pedaggio era:

(A,D) = 5
(B,D) = 6
(B,C) = 7
(A,B) = 1

Quindi [1] è l'unico nodo singolo in grado di prelevare tutti i pedaggi. Dati elenchi come questi, voglio trovare il set di posizioni "ottimali" come questo.

graph graph-traversal

posta user3298142 12.12.2017 - 17:55

fonte

1 risposta

Leggi altre domande sui tag graph graph-traversal

GraphQL - Devo esporre le tabelle dei collegamenti? Come garantire un metodo che gestisca ogni evento in un sistema di eventi?

score 2 · Accepted Answer

Speriamo che un esperto di teoria dei grafi - che non sono - passerà a un certo momento per rispondere a questo. Nel frattempo, ecco alcuni pensieri che si spera possano aiutare.

Approccio ingenuo

Ovviamente, potresti provare a enumerare tutti i possibili percorsi tra tutte le coppie rilevanti di nodi, e quindi cercare di trovare una combinazione valida tramite un metodo comunemente usato (ricerca del grafico su possibili configurazioni / algoritmi di soddisfazione / algoritmi evolutivi).

Tuttavia, sia l'enumerazione che la valutazione di una configurazione sono probabilmente molto costose per i grafici non banali.

approccio semplice

L'approccio più semplice, e sicuramente molto efficiente (in termini di tempo di esecuzione) consiste nel posizionare le cabine di pedaggio vicino ai nodi di inizio / porta accanto o proprio sopra. Poiché devi solo posizionarli prima del o nodo dell'obiettivo iniziale, avrai al massimo 4 * N cabine, dove N è il numero di coppie di nodi. Il 4 viene dal tuo commento che nessun nodo ha più di 4 spigoli.

Puoi tener conto di

quante coppie di nodi un particolare nodo fa parte e
quanti nodi ha il nodo

per ridurre il numero di cabine totali. Da lì, potresti essere in grado di ottimizzare ulteriormente (ad esempio utilizzando alcune varianti BFS per verificare se tutti i percorsi finiscono per essere coperti già dai caselli di altri nodi - fino a una certa profondità).

Se questo è abbastanza buono per te, consiglierei sicuramente questo approccio. Ma se lo fosse, probabilmente non lo staresti chiedendo.

(A, B) Separatori

Considera solo il percorso da A a B nel grafico sottostante. Chiaramente, una buona soluzione sarebbe i nodi rossi oi nodi blu.

Questisonochiamatiseparatoriminimi(a,b)epossonoesseretrovatiintempopolinomiale.Unaricercamoltorapidaharivelato questo , anche se potrebbero esserci algoritmi migliori.

Una volta che hai tutti i separatori minimi (a, b) di tutte le coppie, è tempo di trovare una buona combinazione che copra tutti i percorsi. Questo dovrebbe essere molto più facile.

Nota che mentre dovresti essere in grado di farlo in tempo polinomiale, potrebbe comunque richiedere molto tempo, a seconda delle dimensioni del grafico e del numero di coppie.

Altri approcci

Non sono stato in grado di sfruttare il fatto che hai al massimo 4 spigoli per nodo, ma sembra il tipo di cosa che consentirebbe un approccio più efficiente.

Inoltre, dovresti esaminare qualsiasi ulteriore informazione strutturale che hai sul grafico. Ad esempio, se si riescono a eliminare sottografi densi che contengono al massimo un nodo rilevante (che fa parte di una coppia), si potrebbe finire con un grafico più semplice che consente di formulare ipotesi forti e, quindi, utilizzare altri approcci. Di nuovo, presumo che tu ne abbia parlato, ma potrebbe valerne un'altra.