[Algoritmo] Euristica per pathfinding

[Dan__88]

Ciao a tutti!
Mi serve una soluzione euristica per la ricerca di QUATTRO nodi su un grafo, ovvero un cammino che parta dalla posizione A e tocchi B, C,D e E.
Tale funzione viene chiamata dopo ogni passo, per scegliere il successivo.
Tra le più banali, ho provato ad esempio a calcolare le distanze tra la mia posizione e i 4 punti, ed a restituire la minima (o la massima)

Idee?

[webking]

Ciao,
non ho ben capito la tua richiesta: hai un grafo e devi restituire il percorso minimo o tutta una lista di possibili percorsi?

Una volta mi è capitato di dare una mano ad un mio amico per fare un gioco EX in C, e dovevo cercare un cammino "vincente" che toccasse una serie di caselle adiacenti occupate da pedine dello stesso giocatore.

La logica che c'è dietro è molto semplice: usa una funzione ricorsiva.

      O                Livello 0 (Radice)
    / | \ 
  O  O  O            Livello 1
 /|   |
O O  O               Livello 2
       | \
       O O            Livello 4

Tramite la ricorsione, le chiamate a procedura si impilano in uno stack gestito con politica LIFO (Last In first out). In quale linguaggio devi scrivere? c? Java?

[gugoXX]

Originariamente inviato da Dan__88

Ciao a tutti!
Mi serve una soluzione euristica per la ricerca di QUATTRO nodi su un grafo, ovvero un cammino che parta dalla posizione A e tocchi B, C,D e E.
Tale funzione viene chiamata dopo ogni passo, per scegliere il successivo.
Tra le più banali, ho provato ad esempio a calcolare le distanze tra la mia posizione e i 4 punti, ed a restituire la minima (o la massima)

Idee?

Scrivi un Dijkstra.
Poi calcoli il Dijkstra tra AB, BC, CD, DE -> es:200
poi calcoli il Dijkstra tra AB, BC, CE, ED -> Es:220

insomma calcoli il Dijkstra tra tutte le combinazioni senza ripetizione

ABCDE
ABCED
ABDCE
ABDEC
ACBDE
ACBED
ACE
...

AEDCB

(A e' sempre fisso mi pare di avere capito)
ed scegli quella che ti piace di piu'. Magari quella che ha il valore minore.

In questo modo "forse" non devi richiamare la funzione ad ogni passo. Precalcoli all'inizio e se non cambia nulla segui il tracciato fino alla fine.