Puzzle

PD Tema 4: Resolución de problemas de espacios de estados

Programación lógica (2008–09)
Tema 4: Resolución de problemas de espacios de estados

José A. Alonso Jiménez
Grupo de Lógica Computacional Departamento de Ciencias de la Computación e I.A. Universidad de Sevilla

1 / 48

PD Tema 4: Resolución de problemas de espacios de estados

1. Ejemplo de problema de espacios de estados:El 8–puzzle 2. Procedimientos de búsqueda en espacios de estados

2 / 48

PD Tema 4: Resolución de problemas de espacios de estados Ejemplo de problema de espacios de estados: El 8–puzzle

Enunciado del problema del 8–puzzle
Para el 8–puzzle se usa un cajón cuadrado en el que hay situados 8 bloques cuadrados. El cuadrado restante está sin rellenar. Cada bloque tiene un número. Un bloqueadyacente al hueco puede deslizarse hacia él. El juego consiste en transformar la posición inicial en la posición final mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:

3 / 48

PD Tema 4: Resolución de problemas de espacios de estados Ejemplo de problema de espacios de estados: El 8–puzzle

Desarrollo del problema del 8–puzzle

4 /48

PD Tema 4: Resolución de problemas de espacios de estados Ejemplo de problema de espacios de estados: El 8–puzzle

Solución del problema del 8–puzzle

5 / 48

PD Tema 4: Resolución de problemas de espacios de estados Ejemplo de problema de espacios de estados: El 8–puzzle

Especificación del problema del 8–puzzle
Estado inicial: [[2,8,3],[1,6,4],[7,h,5]] Estado final:[[1,2,3],[8,h,4],[7,6,5]] Operadores:
Mover Mover Mover Mover el el el el hueco hueco hueco hueco a la izquierda arriba a la derecha abajo

Número de estados = 9! = 362.880.

6 / 48

PD Tema 4: Resolución de problemas de espacios de estados Procedimientos de búsqueda en espacios de estados Búsqueda en profundidad sin ciclos

Tema 4: Resolución de problemas de espacios de estados
1. Ejemplo de problemade espacios de estados: El 8–puzzle 2. Procedimientos de búsqueda en espacios de estados Búsqueda en profundidad sin ciclos
El problema del árbol Procedimiento de búsqueda en profundidad sin ciclos El problema de las 4 reinas

Búsqueda en profundidad con ciclos
Problema del grafo con ciclos El procedimiento de búsqueda en profundidad con ciclos El problema de las jarras

Búsqueda en anchuraEl problema del paseo El procedimiento de búsqueda en anchura

Búsqueda óptima
El problema del viaje El procedimiento de búsqueda óptima 2o procedimiento de búsqueda óptima

7 / 48

PD Tema 4: Resolución de problemas de espacios de estados Procedimientos de búsqueda en espacios de estados Búsqueda en profundidad sin ciclos

Enunciado del problema del árbol
Árbol a / \ b c / \ / \ d ef g / / \ \ h i j k Estado inicial: a Estados finales: f y j

8 / 48

PD Tema 4: Resolución de problemas de espacios de estados Procedimientos de búsqueda en espacios de estados Búsqueda en profundidad sin ciclos

Representación del problema del árbol
Representación arbol.pl estado_inicial(?E) se verifica si E es el estado inicial.

estado_inicial(a).
estado_final(?E) se verifica si E esun estado final.

estado_final(f). estado_final(j).
sucesor(+E1,?E2) se verifica si E2 es un sucesor del estado E1.

sucesor(a,b). sucesor(b,e). sucesor(d,h). sucesor(f,k).

sucesor(a,c). sucesor(c,f). sucesor(e,i).

sucesor(b,d). sucesor(c,g). sucesor(e,j).

9 / 48

PD Tema 4: Resolución de problemas de espacios de estados Procedimientos de búsqueda en espacios de estados Búsqueda enprofundidad sin ciclos

Solución del problema del árbol
profundidad_sin_ciclos(?S) se verifica si S es una solución del problema mediante búsqueda en profundidad sin ciclos. Por ejemplo, ?- [arbol]. ?- profundidad_sin_ciclos(S). S = [a, b, e, j] ?- trace(estado_final,+call), profundidad_sin_ciclos(S). T Call: (9) estado_final(a) T Call: (10) estado_final(b) T Call: (11) estado_final(d) T Call:...