Come rappresentare i nodi di collegamento in Java?

Question

Come rappresentare i nodi di collegamento in Java?

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

0

Come implementare un finder di scorciatoie in un algoritmo di ricerca del percorso A *? Supponiamo che ogni tessera sia rappresentata da una coordinata (x, y) e so dove ogni tessera "buona" e ogni tessera "non percorribile" si trova sulla griglia. Come potrei trovare la soluzione migliore a questo problema su larga scala in cui i punti di partenza e di arrivo sono sempre diversi con molte scorciatoie e ostacoli diversi nel modo di ogni punto di partenza e di arrivo. Qual è il modo più ottimale per trovare il percorso più breve tra i punti della griglia a miglia di distanza (supponendo che ogni piastrella rappresenti 1 piede)?

java path-finding

posta Jeff smith 19.06.2018 - 07:42

fonte

2 risposte

Leggi altre domande sui tag java path-finding

UML Class Diagram con tipo di dati di riferimento Design della classe: decidi tra file e database per l'archiviazione durante il runtime [chiuso]

score 2 · Answer 1

A * non può generalmente essere usato con i collegamenti / nodi di salto. Questo perché A * usa un euristico, approssimativamente: "camminare nella direzione del bersaglio è il percorso ottimale, salvo eventuali ostacoli". O più formalmente: la disuguaglianza triangolare deve contenere. La disuguaglianza triangolare garantisce che prendere una deviazione porterà a un percorso più lungo. L'algoritmo A * si basa su un'euristica che non sottovaluta mai la distanza minima.

Tuttavia, i nodi di salto violano questa ipotesi. È possibile costruire uno scenario in cui il percorso più breve è quello di scappare dall'obiettivo per trovare un nodo di salto. Quindi l'euristica A * può essere fuorviante. Nel tuo esempio i nodi di salto funzionerebbero bene perché sono in linea con la direzione suggerita dall'euristica, ma in genere non è così.

Se si desidera utilizzare A * con nodi di salto, è necessario adattare l'algoritmo di individuazione del percorso non solo per cercare un percorso verso il bersaglio, ma anche per tutti i nodi di salto che sono più vicini del bersaglio (come euristico). Questo è complicato (perché devi aggiornare l'elenco dei possibili nodi di salto dopo un salto) ma efficiente. In alternativa, puoi utilizzare un algoritmo di individuazione dei percorsi diverso, ad es. Dijkstra (che è A * senza euristica, quindi una ricerca in ampiezza).

Rappresentare i nodi di salto non è difficile se si scrive l'algoritmo A * in termini di nodi piuttosto che in termini di coordinate della griglia. Dato un nodo, si avrà un'operazione neighbours(node) che fornisce i suoi vicini. Questi vicini sono in genere punti griglia vicini. Tuttavia, la funzione può prendere in considerazione i nodi di salto e restituire invece i vicini del target di salto.

score 0 · Answer 2

A * è applicabile più largo delle griglie quadrate.

Invece di definire i vicini di una tessera solo quelli che differiscono di uno nella direzione X o Y, includi eventuali scorciatoie ed escludi eventuali ostacoli.

Inizia da lo pseudocodice su Wikipedia

function neighbours(node)
    result := []
    for displacement in [(1,0), (-1,0), (0,1), (0,-1)]
        neighbour := node + displacement
        if passable(neighbour)
            result.Add(neighbour)
    for shortcut in shortcuts[node]
        result.Add(shortcut)
    return result

Quindi devi assicurarti che la tua euristica a distanza non sopravvaluti mai.

function prepare_heuristic(shortcuts, goal)
    result := Infinity
    for node in shortcuts.values
        result := min(result, displacement(node, goal))
    return result

function distance_heuristic(node, goal)
    return min(shortcut_distance, displacement(node, goal))

Questo è ancora un miglioramento rispetto a Dijkstra puro, specialmente quando le scorciatoie sono rare