Una heurística admisible es aquella que nunca sobreestima el costo para alcanzar la meta.
Hay muchas formas de generar heurísticas para un problema dado. Relajar el problema es una de las formas más utilizadas.
Relajar el problema simplemente significa eliminar algunas restricciones que se imponen al problema. El problema del mosaico deslizante, como cualquier otro problema, tiene reglas que nos permitirán mover un mosaico solo horizontal o verticalmente. Además, solo podemos mover el mosaico a un espacio en blanco. ¿Qué pasa si dejamos caer tales restricciones?
- ¿Cuál es la diferencia entre las funciones recursivas estáticas y las funciones recursivas no estáticas C / C ++?
- Cómo mejorar mis estructuras de datos y algoritmo desde el nivel básico
- ¿Cuál es la diferencia entre un algoritmo genético y el recocido simulado?
- ¿Es posible proporcionar un análisis de complejidad para todos los algoritmos en términos de theta?
- ¿Cuál es el algoritmo de tiempo polinómico de peor caso de más rápido crecimiento utilizado en la práctica?
Obtenemos lo que llamamos el problema relajado .
Es intuitivo razonar que la solución al problema relajado tiene un costo que es al menos tan bueno como el costo de la solución al problema original. Debido a esta razón, la solución al problema relajado es siempre una heurística admisible al problema original.
Ahora, establezcamos (de alguna manera) formalmente la regla del problema del mosaico deslizante.
Un mosaico puede moverse de A a B si A está horizontal o verticalmente adyacente a B y B está en blanco.
Podemos derivar un problema relajado al soltar la restricción que requiere que el mosaico sea adyacente al cuadrado en blanco. Esto da como resultado lo siguiente.
Un mosaico puede moverse del cuadrado A al cuadrado B si B está en blanco.
Ahora, el costo de la solución del problema relajado derivado puede usarse como una heurística para el problema original.
Podemos tener otro problema relajado al dejar caer otra restricción.
Un azulejo puede moverse del cuadrado A al cuadrado B.
Sin embargo, hay una cosa importante para recordar. El problema relajado debe tener una forma simple de encontrar la solución; no deberían convertirse en un problema de búsqueda propio. No queremos que la heurística sea computacionalmente costosa de obtener.
