Inteligencia Artificial

Traducido por Virginia Herrera Pinell

II. Búsqueda
Las técnicas de búsqueda juegan un rol clave en muchas partes del campo Inteligencia Artificial
(I.A). Estos algoritmos proveen los conceptos que son la columna vertebral de casi cualquier
abordaje a la exploración sistemáticas de alternativas.
Se inicia con alguna terminología y estrategias básicas de implementación y luego se
abordaráncuatro clases de algoritmos de búsqueda los cuales difieren en dos dimensiones:
Primero, es la diferencia entre la búsqueda no informada (o ciega) y la búsqueda informada
(o heurística). Las búsquedas informadas tienen acceso a información de la tarea específica
que puede ser usada para hacer la búsqueda más eficiente. La otra diferencia es entre la
búsqueda del cualquier camino y la búsquedaóptima. Las búsquedas óptimas buscan el mejor
camino posible mientras la búsqueda de cualquier camino, buscarán sólo alguna solución.
Los métodos de búsqueda que trataremos son definidos en árboles o grafos, por eso
necesitamos fijar alguna terminología para estas estructuras:




Un árbol está compuesto de nodos y enlaces (círculos y líneas) no hay ciclos (bucles).
Los nodos sonreferidos algunas veces como vértices y los enlaces como aristas (esto
es más común en la teoría de grafos).
Un árbol tiene un nodo raíz (donde el árbol ¨comienza¨). Todos los nodos tienen un
único padre (ancestro directo) excepto la raíz. Más general aun, un nodo ancestro es
un nodo que puede ser alcanzado por alcanzar al nodo padre repetidamente. Cada
nodo (excepto los nodos terminales (hoja))tiene uno o más hijos (descendiente
directo).Mas generalmente, un nodo descendiente es un nodo que puede ser
alcanzado al acceder al nodo hijo repetidamente.

Un grafo es también un conjunto de nodos conectados por enlaces pero donde los ciclos son
permitidos y un nodo puede tener múltiples padres. Tenemos que lidiar con dos tipos de
grafos: grafos dirigidos, donde los enlaces tienendirecciones (ej. calles de una vía).
ARBOL
RAIZ

CONECTOR

B ES PADRE DE C
C ES HIJO DE B
A ES ANCESTRO DE C
C ES DESCENDIENTE DE A

A

NODO
(VERTICE)

B

C

Y grafos no dirigidos donde los
enlaces van en ambas vías. Un
grafo no dirigido es como la
abreviatura de un grafo con
enlaces dirigidos yendo en
sentido opuesto a cada nodo
conectado.

TERMINAL
(HOJA)
Grafo Dirigido(Calles de una vía)

Grafo No Dirigido

Los grafos están en todas partes, pueden representar una red de carreteras o ruta de aviones
o redes de computadoras. En todos estos casos podríamos estar interesados en encontrar un
camino a través del grafo que satisface alguna propiedad, ejemplo: donde se tenga que hacer

1

Traducido por Virginia Herrera Pinell
la menor cantidad de ¨brincos¨ o elcamino de menor costo, asumiendo que los brincos no son
todos equivalentes, etc.
De todas formas, los grafos pueden ser mucho más abstractos. Pueden denotar descripciones
de un estado del mundo, ejemplo: los nodos pueden contener información de qué bloque está
arriba de cuál otro bloque en un determinado momento, y que los enlaces representen
acciones que cambian de un estado a otro.
Uncamino a través de un grafo (de un estado inicial a un estado meta) es un ¨plan de acción¨
para llegar a algún estado meta deseado desde algún estado inicial conocido. Es el tipo de
grafo que es de mayor interés general en I.A.
EJEMPLOS DE GRAFOS

México

RUTAS DE AVIACION

Tegucigalpa
Guatemala
B

Managua
San Salvador

Planeando Acciones
Grafos de posibles
estados del mundo

AB

C

C

C

B

A

Poner C en
A

Poner C en
A

A

Poner B en
C

A

C
Poner C en
B

A

B

Poner A en
C

C

Un abordaje general para
solucionar problemas en I.A. es
reducir el problema para
plantearlo como una búsqueda
en grafo. Para usar este abordaje
debemos especificar qué son los
estados, las acciones y el objetivo
meta.

B

Un estado esta...