[Tarea 2] Heurísticas no admisibles por el mapa

[cpamengual]

Tenemos que implementar 3 heurísticas: Manhattan, Euclides y una propia.

¿Qué pasa si al poner una celda de inicio y una celda final para poder hacer el recorrido una de estas heurísticas no es admisible? (Por ejemplo, para la Manhattan, no tengo como salir de la posición en la que estoy moviéndome para arriba/abajo/derecha/izquierda (sólo diagonal, o el nodo está inconexo)).

Por ahora estoy asumiendo que hay que poner un mensaje que diga "Para este recorrido escogido, la heurística XXX no funciona".

Asumo igual que es un error del mapa que nos dieron para trabajar, porque con el que nos corrijan debería ser posible utilizar las 3 heurísticas sin problemas.

Saludos!

[paxcema]

Hola!

Recuerda que una heurística será admisible para todo recorrido, o bien simplemente no es admisible.

Lo que asumes es válido, aunque deberás justificarlo correctamente en tu informe. Otra opción es que simplemente pongas el costo en distancia Manhattan de un movimiento diagonal.

Por último, lo que dices del mapa es verdad. De hecho, es recomendable que prueben con mapas propios a ver si obtienen resultados esperables!

Saludos.

[cpamengual]

@pcerdam Gracias por la info. Estuve investigando y la heurística de la Distancia de Manhattan que nos entregaron a nosotros en clases es sólo admisible para 4 movimientos (up/left/right/down), pero encontré en Stanford distintos documentos que hablan de una Distancia de Manhattan con admisibilidad para 8 movimientos (los 4 iniciales más los diagonales). [http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html](Stanford Heuristics - Game Programming)

No sé si se entiende bien lo que estoy tratando de preguntar (por eso adjunto una foto), pero mi duda es si nos quedamos básicamente con las 2 heurísticas "simples" presentadas en el Material de Clases (Euclides y Manhattan Simple) o debemos hacerles modificaciones para que sean admisibles a cualquier caso.

[paxcema]

Sí, se entiende.

Ojo que el enunciado no pide que las heurísticas sean todas admisibles para el problema. En caso de que una de ellas no lo sea, justifícalo y luego comenta el efecto de esto sobre el algoritmo de navegación en tu informe, y no habrá problemas.

Saludos.