Miscelazione delle funzioni euristiche in A *

Question

Miscelazione delle funzioni euristiche in A *

#1 da (2 voti)

6

Ho applicato un'euristica personalizzata alla mia ricerca A *. È ammissibile, ma non è coerente (monotono). In quanto tale, non sono sicuro di trovare il percorso più breve.

Avevo pensato che avrei potuto usare un approccio ibrido che calcola sia la distanza euristica euclidea che la mia euristica personalizzata e sceglie il valore più stretto e coerente dei due (dove l'euclideo sarà sempre coerente).

Tuttavia, quando ho provato questo, ho trovato casi in cui anche la distanza euclidea non è coerente in presenza del nodo genitore. Cioè, dato il bordo uv , custom-heuristic(u) - euclidian-distance(v) > edge(uv) .

Per risolvere questo, ho tentato di rilevare questo & predefinito su un valore euristico di h(u) - e(uv) ma che ha provocato alcuni percorsi veramente terribili.

È possibile combinare efficacemente i metodi euristici e mantenere la coerenza? In quali circostanze funzionerà?

algorithms graph path-finding dijkstra

posta Synesso 19.08.2016 - 02:48

fonte

1 risposta

Leggi altre domande sui tag algorithms graph path-finding dijkstra

Best practice per le dipendenze locali di progettazione multi-modulo Come documentare gli URL e l'interazione tra le pagine

score 2 · Answer 1

Qualsiasi euristico ammissibile può essere reso coerente utilizzando quanto segue:

h*(p) = Max(h(p), h*(n)-c(np))
where
h is the admissible heuristic
h* is the new consistent heuristic
n is any node
p is any child of n
c is the cost of going from n to p
Note: h*(start) = h(start)

Usando questo il costo totale stimato rimane uguale nel caso h * (n) -c (np) o aumenta nel caso h (p) e quindi è non-decrescente che è quello che ti serve per coerenza.

Euristico coerente

Per combinare l'euristica devi solo aggiungerli al massimo.

h*(p) = Max(h(p), h*(n)-c(np), h'(p))

Ancora una volta h * (n) -c (np) mantiene la stima del costo totale decrescente, quindi finché tutte le tue euristiche sono ammissibili puoi aggiungere quante vuoi alla funzione Max.

Per essere chiari, però, il massimo non funzionerebbe necessariamente senza h * (n) -c (np). se si combina un'euristica incoerente con una costante perché se quella incoerente è costantemente maggiore di quella coerente allora il massimo non avrà alcun effetto. Un'euristica che dice sempre che 0 è coerente.