Antes de poner el ejemplo, veamos que es busqueda irrevocable.
Bueno para empezar esta busqueda, entra dentro de las estrategias de busqueda, la cual son las siguientes:
* Busqueda irrevocable
* Busqueda por backtrack
* Busquedas ciegas
- Busqueda irrevocable
+ Caracteristicas :
1: Solo hay un estado activable y se le considera el estado actual del problema
2: Se determina el conjunto de reglas aplicables (las reglas aplicables son los estados o nodos)
3: Se escoje una regla
4: Se aplica la regla seleccionada y se genera el nuevo estado que se considera el estado áctual, el estado anterior se olvida (borramos)
+Criterio:
Esta estrategia se aplica en problemas donde sabemos que si aplicamos una regla equivocada no impedira la subsiguiente aplicación de una regla correcta, el único defecto negativo de las aplicaciones es alargar la busqueda. Recordar que una vez aplicada la regla no se puede volver atras.
Para este Ejemplo hemos seleccionado este tipo de busqueda.
Las reglas que manejamos son las siguientes:
a: Derecha
b: Abajo
c: Izquierda
d: Arriba
Seleccionamos regla y aplicamos.
La regla que vamos a utilizar es el que tenga el menor numero de errores posibles al de la meta.
Nombre: CUADROS2.C
Autor: maurici0
Lenguaje: Turbo C
Descargar:[CUADROS2.C] Buscalo en el link con ese nombre
Descripción: Resuelve un puzzle que se le de por medio de la busqueda irrevocable, utilizando el cero (0) como espacio, y con el compararemos los errores que tiene contra la meta, es bastante limitado su busqueda, ya que si en uno encuentra un error donde el menor es de 3, y en otro encuentra que el menor es 4 ya no tiene solución, ya que generaria un bucle.
Primero pedira los de inicio, un ejemplo básico:
Inicio: 2 8 3 1 6 4 7 0 5
Meta: 1 2 3 8 0 4 7 6 5
Despues de cada numero se pulsa enter para meter otro numero ^^.
La solucion esta en esta hoja:
(La linea que esta con negrita es la solución)
Y esos son los pasos que recorre el codigo para solucionarlo. Como les menciono es bastante limitado, ya que si le ponemos un puzzle complejo, no lo resolvera, ya que si se equivoca de camino, no tiene forma de regresar al nodo raiz (o el nodo anterior).
Anexado:
Informacion sacada de : [LINK]
- El problema del 8-puzzle
- : consiste en pasar de una confinguración inicial a una final deslizando cuadros aprovechando el espacio vacío.
El tratar de hacer búsqueda exhaustiva es impráctico cuando el número de posibles estados es muy grande, por lo que la decisión de qué hacer depende de una regla o juicio anterior a la búsqueda.Una posible regla es estimar qué tan cerca se está de la solución.
Algunas heurísticas que se han usado para ésto son:
- Contar el número de cuadros que no corresponden a la meta (sin contar el blanco). En el ejemplo: heu1(A)=2, heu1(B)=3, heu1(C)=4.
- La suma de la distancia Manhattan de los cuadros que no corresponden a su lugar. En el ejemplo: heu2(A)=2, heu2(B)=4, heu2(C)=4.
- Distancia del cuadro blanco al primer cuadro fuera de su lugar. En el ejemplo: heu3(A)=1, heu3(B)=1, heu3(C)=3.
- Distancia entre la posición final del blanco y su posición actual. En el ejemplo: heu4(A)=2, heu4(B)=0, heu4(C)=2.
