Come trovare il percorso più breve con i nodi wormhole?

La maggior parte degli algoritmi di ricerca del percorso sono definiti in termini di grafici, non in termini di griglie. In un grafico, una connessione tra due nodi altrimenti distanti non è davvero un problema.

Tuttavia, devi stare attento con la tua euristica. Con i wormhole, la distanza minima tra due nodi non è più la distanza euclidea e la distanza non soddisfa la disuguaglianza triangolare. Tali euristiche sono inammissibili per A *. Pertanto non puoi usare A * facilmente.

Naturalmente gli algoritmi di individuazione dei percorsi come Dijkstra che non usano un'euristica funzioneranno ancora. Questo è più simile a una ricerca in ampiezza e selezionerà i tuoi wormhole senza ulteriore sforzo. Tuttavia, Dijkstra visiterà più nodi che A * con una buona euristica. (Dijkstra è equivalente a A * con heuristic(x) = 0 .)

Penso che A * funzioni se usi un'euristica che tratta tutti i wormhole uscenti come un wormhole direttamente sul bersaglio: l'euristica può sottovalutare la distanza, ma non deve mai sovrastimarla. Cioè l'euristico sarebbe:

def wormhole_heuristic(x):
  return min(euclidean_distance(x, g) for g in [goal, wormholes...])

Per un'euristica molto accurata, puoi (in modo ricorsivo) aggiungere la distanza dall'endpoint del wormhole all'obiettivo o al prossimo wormhole. Cioè come pre-calcolo è possibile eseguire la ricerca del percorso sul sottografo (totalmente connesso) contenente tutti i wormhole e l'obiettivo, in cui la distanza tra due nodi è la loro distanza euclidea. Questo può essere utile se il numero di wormhole è molto inferiore al numero di celle raggiungibili sulla tua griglia. La nuova euristica sarebbe:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  via_wormhole = min(euclidean_distance(x, w) + wormhole_path_distance(w, goal) for w in wormholes)
  return min(direct, via_wormhole)

Come sottolinea @Caleth nei commenti, tutto questo è molto sintonizzabile e possiamo migliorare la prima euristica del wormhole senza fare un percorso completo attraverso la rete wormhole, aggiungendo la distanza tra l'ultima uscita del wormhole e l'obiettivo. Poiché non sappiamo quale sarà l'ultima uscita del wormhole e non dobbiamo sopravvalutare, dobbiamo assumere l'uscita più vicina all'obiettivo:

def wormhole_heuristic(x):
  direct = euclidean_distance(x, goal)
  to_next_wormhole = min(euclidean_distance(x, w) for w in wormholes)
  from_last_wormhole = min(euclidean_distance(w.exit, goal) for w in wormholes)
  via_wormhole = to_next_wormhole + from_last_wormhole
  return min(direct, via_wormhole)

Hai un grafico con 6 vertici su una griglia con coordinate:

A ( 0,0)
B ( 4,7)
C ( 7,4)
D (10,4)
E (16,2)
F (16,0)

Puoi generare un grafico completo su quei vertici e assegnare un costo a ciascun bordo dove il costo è MAX( ABS( x1 - x2 ), ABS( y1 - y2 ) ) per i bordi standard e un costo di 0 per i wormhole.

Questo ti darà i costi (come matrice di adiacenza):

   A  B  C  D  E  F
- -- -- -- -- -- --
A  -  7  7 10 16 16
B  7  -  0  6 12 12
C  7  0  -  3  9  9
D 10  6  3  -  0  6
E 16 12  9  0  -  2
F 16 12  9  6  2  -

Se vi sono orditi unidirezionali, crea solo bordi nel grafico (o matrice di adiacenza) che vanno in quella direzione ma non nel contrario.

Puoi quindi utilizzare l'algoritmo Dijkstra con un coda di priorità .

Inizia da A e spinge ogni margine adiacente sulla coda di priorità:

Formato: (percorso: costo)

queue     = [ (A-B : 7), (A-C : 7), (A-D : 10), (A-E : 16), (A-F : 16) ]

Poiché gli articoli vengono inseriti in coda, tieni traccia del costo minimo per ogni vertice e spinga i percorsi sulla coda solo se è a costo inferiore rispetto al costo minimo esistente.

min-costs = { A: 0, B: 7, C: 7, D: 10, E: 16, F: 16 }

Rimuovere il primo elemento dalla coda e, se il costo corrisponde ancora al costo minimo, spingere tutti i percorsi compositi formati da quel percorso e i suoi bordi adiacenti di nuovo sulla coda di priorità (se i percorsi compositi hanno un costo inferiore a quello esistente minimo):

Rimuovi: (A-B : 7)

• Prova (A-B-A : 14) - rifiuta come costo più alto
• Prova (A-B-C : 7) - rifiuta allo stesso costo
• Prova (A-B-D : 13) - rifiuta come costo più alto
• Prova (A-B-E : 19) - rifiuta come costo più alto
• Prova (A-B-F : 19) - rifiuta come costo più alto

Rimuovi (A-C : 7)

• Prova (A-C-A : 14) - rifiuta come costo più alto
• Prova (A-C-B : 7) - rifiuta allo stesso costo
• Prova (A-C-D : 10) - rifiuta allo stesso costo
• Prova (A-C-E : 16) - rifiuta allo stesso costo
• Prova (A-C-F : 16) - rifiuta allo stesso costo

Rimuovi (A-D : 10)

• Prova (A-D-A : 20) - rifiuta come costo più alto
• Prova (A-D-B : 16) - rifiuta come costo più alto
• Prova (A-D-C : 13) - rifiuta come costo più alto
• Prova (A-D-E : 10) - inserisci nella coda
• Prova (A-D-F : 16) - rifiuta allo stesso costo

Ora la coda avrà il seguente aspetto:

queue     = [ (A-D-E : 10), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 16 }

Rimuovi (A-D-E : 10)

• Prova (A-D-E-A : 26) - rifiuta come costo più alto
• Prova (A-D-E-B : 22) - rifiuta come costo più alto
• Prova (A-D-E-C : 19) - rifiuta come costo più alto
• Prova (A-D-E-D : 10) - rifiuta allo stesso costo
• Prova (A-D-E-F : 12) - inserisci nella coda

Quindi la coda è:

queue     = [ (A-D-E-F : 12), (A-E : 16), (A-F : 16) ]
min-costs = { A: 0, B: 7, C: 7, D: 10, E: 10, F: 12 }

Rimuovi (A-D-E-F : 12) , scopri che hai raggiunto il nodo di destinazione con un costo di 12.

Nota: i percorsi (A-B-C-D-E-F) , (A-C-D-E-F) e (A-D-E-F) hanno tutti lo stesso costo minimo di 12.

Imposta una matrice contenente tutti i vertici e utilizza l'algoritmo Floyd-Wallenstein o l'algoritmo Bellman-Ford. Entrambi si tradurranno in una matrice con il percorso più breve possibile tra tutti i punti. È quindi possibile scorrere la matrice per trovare il percorso più breve che collega due punti. (il tuo problema è lo stesso di un TSP asimmetrico).