Alla ricerca di un algoritmo per connettere punti - percorso più breve

Question

Alla ricerca di un algoritmo per connettere punti - percorso più breve

#1 da (1 voti)
#2 da (1 voti)

1

Ho scritto un programma per risolvere un puzzle speciale, ma ora sono piuttosto bloccato al seguente problema: Ho circa 3200 punti / nodi / punti. Ciascuno di questi punti è collegato ad alcuni altri punti (di solito 2-5, il limite teorico è 1-26). Ho esattamente un punto di partenza e circa 30 punti di uscita (probabilmente tutti i punti di uscita sono collegati tra loro). Molti di questi 3200 punti non sono probabilmente collegati né ad inizio né a punto finale in alcun modo, come una rete separata, ma tutti i punti sono collegati ad almeno un altro punto.

Ho bisogno di trovare il numero più breve di hop per passare da entrata a uscita. Non c'è distanza tra i punti (a differenza del problema di routing su strada o treno), conta solo il numero di hop. Ho bisogno di trovare tutte le soluzioni con il minor numero di hop, e non solo una soluzione, ma tutte. E potenzialmente anche soluzioni con un altro hop ecc. Mi aspetto di avere una soluzione con circa 30-50 luppoli per andare dall'inizio alla fine.

Ho già provato:

1) provare casualmente le possibilità e ricominciare da capo quando il conteggio era più grande di una soluzione precedente. Ho ottenuto la prima soluzione con 3500 luppolo, dopo alcuni minuti è sceso a circa 97, ma guardando le soluzioni ho visto problemi come loop e cose inutili, quindi ho cercato di ottimizzare un po '(come non tornare da dove è venuto da ecc. .). Sono possibili ulteriori ottimizzazioni, ma questa cosa casuale non trova tutte le soluzioni migliori o richiede troppo tempo.

2) Passa in modo ricorsivo dall'inizio alla fine (come in una sorta di scacchi) e rompendo la prova quando ha raggiunto un punto precedente. Si trattava di un loop di circa 120 nodi, quindi cerca catene che sono (probabilmente) di gran lunga troppo lunghe. Se calcoliamo 4 possibilità e 120 nodi, stiamo raggiungendo 1,7E72 possibilità, che non è possibile calcolare attraverso. Questo è chiamato Depth-first search (DFS) come ho scoperto nel frattempo. Forse dovrei provare la ricerca di Breadth-first aggiungendo qualche coda?

Le connessioni tra i punti sono in realtà mosse che puoi effettuare nel gioco e i punti sono come apparirà il gioco dopo aver effettuato la mossa.

Quale sarebbe l'algoritmo da utilizzare per questo problema? Sto usando C # .NET, ma la lingua non dovrebbe avere importanza.

algorithms graph-traversal

posta e4ch 23.08.2014 - 16:04

fonte

2 risposte

Leggi altre domande sui tag algorithms graph-traversal

Notazione / Meta lingua per esprimere un algoritmo Gestione delle eccezioni nell'applicazione WIn Forms

score 1 · Answer 1

generalmente questo è chiamato ricerca del percorso

Sembravi aver provato 2 prime ricerche di profondità.

Suggerisco di utilizzare una ricerca per ampiezza (mantenere tutti i percorsi di lunghezza n e quindi utilizzare quelli per trovare tutti i percorsi di lunghezza n + 1).

Se questo supera la tua memoria, puoi utilizzare un approccio di approfondimento iterativo. Questa è una prima profondità che ti interrompi di lunghezza n e se non trovi una soluzione prova di nuovo con n' = n+k e ripeti

score 1 · Answer 2

Raccomando una ricerca approfondita come hai già provato, ma aggiungo alcuni vincoli aggiuntivi. Ad esempio, un percorso che esegue il ciclo (rivisita i nodi) è chiaramente indesiderabile quando si cerca il percorso più breve: basta rimuovere i loop e si trova un percorso più breve di N dove N è il numero di nodi nel loop.

Con qualsiasi algoritmo ha senso impostare le precondizioni, incluso il problema da risolvere: i passi dell'algoritmo: e la condizione di uscita (successo o fallimento).

Il problema

Considera un grafico costituito da un numero arbitrario di nodi. Un nodo è il nodo iniziale e ci sono più nodi di uscita . L'obiettivo è trovare tutti i percorsi della stessa lunghezza che attraversano il nodo di partenza in uno dei nodi di uscita e che sono la lunghezza più breve.

Ogni attraversamento del grafico manterrà necessariamente un elenco di tutti i nodi attraversati dall'inizio al nodo corrente. Questo definisce il percorso .

Ci sarà spazio di archiviazione per contenere i percorsi completati che contiene zero o più percorsi che rappresentano attraversamenti dal nodo iniziale a un nodo di uscita.

Algoritmo

Il nodo corrente è il nodo iniziale.
Scegli un bordo non ancora attraversato: non fa parte del percorso corrente; non è stato attraversato e retrocesso; che non si collega al nodo corrente (non loop).
1. Se non ci sono bordi da attraversare e il nodo corrente è il nodo di partenza, l'algoritmo termina.
2. Se non ci sono spigoli da attraversare e il nodo corrente è non il nodo di partenza, backtrack un nodo e ripeti questo passaggio.
Attraversa il bordo del nodo successivo e aggiungilo al percorso.
Se il nodo corrente è un nodo di uscita: copia il percorso dei percorsi completati e torna al nodo precedente.
Vai al passaggio 2.

Note

Questo è un algoritmo di base in profondità che sarà implacabile nel trovare tutti dei percorsi. Questo è necessario per trovare il più breve: l'ultimo percorso percorso potrebbe essere il più breve, non lo sappiamo.

Questo algoritmo:

Troverà tutti i percorsi.
Non attraverserà lo stesso bordo due volte in un solo percorso. Cioè, non loop.
Non interessa nodi o sistemi di nodi che non sono raggiungibili dal nodo iniziale. Tali nodi occuperanno memoria, ma non avranno importanza per il tempo di esecuzione dell'algoritmo.
Potrebbe essere migliorato. In particolare, potrebbe essere possibile eseguire un algoritmo diverso per potare nodi e spigoli in anticipo che potrebbero aiutare a ridurre il numero di nodi nel grafico. Forse c'è una catena di nodi lunga mille che finisce in un nodo di non uscita, per esempio. A volte il tempo e lo sforzo per farlo aiuta, a volte no.