Algoritmo di ricerca del grafico

Question

Sto cercando un algoritmo grafico con alcune proprietà insolite.

Ogni bordo nel grafico è un bordo "su" o un bordo "giù".

Un percorso valido può fare un numero indefinito di "su" seguito da un numero indefinito di "giù" o viceversa.Tuttavia non può cambiare direzione più di una volta.

Ad esempio, un percorso valido potrebbe essere un "up" b "up" c "giù" e "giù" f Un percorso non valido potrebbe essere un "up" b "giù" c "up" d

Qual è un buon algoritmo per trovare il percorso valido più breve tra due nodi?Che ne dici di trovare tutti i percorsi più brevi di uguale lunghezza?

Answer 1

Supponendo che tu non abbia alcuna euristica, una variazione di Algoritmo di Dijkstra dovrebbe bastare abbastanza bene.Ogni volta che consideri un nuovo vantaggio, memorizza le informazioni sui suoi "antenati".Quindi, controlla l'invariante (un solo cambio di direzione) e torna indietro se viene violato.

Gli antenati qui sono tutti i bordi che sono stati attraversati per arrivare al nodo attuale, lungo il percorso più breve.Un buon modo per memorizzare le informazioni sugli antenati sarebbe come una coppia di numeri.Se U è su e D è giù, gli antenati di un particolare bordo potrebbero esserlo UUUDDDD, che sarebbe la coppia 3, 4.Non avrai bisogno di un terzo numero, a causa dell'invariante.

Poiché abbiamo utilizzato l'algoritmo di Dijkstra, la ricerca di più percorsi più brevi è già stata gestita.

Answer 2

Forse puoi trasformare il tuo grafico in un normale grafico diretto e quindi utilizzare gli algoritmi esistenti.

Un modo potrebbe essere quello di dividere il grafo in due grafi, uno con tutti gli archi verso l'alto e uno con tutti gli archi verso il basso e con gli archi diretti tra tutti i nodi del grafico uno e il nodo corrispondente sul grafico due.

Per prima cosa risolvi iniziando dal grafico uno e terminando con il grafico due e poi viceversa, quindi controlla la soluzione più breve.

Answer 3

Si potrebbe pensare al tuo standard BFS dovrebbe funzionare qui.Ogni volta che aggiungi un nodo all'elenco aperto, puoi racchiuderlo in una struttura che mantiene la direzione che sta utilizzando (su o giù) e un flag booleano che indica se ha già cambiato direzione.Questi possono essere utilizzati per determinare quali archi in uscita da quel nodo sono validi.

Per trovare tutti i percorsi più brevi di uguale lunghezza, includi il numero di archi attraversati finora nella tua struttura.Quando trovi il primo percorso più breve, prendi nota della lunghezza del percorso e smetti di aggiungere nodi all'elenco aperto.Continua a percorrere i restanti nodi dell'elenco finché non avrai controllato tutti i percorsi della lunghezza corrente, quindi fermati.

Answer 4

UN* con una funzione di costo (punteggio G) ed euristica (punteggio H) appositamente predisposta può gestirlo.

Per il costo potresti tenere traccia del numero di cambi di direzione nel percorso e aggiungere un costo infinito al secondo cambio (es.interrompere la ricerca di quei rami).

L'euristica richiede qualche riflessione in più, soprattutto quando si vuole mantenere l'euristica ammissibile (mai sopravvalutare la distanza minima dall'obiettivo) e monotona.(L'unico modo per garantire che A* trovi una soluzione ottimale.)

Forse sono disponibili più informazioni sul dominio per creare l'euristica?(cioè.coordinate x,y dei nodi nel grafico?)

Naturalmente, a seconda della dimensione del grafico che desideri risolvere, potresti prima provare algoritmi più semplici come la ricerca in ampiezza o l'algoritmo di Dijkstra:praticamente ogni algoritmo di ricerca andrà bene, e per ognuno avrai comunque bisogno di una funzione di costo (o simile).

Answer 5

Se disponi di una funzione di ricerca grafica standard, ad esempio Graph.shortest(from, to) in una libreria, puoi ripetere il ciclo e minimizzare, in C#/pseudocodice:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

Se hai bisogno di ricordare il percorso/percorsi minimi e capita che la tua funzione standard ti restituisca i dati, potresti anche pronunciare

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

Dove myMin dovrebbe confrontarne due [fst, nxt, C, AC, BD] tuple e lasciare quella che ha la distanza minore, o entrambe e assumendo reduce è una funzione intelligente.

Ciò comporta un sovraccarico di memoria se i nostri grafici sono grandi e non utilizzano affatto memoria (il che è possibile se vengono generati dinamicamente), ma non un reale sovraccarico di velocità, imho.