2.1 Introducción

Figura 2.1: Un grafo y su corresondiente árbol de búsqueda de ejemplo

Primero, algunos conceptos: nodos, arcos, nodo inicial, sucesor o hijo, padre, grado de arborecencia (asumimos finito), árbol, nodo raíz, hoja o nodo terminal, árbol uniforme, pesos/costos/premios asociados, camino, decendiente, ancestro.

• Nodos expandidos (CLOSED)
• Nodos explorados pero no expandidos
• Nodos generados pero no explorados (OPEN)
• Nodos no generados

Es común asociar una estructura de datos para cada nodo, por ejemplo:

• El estado en el espacio de estados al que corresponde el nodo
• El nodo que generó ese nodo (su padre)
• El operador que se uso para generarlo
• El número de nodos en el camino de la raíz al nodo (profundidad del nodo)
• El costo del camino

Propiedades de algoritmos de búsqueda (heurísticas):

1. Completo: un algoritmo se dice que es completo si encuentra una solución cuando ésta existe
2. Admisible: Si garantiza regresar una solución óptima cuando ésta existe
3. Dominante: un algoritmo $A_1$ se dice que domina a $A_2$ si todo nodo expandido por $A_1$ también es expandido por $A_2$ (``más eficiente que''). Se dice extrictamente dominante si $A_1$ domina a $A_2$ y $A_2$ no domina a $A_1$.
4. Óptimo sobre una clase: un algoritmo se dice óptimo sobre una clase de algoritmos si domina a todos los miembros de la clase.