Quale algoritmo posso utilizzare per trovare il percorso più breve tra i tipi di nodo specificati in un grafico?

Question

Questo è il problema:

Ho n punti (p1, p2, p3, .. pn), ognuno di essi può connettersi a qualsiasi altro con un costo determinato x.

Ogni punto appartiene a un gruppo di tipi di punti (ad esempio "A" "B" "C" "D" ...).

L'input del metodo è il percorso che voglio seguire, ad esempio "A-B-C-A-D-B".

L'uscita è il percorso più breve che collega i punti del tipo dò in ingresso così per esempio "p1-p4-P32-P83-P43-p12" dove p1 è un tipo A, p4 un tipo B, p32 un tipo C, p83 un tipo A, p43 un tipo D e p12 un tipo B.

La soluzione "facile" consiste nel calcolare TUTTI i possibili percorsi ma il costo computazionale è molto alto!

Qualcuno può trovare un algoritmo migliore?

Come ho detto nel titolo, non so se esiste!

Aggiornamento:

Il punto chiave che mi impedisce di usare Dijkstra e gli altri algoritmi simili è che non ho a collegare i punti in base al tipo.

Come input, ho una serie di tipi e devo collegarmi in questo ordine.

Questa è un'immagine di Kent Fredric (grazie mille) che descrive la situazione iniziale (nei collegamenti consentiti in rosso)!

alt text http://img13.imageshack.us/img13/3856/immagineaol.jpg

Un vero e proprio esempio di vita:

Un uomo vuole visitare una chiesa al mattino, andare al ristorante e, infine, visitare un museo nel pomeriggio.

Nella mappa ci sono 6 chiese, 30 ristoranti e 4 musei.

Vuole che il museo-chiesa-distanza sia il minimo possibile.

Answer 1

Ci sono molti algoritmi che faranno meglio del calcolo di tutti i possibili percorsi. Breadth-first search è il punto di partenza di base per la famiglia di algoritmi che ho in mente, Best-first search è appropriato perché hai definito i costi dei vertici, e se puoi ottenere maggiori informazioni sulla tua area di problemi, potresti essere in grado di usare A* o Dijkstra's algorithm. (In ogni caso, trovare i percorsi dall'insieme di nodi iniziali consentiti.)

Modifica: il vincolo del percorso (l'array di tipi di nodo che è necessario soddisfare) non impedisce di lavorare con questi algoritmi; al contrario, li aiuta tutti a lavorare meglio. Hai solo bisogno di implementarli in un modo che permetta di incorporare il vincolo del percorso, limitando i vertici disponibili in ogni fase della ricerca a quelli che sono validi dato il vincolo.

Answer 2

Per quanto riguarda la domanda, è necessario un percorso più breve in un grafico diretto. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm dovrebbe darti un'idea.

saluti, Jan

Answer 3

1. calcolate tutte le coppie di cammini minimi all'interno di ciascun blocco equivalenza.
2. Ora crea un grafico che non ha spigoli interclassici, ma i cui bordi tra le classi corrispondono al percorso più breve all'interno di quella classe, che porta al nodo specifico di un'altra classe.

Spero che questo sia chiaro.

Questa soluzione non è particolarmente efficiente, ma chiaramente polinomiale.

Answer 4

È possibile utilizzare l'algoritmo di Floyd-Warshall. Ecco il pseudocodice data da Wikipedia:

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
    (infinity if there is none). 
    Also assume that n is the number of vertices and edgeCost(i,i)=0 
*/ 

int path[][]; 

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 
    from i to j using intermediate vertices (1..k-1). Each path[i][j] is initialized to 
    edgeCost(i,j) or infinity if there is no edge between i and j. 
*/ 

procedure FloydWarshall() 
    for k: = 1 to n 
     for each (i,j) in {1,..,n}2 
      path[i][j] = min (path[i][j], path[i][k]+path[k][j]); 

ho dovuto scrivere un programma per un corso di algoritmi su questo stesso problema. Questo algoritmo ha funzionato come un incantesimo! In bocca al lupo.

Answer 5

Sulla revisione della tua domanda sembra che tu chieda un nodo per lettera - in questo caso è una semplice soluzione di programmazione dinamica: Calcola tutti i percorsi più brevi di lunghezza 1, che soddisfano l'inizio della sequenza, tra ogni coppia di nodi. Quindi avendo per k tutti questi percorsi per tutte le coppie di nodi, è banale costruire per k + 1.

Answer 6

Come detto in precedenza, è sufficiente un normale algoritmo di percorso più noioso (come l'algoritmo di Dijkstra o Floyd's); tuttavia, è necessario trasformare il grafico di input in modo che il percorso di uscita rispetti il ​​vincolo del percorso.

Dato un vincolo percorso di: A - B - A

Creare un nuovo grafico G e inserire tutti i vertici da A in G nuove etichette come a_01. Quindi inserire tutti i vertici da B in G e connettere i vertici A con i vertici B (i bordi devono essere indirizzati verso i nodi appena inseriti) copiando i costi dal grafico originale. Quindi ripetere questo passaggio con A (e qualsiasi altro componente del percorso) che collega i vertici appena inseriti a quelli in B. Pertanto, si crea un grafico in cui solo i percorsi esistenti soddisfano il vincolo del percorso. È quindi possibile utilizzare gli algoritmi di percorso minimo normale.

L'intuizione chiave è che quando si rivisita una classe si sta effettivamente visitando un insieme distinto di nodi e si desidera solo i bordi che collegano le classi di nodi adiacenti.

Answer 7

È così che ho attualmente interpreto il tuo problema.

Le frecce rosse consentono di tracciare manualmente i percorsi conformi al vincolo di ordinamento specificato.

I costi non vengono forniti, ma si presume che tutti i link sostengano un costo e che i costi di collegamento siano diversi.

Se questo descrive accuratamente lo scenario che si sta tentando di risolvere, si prega di dirlo, in modo che altri possano rispondere meglio alla domanda.

Answer 8

Ecco pseudocode con una soluzione di programmazione dinamica:

n - length of desired path 
m - number of vertices 
types[n] // desired type of ith node 
vertice_types[m] 
d[n][m] // our DP tab initially filled with infinities 

d[0][0..m] = 0 
for length from 1 to n 
    for b from 0 to m 
    if types[length] == vertice_types[b] 
     for a from 0 to m 
     if types[length-1] == vertice_types[a] 
      d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b)) 

vostro percorso minimo costo è min (d [n] [0..m])

è possibile ridurre la dimensione del tavolo d per 2 righe, ma sarebbe offuscare la soluzione