Explorando Algoritmos de Búsqueda: Costos, Estrategias y Optimización

B1t5

Coste del camino: suma de los costes de las acciones individuales del camino.

El coste de una acción es independiente del estado en que se aplique.

Coste del estado sn: coste del camino desde el estado inicial s0 al estado sn.

Búsqueda General de Soluciones

Proceso General de Búsqueda:

1. Nodo-actual <- estado inicial del problema
2. Comprobar si nodo-actual es el estado final del problema; en dicho caso, FIN.
3. Expandir nodo-actual aplicando las acciones del problema en dicho estado y generando el conjunto de nuevos estados.
4. Escoger un nodo que no ha sido expandido todavía.
5. Ir al paso 2.

Lista OPEN: conjunto de nodos no expandidos.

Los algoritmos de búsqueda se diferencian en la elección del siguiente nodo a expandir.

Algoritmo TREE-SEARCH:

Inicializar la lista OPEN con el estado inicial del problema; if lista OPEN está vacía then return fallo; expandir un nodo: escoger nodo hoja y eliminarlo de OPEN; if nodo escogido es el estado final then return solución; generar hijos y añadir esos nodos a la lista OPEN.

Estados Repetidos

Para evitarlos: incluir en el algoritmo TREE-SEARCH una lista CLOSED donde poder guardar los nodos explorados o expandidos; cuando se genera un nuevo nodo y éste está en la lista CLOSED, se elimina en vez de añadirlo a la lista OPEN; nuevo algoritmo: GRAPH-SEARCH, algoritmo que separa el grafo del espacio de estados en dos regiones: la región de nodos explorados/expandidos y la región de nodos no expandidos.

Algoritmo GRAPH-SEARCH:

La lista OPEN se implementa como una cola de prioridades: se extrae el elemento con la máxima prioridad; para cada estrategia de búsqueda se define una función de evaluación f(n) que devuelve un valor numérico para el nodo n tal que el nodo se inserta en la lista en el lugar en el que le corresponda según esa prioridad.

TREE SEARCH à mantiene OPEN pero no CLOSED (menos memoria); puede evitar estados repetidos en la lista OPEN; re-expande nodos ya explorados.

GRAPH-SEARCH à mantiene OPEN y CLOSED (mayor memoria); control de estados repetidos y caminos redundantes (reducción en la búsqueda).

Propiedades de los Algoritmos de Búsqueda

Evaluaremos las estrategias de búsqueda de acuerdo a completitud, complejidad temporal, complejidad espacial y optimalidad; soluciones que representen un balance entre coste del camino solución y coste de búsqueda (encontrar el camino solución); tipos de estrategias de búsqueda: 1) no informada o búsqueda ciega (orden de expansión de nodos) 2) informada o búsqueda heurística (expansión ‘inteligente’ de los nodos).