Pathfinding - A * con meno turni

Question

È possibile modificare A * per restituire il percorso più breve con il numero minimo di turni?

Una complicazione: i nodi non possono più essere distinti solo dalla loro posizione, perché il loro nodo genitore è rilevante nel determinare i turni futuri, quindi devono avere anche una direzione ad essi associata.

Ma il problema principale che sto avendo è come lavorare il numero di giri nel costo del percorso parziale (g). Se moltiplico g per il numero di turni presi (t), le cose strane stanno accadendo come: Un percorso più lungo con N spire vicino alla fine è favorito su un percorso più breve con N gira vicino all'inizio.

Un'altra soluzione meno ottimale che sto considerando è: dopo aver calcolato il percorso più breve, ho potuto eseguire una seconda iterazione A * (con una formula di costo percorso diversa), questa volta limitata all'interno dell'intervallo x/y del percorso più breve e restituire il percorso con il minor numero di giri. Altre idee?

Answer 1

Lo "stato" corrente della ricerca è in realtà rappresentato da due elementi: il nodo in cui ci si trova e la direzione verso cui si sta guardando. Quello che vuoi è separare ciascuno di questi stati in nodi diversi.

Quindi, per ciascun nodo nel grafico iniziale, dividerlo in nodi E separati, dove E è il numero di fronti in entrata. Ognuno di questi nuovi nodi rappresenta il vecchio nodo, ma rivolto in direzioni diverse. I bordi in uscita di questi nuovi nodi saranno tutti uguali ai vecchi bordi in uscita, ma con un peso diverso. Se il vecchio peso era w, quindi ...

• Se il bordo non rappresenta una svolta, rendono il nuovo peso w così
• Se il bordo non rappresentano una svolta, fanno il nuovo peso w + ε, dove ε è un numero significativamente più piccolo del peso più piccolo.

Quindi eseguire semplicemente una ricerca A * normale. Poiché nessuno dei pesi è diminuito, la tua euristica sarà ancora admissible, quindi puoi ancora usare la stessa euristica.

Answer 2

Se si desidera ridurre al minimo il numero di giri (anziché trovare un buon compromesso tra curve e lunghezza del percorso), perché non trasformare lo spazio del problema aggiungendo un bordo per ogni coppia di nodi connessi da una linea retta non ostruita ; queste sono le coppie che puoi percorrere senza un turno. Ci sono O (n) tali bordi per nodo, quindi il nuovo grafico è O (n) in termini di bordi. Ciò rende le soluzioni A * quanto O (n) in termini di tempo.

La distanza di Manhattan potrebbe essere una buona euristica per A *.