Introducción
La búsqueda en el espacio de estados es un proceso ocupado en Inteligencia Artificial en el cual se consideran sucesivos estados de una instancia para encontrar un estado final con las características que se elijan.
Es necesario definir un problema el cual será modelado por un conjunto de estados que lo contengan, cada estado estará conectado si existe una operación que transforme el primer estado en el segundo.
Una representación de estados es un modelo matemático de un sistema (problema) descrito mediante un conjunto de entradas, salidas y variables de estado relacionadas.
El siguiente informe busca definir los conceptos básicos referentes a la búsqueda en el espacio de estados, para esto se mostrará el comportamiento de estos mediante la solución al problema del 8 puzzle.
Parte I - Representación de problemas en el espacio de estados.
La representación de problemas en Inteligencia Artificial consiste en buscar un estado concreto (el mejor) entre un conjunto de estados llamada espacio de estados.
Para diseñar esta representación es necesario seguir los siguientes pasos:
Crear una descripción formal y manejable del propio problema.
- Espacio de estados
- Estado inicial
- Estado final
- Reglas para pasar de un estado a otro.
Estos pasos permiten definir formalmente el problema, convirtiendo una situación dada en una situación deseada, al mismo tiempo permite definir el proceso de resolución de un problema con una combinación de técnicas conocidas (encontrar una ruta desde el estado inicial, hasta el estado esperado).
A continuación se muestra el modelo típico de espacios de estados:
Parte I Representación de 8 puzzle en el espacio de estados
Espacio de estados: cantidad de de puzles que se pueden generar en un juego.
Estado inicial: Un puzle de 9 casillas en el cual ocho están llenas de algún elemento y la novena casilla se encuentra vacía, sin importar el orden de los elementos.
Estado final: Un puzle con los elementos ordenados de menor a mayor y la última casilla vacía.
Reglas: Los movimientos de cada elemento serán de manera horizontal o vertical, dependiendo de la ubicación de la casilla vacía y estarán limitados por los bordes del puzle.
Operadores de cambio de estado:
- Arriba.
- Abajo.
- Derecha.
- Izquierda
.
A continuación se muestra un ejemplo básico de representación de 8 puzle en el espacio de estados.
Parte II - Implementación de los Algoritmos de búsqueda en el espacio de estados.
Búsqueda en profundidad
Es un algoritmo que permite recorrer todos los nodos de un árbol de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo cada uno de los nodos localizados, de forma recurrente en un camino concreto, cuando ya no quedan nodos en dicho camino, regresa, de esta forma repite el proceso para cada uno de los hermanos del nodo ya procesado.
A continuación Pseudocódigo para el algoritmo en profundidad:
DFS(grafo G)
PARA CADA vertice u ∈ V[G] HACER
estado[u] ← NO_VISITADO
padre[u] ← NULO
tiempo ← 0
PARA CADA vertice u ∈ V[G] HACER
SI estado[u] = NO_VISITADO ENTONCES
DFS_Visitar(u)
DFS_Visitar(nodo u)
estado[u] ← VISITADO
tiempo ← tiempo + 1
d[u] ← tiempo
PARA CADA v ∈ Vecinos[u] HACER
SI estado[v] = NO_VISITADO ENTONCES
padre[v] ← u
DFS_Visitar(v)
estado[u] ← TERMINADO
tiempo ← tiempo + 1
f[u] ← tiempo
Búsqueda en profundidad
Es un algoritmo que permite recorrer o buscar elementos en un árbol intuitivamente, expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución, este algoritmo no ocupa ninguna estrategia heurística.
BFS(grafo G, nodo_fuente s)
{
// recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
// distancia INFINITA y padre de cada nodo NULL
for u ∈ V[G] do
{
estado[u] = NO_VISITADO;
distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
padre[u] = NULL;
}
estado[s] = VISITADO;
distancia[s] = 0;
Encolar(Q, s);
while !vacia(Q) do
{
// extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
u = extraer(Q);
for v ∈ adyacencia[u] do
{
if estado[v] == NO_VISITADO then
{
estado[v] = VISITADO;
distancia[v] = distancia[u] + 1;
padre[v] = u;
Encolar(Q, v);
}
}
}
}
A continuación el código fuente de nuestro programa:
/*
*
*
*/
package project01;
/**
*
* @author Grupo: Jonathan Campos, Carlos Elmes, Esteban Gonzalez, Carlos Melo
*/
class Calculos
{
private int[] counter; // Arreglo para recorrer cada contador de profundidad
private int[] timer; //Tiempo
private int[] cost; //Costo
private int max; // Maxima profundidad
private int min = 0; // Minima profundidad
private int num = 10; // # para conseguir cada solución
private int size = 75; // Tamaño base para randomizar
//---------------------------------------------------------------------------------
public Calculos(int max)
{
this.max = max;
counter = new int[max];
timer = new int[max];
cost = new int[max];
}
//---------------------------------------------------------------------------------
public Calculos(int min, int max)
{
this.max = max;
this.min = min;
counter = new int[max];
timer = new int[max];
cost = new int[max];
}
//---------------------------------------------------------------------------------
// Corre suficientes puzles para cumplir con los requisitos
public void run()
{
int i;
do
{
Resuelve p = new Resuelve(size);
Tiempo t = new Tiempo();
t.start();
p.solve();
long time = t.end();
Puzle solution = p.getPuzzleSolution();
if (solution.getDepth() <= max && (solution.getDepth()-min) > 0)
{
if (counter[(solution.getDepth()-1)-min] < num)
{
counter[(solution.getDepth()-1)-min]++;
timer[(solution.getDepth()-1)-min] += time;
cost[(solution.getDepth()-1)-min] += p.getCost();
}
}
} while (!checkCounter());
System.out.println("Profundidad\tCosto\tTiempo de Ejecucion");
for (i=0; i<(max-min); i++)
System.out.println((i+1)+min+"\t"+(cost[i]/num)+"\t"+timer[i]/num);
}
//---------------------------------------------------------------------------------
//Retorna verdadero si la data esta completa
public boolean checkCounter()
{
int count = 0;
for (int i=0; i<(max-min); i++)
{
count += counter[i];
}
return (count == ((max-min)*num));
}
} // Fin Clase Calculos
/*
*
*
*/
package project01;
/**
*
* @author jonathan
*/
class Ejecutar
{
//---------------------------------------------------------------------------------
public static void main(String[] args)
{
Resuelve puzzle = new Resuelve(100);// inicia clase y establece numero maximo de jugadas (profundidad)
puzzle.solve();
puzzle.print();
}
//---------------------------------------------------------------------------------
} // fin clase Ejecutar
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package project01;
/**
*
* @author jonathan
*/
import java.util.Vector;
import java.util.Arrays;
import java.util.Random;
import java.lang.Math;
import java.util.Date;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////
class Puzle
{
private int[] pieces = new int[9];
private boolean manhattan = true; //Type of heuristic function
private int depth; //Number of moves made so far
private int parentID=-1; //Parent ID for node tracking
//---------------------------------------------------------------------------------
public Puzle(int move) {generate(move);}
//---------------------------------------------------------------------------------
public Puzle(int[] squares, boolean isManhattan)
{
for (int i=0; i<9; i++)
{
pieces[i] = squares[i];
setHeuristic(isManhattan);
}
}
//---------------------------------------------------------------------------------
public Puzle(int[] squares, boolean isManhattan, int depth)
{
this.depth = depth;
for (int i=0; i<9; i++)
{
pieces[i] = squares[i];
setHeuristic(isManhattan);
}
}
//---------------------------------------------------------------------------------
public Puzle(int[] squares, boolean isManhattan, int depth, int parentID)
{
this.depth = depth;
this.parentID = parentID;
for (int i=0; i<9; i++)
{
pieces[i] = squares[i];
setHeuristic(isManhattan);
}
}
//---------------------------------------------------------------------------------
public Puzle(Puzle puzzle)
{
pieces = puzzle.copyArray();
manhattan = puzzle.isManhattan();
depth = puzzle.getDepth();
parentID = puzzle.getParentID();
}
//---------------------------------------------------------------------------------
// Generates a fresh set of squares by moving the blank x number of times
public void generate(int move)
{
// create a correct puzzle
for (int i=0; i<9; i++)
pieces[i] = i;
// randomly move the puzzle (25 times for this project)
for (int j=0; j<move; j++)
{
// pick a random action
Random rand = new Random();
int choice = rand.nextInt(4)+1;
switch (choice)
{
case 1:
pieces = up(pieces);
break;
case 2:
pieces = down(pieces);
break;
case 3:
pieces = left(pieces);
break;
case 4:
pieces = right(pieces);
break;
}
}
}
//---------------------------------------------------------------------------------
private int[] up(int[] puzzleArray)
{
int i;
int[] temp = new int[puzzleArray.length];
int holder;
for (i=0; i<puzzleArray.length; i++)
temp[i] = puzzleArray[i];
int square= 0;
for (i=0; i<temp.length; i++)
{
if (temp[i] == 0)
square = i;
}
// invalid option check
if (square < 3)
return temp;
holder = temp[square];
temp[square] = temp[square-3];
temp[square-3] = holder;
return temp;
}
//---------------------------------------------------------------------------------
private int[] down(int[] puzzleArray)
{
int holder;
int[] temp = new int[puzzleArray.length];
for (int i=0; i<puzzleArray.length; i++)
temp[i] = puzzleArray[i];
int square= 0;
for (int i=0; i<temp.length; i++)
{
if (temp[i] ==0 )
square = i;
}
// invalid option check
if (square > 5)
return temp;
holder = temp[square];
temp[square] = temp[square+3];
temp[square+3] = holder;
return temp;
}
//---------------------------------------------------------------------------------
private int[] left(int[] puzzleArray)
{
int holder;
int[] temp = new int[puzzleArray.length];
for (int i=0; i<puzzleArray.length; i++)
temp[i] = puzzleArray[i];
int square= 0;
for (int i=0; i<temp.length; i++)
{
if (temp[i] ==0 )
square = i;
}
// invalid option check
if (square%3 == 0)
return temp;
holder = temp[square];
temp[square] = temp[square-1];
temp[square-1] = holder;
return temp;
}
//---------------------------------------------------------------------------------
private int[] right(int[] puzzleArray)
{
int holder;
int[] temp = new int[puzzleArray.length];
for (int i=0; i<puzzleArray.length; i++)
temp[i] = puzzleArray[i];
int square= 0;
for (int i=0; i<temp.length; i++)
{
if (temp[i] ==0 )
square = i;
}
// invalid option check
if (square%3 == 2)
return temp;
holder = temp[square];
temp[square] = temp[square+1];
temp[square+1] = holder;
return temp;
}
//---------------------------------------------------------------------------------
public String toString()
{
String out = new String(" +---+---+---+\n");
for (int i=1; i<=9; i++) {
if ((i%3) == 1)
out += " | ";
if (pieces[i-1] == 0)
out += " | ";
else
out += pieces[i-1]+" | ";
if ((i%3) == 0)
out += "\n +---+---+---+\n";
}
return out;
}
//---------------------------------------------------------------------------------
public boolean equals(Puzle p)
{
return (p.toString().equals(toString()));
}
//---------------------------------------------------------------------------------
public boolean isManhattan() {return manhattan;}
//---------------------------------------------------------------------------------
public int getDepth() {return depth;}
//---------------------------------------------------------------------------------
public int getParentID() {return parentID;}
//---------------------------------------------------------------------------------
public void setDepth(int depth) {this.depth = depth;}
//---------------------------------------------------------------------------------
// Set Heuristic type
public void setHeuristic(boolean isManhattan)
{
manhattan = isManhattan;
}
//---------------------------------------------------------------------------------
// Get Heuristic based on type
public int getH()
{
if (manhattan)
return getmanhattanH();
else
return getOtherH();
}
//---------------------------------------------------------------------------------
// Set Non-manhattan Heuristic
private int getOtherH()
{
// count the number of squares in the wrong place
int wrong = 0;
for (int i=0; i<9; i++)
if (pieces[i] != i)
wrong++;
return wrong;
}
//---------------------------------------------------------------------------------
// Set manhattan Heuristic
private int getmanhattanH()
{
int h = 0;
int xs, xg, ys, yg;
for (int i=0; i<9; i++)
{
// breaks the game locations into a grid formation
// measures the distance using grid length.
xg = i%3;
yg = i/3;
xs = pieces[i]%3;
ys = pieces[i]/3;
h += Math.abs(xs-xg) + Math.abs(ys-yg);
}
return h;
}
//---------------------------------------------------------------------------------
// Add to the cost
public void addMove() { depth++;}
//---------------------------------------------------------------------------------
public int[] copyArray()
{
int[] temp = new int[9];
for (int i=0; i<9; i++)
temp[i] = pieces[i];
return temp;
}
//---------------------------------------------------------------------------------
public int[] up() { return up(pieces);}
//---------------------------------------------------------------------------------
public int[] down() { return down(pieces);}
//---------------------------------------------------------------------------------
public int[] left() { return left(pieces);}
//---------------------------------------------------------------------------------
public int[] right() {return right(pieces);}
//---------------------------------------------------------------------------------
} // end class Pazzle
/*
*
*
*/
package project01;
import java.util.Vector;
class Resuelve
{
private int cost = 0;
private Vector usedList;
private Vector fringeList;
private Puzle p;
//---------------------------------------------------------------------------------
public Resuelve(int depth)
{
usedList = new Vector();//guarda jugadas utilizadas
fringeList = new Vector();//contador de jugadas
p = new Puzle(depth);
fringeList.add(p);
}
//---------------------------------------------------------------------------------
//---------------------------------------------------------------------------------
public void solve() {while (expandNodes(p)) {p=findBestNode();}}//busca el nodo mas apropiado durante la expancion
//---------------------------------------------------------------------------------
public int getCost() {return (usedList.size() + fringeList.size());}//entrega jugadas
//---------------------------------------------------------------------------------
// Encuentra mejor nodo fde la lista
private Puzle findBestNode()
{
Puzle best;
Puzle test;
// Si el borde esta bacio toma el unico nodo
if (fringeList.size()==0)
best = (Puzle)usedList.elementAt(0);
// Si no encuentra el primer nodo lo prepara para su comparacion
else
best = (Puzle)fringeList.elementAt(0);
for (int i=1; i<fringeList.size();i++)
{
test = (Puzle)fringeList.get(i);
// Obtiene el valor heuristico para el nodo
int bestH = best.getDepth() + best.getH();
int testH = test.getDepth() + test.getH();
// Si es inferior cambia por el mejor
if (testH < bestH)
best = test;
}
return best;
}
//---------------------------------------------------------------------------------
private boolean expandNodes(Puzle p)
{
int[] test;
Puzle temp;
// toma nodo fuera de la franja
fringeList.remove(p);
// agregarlo a la lista utilizada por GRAPH-SEARCH
int parentID = usedList.size();
usedList.add(p);
// agregarlo a la lista utilizada por GRAPH-SEARCH
if (p.getH() == 0)
return false;
// otra prueba de todas las direcciones
test = p.up();
temp = new Puzle(test, p.isManhattan(), p.getDepth(), parentID);
addToFringe(temp);
test = p.down();
temp = new Puzle(test, p.isManhattan(), p.getDepth(), parentID);
addToFringe(temp);
test = p.left();
temp = new Puzle(test, p.isManhattan(), p.getDepth(), parentID);
addToFringe(temp);
test = p.right();
temp = new Puzle(test, p.isManhattan(), p.getDepth(), parentID);
addToFringe(temp);
return true;
}
//---------------------------------------------------------------------------------
private void addToFringe(Puzle p)
{
// no repite nodos
if (!nodeRepeated(p))
{
p.addMove();
fringeList.add(p);
}
}
//---------------------------------------------------------------------------------
private boolean nodeRepeated (Puzle node)
{
for (int i=0; i<usedList.size(); i++)
{
if (node.equals((Puzle)usedList.get(i)))
return true;
}
return false;
}
//---------------------------------------------------------------------------------
public void print()
{
Vector list = new Vector();
// Obtiiene la solucion
Puzle node = getPuzzleSolution();
// Agrega el nodo a la lista de soluciones
list.add(node);
// Busca el nodo padre
int parentID = node.getParentID();
while (parentID != -1)
{
node = (Puzle)usedList.elementAt(parentID);
list.add(node);
parentID = node.getParentID();
}
for (int i = 1; i <= list.size(); i++)
{
if (i ==1)
{
System.out.println("Original:");
System.out.println((Puzle)list.elementAt(list.size()-i));
}
else
{
System.out.println("paso " + ( i -1)+ ":");
System.out.println((Puzle)list.elementAt(list.size()-i));
}
}
System.out.println("\nSolucionado con "+getPuzzleSolution().getDepth()+" paso(s).");
}
//---------------------------------------------------------------------------------
public Puzle getPuzzleSolution()
{
return (Puzle)usedList.lastElement();
}
//---------------------------------------------------------------------------------
} // Fin de la clase Resuelve
/*
*
*
*/
package project01;
import java.util.Date;
/**
*
* @author jonathan
*/
class Tiempo
{
Date now;
long start;
//---------------------------------------------------------------------------------
public Tiempo() {}
//---------------------------------------------------------------------------------
// Tiempo Inicial
public void start()
{
now = new Date();
start = now.getTime();
}
//---------------------------------------------------------------------------------
// Tiempo Final
public long end()
{
now = new Date();
long end = now.getTime();
return ((end-start));
}
} // Fin Clase Tiempo
Parte III Experimentación con los algoritmos implementados
El programa genera el estado inicial aleatorio con random, por lo tanto, para realizar las pruebas se tuvo que comentar esta parte del código y generar los estados iniciales solicitados para evaluar cada uno de los casos.
La solución del puzle dependerá del estado final que se elija, el estado final que se escogió es el siguiente:
Los estados iniciales usados para realizar las pruebas son los siguientes:
# E1 E2 E3 E4
#
# +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
# | 2 | 8 | 3 | | 4 | 8 | 1 | | 2 | 1 | 6 | | 5 | 2 | 3 |
# +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
# | 1 | 6 | 4 | | 3 | H | 2 | | 4 | H | 8 | | H | 4 | 8 |
# +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
# | 7 | H | 5 | | 7 | 6 | 5 | | 7 | 5 | 3 | | 7 | 6 | 1 |
# +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
En ninguno de estos casos se encontró resultado, esto debido a un error conocido como error de paridad, el cual ocurre cuando se produce una violación del orden de la posición de acuerdo a su valor consecutivo, en otras palabras cuando un número mayor se encuentra justamente detrás de un número menor.
