Introduction
Algoritmos de búsqueda en espacio de
estados
1 Departamento de Ingeniería Informática
September 8, 2025
Búsqueda en espacio de estados
Introduction
Problema de los Canibales y Misioneros
Tres misioneros y tres caníbales se encuentran en la orilla
izquierda de un río, junto con un bote que puede transportar a
lo sumo dos personas. El objetivo es transportar a todos al otro
lado del río (la orilla derecha), garantizando que en ningún
momento, en ninguna de las orillas, el número de caníbales
exceda al número de misioneros (de lo contrario, los caníbales
se comerán a los misioneros).
Búsqueda en espacio de estados
Introduction
Problema de los Canibales y Misioneros
Búsqueda en espacio de estados
Introduction
Problema de búsqueda en espacio de estados
Conjunto de posibles estados en los que puede
encontrarse el entorno, llamado espacio de estados.
Un estado inicial, a partir del que comienza la búsqueda, y
uno o varios estados objetivos, al llegar a uno de ellos
finaliza la búsqueda
Un conjunto de acciones a realizar en cada estado
Un modelo de transición que define el resultado de cada
acción
Una función de costo que proporciona el coste numérico
de aplicar la acción en el estado para alcanzar el nuevo
estado.
Una secuencia de acciones forma una ruta, y una solución
es una ruta desde el estado inicial hasta un estado objetivo
El espacio de estados se puede representar como un
grafo en el que los vértices son estados y las aristas
dirigidas entre ellos son acciones.
Búsqueda en espacio de estados
Introduction
Algoritmos de búsqueda en espacio de estados
Un algoritmo de búsqueda toma un problema de búsqueda
como entrada y devuelve una solución o una indicación de
fallo.
Algoritmos que superponen un árbol de búsqueda sobre el
grafo del espacio de estados, formando varias rutas desde
el estado inicial, buscando una que alcance un estado
objetivo (Árbol de expansión).
Cada nodo del árbol de búsqueda corresponde a un
estado en el espacio de estados y sus aristas a acciones.
La raíz del árbol corresponde al estado inicial del
problema.
Búsqueda en espacio de estados
Introduction
Estructura de datos
Los algoritmos de búsqueda requieren una estructura de
datos para realizar el seguimiento del árbol de búsqueda.
Un nodo del árbol se representa mediante una estructura
de datos con cuatro componentes:
[Link]: el estado al que corresponde el nodo;
[Link]: el nodo del árbol que generó este nodo;
[Link]ÓN: la acción aplicada al estado del padre para
generar este nodo;
[Link]-RUTA: el coste total de la ruta desde el
estado inicial hasta este nodo. En fórmulas matemáticas,
usamos g(nodo) como sinónimo de COSTO-RUTA.
Seguir los punteros PADRE desde un nodo nos permite
recuperar los estados y acciones a lo largo de la ruta hacia
ese nodo. Hacer esto desde un nodo objetivo nos
proporciona la solución.
Búsqueda en espacio de estados
Introduction
Algoritmos de búsqueda No Informada
Necesitamos una estructura de datos para almacenar la
frontera(Nodos expandidos a partir de los ya visitados). La
opción adecuada es una cola de algún tipo, ya que las
operaciones en una frontera son:
IS-EMPTY(frontera) devuelve verdadero solo si no hay
nodos en la frontera.
POP(frontera) elimina el nodo superior de la frontera y lo
devuelve.
TOP(frontera) devuelve (pero no elimina) el nodo superior
de la frontera.
ADD(nodo, frontera) inserta el nodo en su lugar
correspondiente en la cola.
Búsqueda en espacio de estados
Introduction
Algoritmos de búsqueda No Informada
A un algoritmo de búsqueda no informada no se le da
ninguna pista sobre qué tan cerca está un estado del
objetivo(s).
Búsqueda en amplitud, en la que se expande primero el
nodo raíz, luego todos los sucesores del nodo raíz, luego
sus sucesores, y así sucesivamente.
Búsqueda en profundidad, en la que se expande primero
el nodo raíz, explora una rama del grafo o árbol lo más
abajo posible antes de retroceder para explorar ramas
alternativas
Búsqueda en espacio de estados
Introduction
Búsqueda a lo ancho
Búsqueda en espacio de estados
Introduction
Búsqueda en profunfidad limitada
Búsqueda en espacio de estados
Introduction
Algoritmos de búsqueda Informada
Utiliza pistas específicas del dominio sobre la ubicación de
los objetivos puede encontrar soluciones con mayor
eficiencia que una estrategia desinformada. Las pistas se
presentan en forma de una función heurística, denotada
como h(n)
La búsqueda voraz de primero el mejor expande primero el
nodo con el valor h(n) más bajo (el nodo que parece estar
más cerca del objetivo), con el argumento de que esto
probablemente conducirá a una solución rápidamente. Por
lo tanto, la función de evaluaciónf (n) = h(n).
.
Búsqueda A* (pronunciada "búsqueda A-estrella"), una
búsqueda del "primero mejor" que utiliza la función de
evaluación f (n) = g(n) + h(n), donde g(n) es el coste de
la ruta desde el estado inicial hasta el nodo y h(n) es el
coste estimado de la mejor ruta de n hasta el objetivo
Búsqueda en espacio de estados