Breadth First Search (Búsqueda Anchura)

Búsqueda en Anchura
utilizando Java.
(Breadth First Search).

nteligencia Artificial

Estados
Definiremos primeramente el Estado Inicial y
Final del Puzzle . El estado inicial como
“desordenado”, osimplemente como
cualquier estado distinto al final.

Figura N°1 Estado Inicial

Figura N°2: Estado Final

El espacio de estados para este problema se encuentra
representado por el conjunto de todaslas posibles ubicaciones
de cada una de las fichas.

Operaciones
Para el problema se han definido 4 tipos de operaciones.
Las cuales son las de movimiento de una ficha hacia arriba,
abajo, izquierday derecha; donde la ficha que se mueve a una
cierta posición intercambia de lugar con la ficha que se
encontraba anteriormente en dicho lugar.

En la figura anterior podemos ver los 4 primerosestados
posibles, y los siguientes posibles estados para cierto estado
inicial. Así podríamos seguir completando el árbol hasta dar
con la solución (estado final).

Búsqueda de Anchura
(BFS)

ALGORITMODeclarar lista doblemente enlazada openlist.
Agregar el nodo raíz a openlist.
Mientras la openlist no está vacía hacer los siguientes ciclos:
a) Recuperar, después remover el primer nodo de nuestraopenlist
b) Comprobar estado del nodo recuperado
Si el nodo es la meta entonces se detiene el ciclo y se
imprime la solución
Si el nodo no es la meta, entonces:
- Expandir el nodo recuperado
- Agregar elnodo expandido al final de la openlist
- Continuar el ciclo (loop)
1.
2.

Estructura de Datos
Representación
Índice de posiciones en el “Tablero” (porque estamos utilizando
una cadena – string).
012345
678
1.

Si str = “135782460” entonces corresponde a:
135
782
460
Donde 0 es nuestro espacio en blanco

Openlist
Utilizando una estructura de datos de lista enlazada para
openlist.

EstructuraAdicional
a) Hashmap para almacenar currentState (estado
actual) y su padre (sin esto, no seríamos capaces de
rastrear la posición de la búsqueda).
b) Hashmap para almacenar currentState (estado...