Algoritmi di Ricerca e Programmazione Logica: Euristiche, ASP e PDDL
Inviato da Anonimo e classificato in Altri soggetti
Scritto il in
italiano con una dimensione di 5,62 KB
Funzioni Euristiche
La formula generale per il calcolo del costo in un algoritmo di ricerca è: f(n) = g(n) + h(n), dove g(n) rappresenta il Costo Passato e h(n) l'Euristica.
Problemi di cammino su griglia o mappa
- 1. Distanza di Manhattan
- Quando usarla: Griglie con movimenti in 4 direzioni (su, giù, sinistra, destra).
- Formula: h(n) = |x₁ - x₂| + |y₁ - y₂|
- Esempio: Muoversi in una città a blocchi.
- 2. Distanza Euclidea
- Quando usarla: Movimento continuo nello spazio (senza restrizioni di direzione).
- Formula: h(n) = √{(x₁ - x₂)² + (y₁ - y₂)²}
- Esempio: Un drone che vola da un punto all’altro in linea retta.
- 3. Distanza di Chebyshev
- Quando usarla: Griglie in 8 direzioni (inclusi movimenti diagonali a costo uniforme).
- Formula: h(n) = max(