Download Problema

Problema 1. Considere un laberinto de tamaño 4x4. Cada posición del laberinto se
define por las coordenadas x (fila) y y (columna). Se desea llegar desde la posición
(3,2) a la posición (1,4).
Para realizar los movimientos se tienen las acciones arriba, abajo, izquierda y
derecha. Cada acción tiene costo 1.
2
1
3
4
F
1
2
3
4
I
Considere las siguientes heurísticas:
h1(n) = |5 – (x+y)|, donde (x,y) corresponde a las coordenadas del nodo n
h2(n) = |4 – (x*y)|, donde (x,y) corresponde a las coordenadas del nodo n
h3(n) = distancia de Manhattan de n a (1,4)
Indique cuáles heurísticas son admisibles
Aplique búsqueda avara utilizando h3. No evite devolverse
Aplique búsqueda A* utilizando la heurística h3. No evite devolverse
Problema 2. El cuadrado mágico.
Se tiene un tablero de 3x3. En cada posición se
debe colocar un número del 1 al 9, no se puede repetir ningún número. Además, la suma
de cada fila, columna y las diagonales debe ser 15. A continuación se muestra un
estado inicial:
7
1
2
8
5
3
6
9
4
Los números en las celdas coloreadas no se pueden mover. En cada avance del juego se
puede realizar la operación intercambiar(x,y) que permite intercambiar de posición los
números x y y. Cada avance tiene costo de una unidad.
6
1
8
7
5
3
2
9
4
Defina una heurística admisible
Aplique búsqueda avara
Aplique búsqueda A*
Problema 3. Sudoku.
Considere la siguiente configuración inicial. En cada avance
del juego se puede colocar/reescribir en una casilla no fija un número entre 1 y 9.
Defina una heurística
Aplique búsqueda avara
Aplique el algoritmo A*
Problema 4.
Considere el ambiente representado por la matriz de 5x6 que se
muestra a continuación:
1
Inicio
2
3
4
5
2
5
6
3
4
5
Fin
1
4
2
6
El problema consiste en llegar a la casilla etiquetada con la palabra Fin, posición (1,5),
empezando en la casilla con etiqueta Inicio, posición (2,1). Los únicos operadores
admitidos son arriba, abajo, izquierda y derecha. Aplicar cada operador cuesta 1.
En el ambiente el símbolo
representa un muro. El símbolo
representa un
hueco. Tenga en cuenta que nunca hay dos huecos seguidos y tampoco se pueden
ubicar en las filas o columnas que están en los bordes. Además, cuando se aplica un
operador en una casilla contigua a un hueco, el resultado de aplicar dicho operador es
desplazarse hasta la casilla que está al lado opuesto de donde se aplicó el operador,
por ejemplo, si en la casilla (4,1) se aplica el operador “derecha”, su nueva posición
será (4,3).
Defina una heurística que sea admisible.
Muestre el árbol generado al aplicar búsqueda Avara. Debe indicar el valor de h en
cada nodo.
Muestre el árbol generado al aplicar A*. Debe indicar el valor de f, g y h en cada
nodo.
Problema 5:
Imagine que se dispone de un agente que se debe mover en una
cuadrícula bidimensional compuesta de celdas cuadradas, las cuales pueden o no estar
llenas de piedras. El agente se puede mover arriba, abajo, izquierda o derecha. Una de
las celdas vacías contiene una caja la cual puede ser empujada por el agente al
ubicarse en la celda adyacente donde está la caja y realizar la acción “empujar”. Al
empujar la caja, el agente se desplaza a la celda donde estaba la caja.
La caja no se puede mover de ninguna otra manera, lo cual implica que si la caja se
mueve hacia una esquina, ésta no podrá ser retirada. Una de las celdas vacías se marca
con una X como la celda objetivo a la cual se desea llevar la caja.
Tenga en cuenta que el movimiento del agente cuando no está empujando la caja es de
1 unidad de energía y con la caja es de 2 unidades de energía.
Defina una heurística
Aplique búsqueda avara
Aplique el algoritmo A*