3. Un puzzle un poco diferente
El rompecabezas deslizante es una versión diferente del 15 puzzle, en la cual cada linea y cada columna se deslizan, como si se encontrara en una esfera (por supuesto que este tipo de rompecabezas no se puede hacer en madera, pero en la computadora es facilísimo). Un esquema del entorno es el siguiente:
| $\Uparrow$ | $\Uparrow$ | $\Uparrow$ | $\Uparrow$ | ||
|---|---|---|---|---|---|
| $\Leftarrow$ | 1 | 2 | 3 | 4 | $\Rightarrow$ |
| $\Leftarrow$ | 5 | 6 | 7 | 8 | $\Rightarrow$ |
| $\Leftarrow$ | 9 | 10 | 11 | 12 | $\Rightarrow$ |
| $\Leftarrow$ | 13 | 14 | 15 | 16 | $\Rightarrow$ |
| $\Downarrow$ | $\Downarrow$ | $\Downarrow$ | $\Downarrow$ |
Las acciones que el agente puede realizar sobre el ambiente son: a) Girar por la derecha el renglón $i$ ($i \in {1,2,3,4}$); b) Girar por la izquierda el renglón $i$ ($i \in {1,2,3,4}$); c) Girar por arriba la columna $j$ ($j \in {1,2,3,4}$); y d) Girar por abajo la columna $j$ ($j \in {1,2,3,4}$). Se asume que el ambiente es completamente observable. El objetivo del agente es que, después de aplicar un cierto numero de movimientos aleatorios y no observados. El agente pueda realizar las acciones necesarias para regresar el sistema al estado mostrado en el esquema anterior, utilizando la menor cantidad de movimientos posibles.
Conteste las siguientes preguntas (10 puntos por pregunta):
- Establezca una manera de representar el estado del problema.
- Establezca cuales serían las acciones legales en un estado dado.
- Establezca el estado sucesor a un estado dado, si se selecciona una acción.
- Establezca el costo local dependiendo del estado y la acción.
- ¿Cual es la cardinalidad del espacio de estado?
- ¿La distancia de Manhattan, o el número de piezas mal colocadas podrían ser heurísticas admisibles?
- Desarrolle 2 heurísticas ($h_1(n)$ y $h_2(n)$) para resolver el problema por el método de búsqueda A*.
- Demuestre (o haga un esbozo de demostración) que las heurísticas son admisibles.
- Determine si una heurística es dominante respecto a la otra. Demuestre que lo son (o que no lo son, en su caso).
- ¿La búsqueda en grafos ofrecería ventajas respecto a la búsqueda en árboles en este problema? Justifique su respuesta.