El algoritmo de búsqueda es uno de las mejores y más populares técnicas utilizadas en la búsqueda de caminos y los recorridos de gráficos
Enviado por Jillian • 18 de Noviembre de 2018 • 802 Palabras (4 Páginas) • 361 Visitas
...
2) Si no hay celdas bloqueadas / obstáculos entonces podemos encontrar el valor exacto de h sin ningún cálculo previo usando la fórmula de distancia / distancia euclidiana
B) Heurística de aproximación -
Generalmente hay tres heurísticas de aproximación para calcular h -[pic 1]
1) Distancia de Manhattan -
No es más que la suma de los valores absolutos de las diferencias en las coordenadas x e y de la meta y las coordenadas x e y de la celda actual respectivamente, es decir,
H = abs (celda_actual.x - objetivo.x) +
Abs (celda_actual.y - objetivo.y)
¿Cuándo usar esta heurística? - Cuando se nos permite moverse sólo en cuatro direcciones solamente (derecha, izquierda, arriba, abajo)
La Heurística de distancia de Manhattan se muestra en la figura inferior (asumir la mancha verde como célula fuente y la mancha roja como célula objetivo).
2) Distancia Diagonal
[pic 2]
No es más que el máximo de valores absolutos de diferencias en las coordenadas x y y de la meta y las coordenadas x y y de la celda actual, es decir,
H = max {abs (celda_actual.x - objetivo.x),
Abs (celda_actual.y - objetivo.y)}
¿Cuándo usar esta heurística? - Cuando se nos permite moverse en ocho direcciones solamente (similar a un movimiento de un Rey en Ajedrez)
La Heurística de Distancia Diagonal se muestra en la figura inferior (asumir la mancha verde como célula fuente y la mancha roja como célula objetivo).
3) Distancia euclidiana -
Como se desprende de su nombre, no es más que la distancia entre la celda actual y la celda de meta utilizando la fórmula de distancia
H = sqrt ((celda_actual.x - objetivo.x) 2 +
(celda_actual.y - objetivo.y) 2)
¿Cuándo usar esta heurística? - Cuando se nos permite moverse en cualquier dirección.
La heurística de distancia euclidiana se muestra en la siguiente figura (asumir la mancha verde como célula fuente y la mancha roja como célula objetivo).
[pic 3]
...