TIPOS DE BUSQUEDA EN INTELIGENCIA ARTIFICCIAL

TIPOS BÁSICOS DE BUSQUEDA

REDES Y BÚSQUEDAS

Encontrar una trayectoria del punto S al punto G involucra dos costos:

El costo del cálculo para encontrar la trayectoria.

El costo del viaje cuando se sigue la trayectoria

ÁRBOL DE BÚSQUEDA

• Es una representación que considera todas las trayectorias posibles en la red:  
  
  
  Los nodos representan trayectorias, y las ramas conectan trayectorias a extensiones de trayectoria de un solo paso. 

• Idea es construir al vuelo este árbol, siguiendo una estrategia de búsqueda.

• El número total de trayectorias de un árbol con factor de ramificación b y profundidad d es bd. 

BÚSQUEDA EN PROFUNDIDAD PRIMERO

Para llevar a cabo una búsqueda en profundidad, 

1. Inserte en una pila el elemento raíz (nodo de partida) 

2. Hasta que el elemento tope sea el nodo meta, o se vacié la pila

           1. Si nodo tope tiene hijos, insertar el hijo siguiente aun no visitado, según ordenamiento. 
              2. Si no, entonces eliminar nodo tope. 

3. Si el nodo meta se alcanza, mencione éxito, de lo contrario, notifique el fracaso. 

La búsqueda por profundidad se usa cuando queremos probar si una solución entre varias posibles cumple con ciertos requisitos. 

 BÚSQUEDA EN AMPLITUD PRIMERO

Para llevar a cabo una búsqueda en profundidad

1. Inserte en una pila el elemento raíz (nodo de partida) 

2. Hasta que el elemento tope sea el nodo meta, o se vacié la pila 

       1. Si nodo tope tiene hijos, insertar el hijo siguiente aun no visitado, según ordenamiento. 
       2. Si no, entonces eliminar nodo tope. 

3. Si el nodo meta se alcanza, mencione éxito, de lo contrario, notifique el fracaso. 

Sirve para cualquier estado, sin embargo para algunos es muy tardado.

Es una estrategia sencilla en la que se expande el nodo raíz, a continuación se expande todos los sucesores del nodo raíz, después sus sucesores etc.  

RAMIFICACIÓN Y COTA

 
Menos sacrificado para encontrar la ruta óptima. 

Idea básica es expandir en cada ocasión la ruta parcial con el menor costo hasta el momento. 

          ◦ Es decir, todos los nodos abiertos hasta el momento entran en consideración. 

Similar a método “primero el mejor”, pero al revés. 

         ◦ En lugar de seguir el trayecto que aparentemente tiene la menor distancia hacia él.

ALGORITMO BÁSICO

 

Formar una cola de trayectos parciales. Inicialmente sólo tiene el elemento raíz.

Hasta que la cola se vacié o se alcance el nodo objetivo, determinar si el primer elemento alcanza el nodo objetivo. 

         ◦ Si alcanza el objetivo, salir. 
         ◦ Si no, entonces; 

Borrar el nodo de la cola.

Agregar sus hijos a la cola.

Ordenar los nodos por costo acumulado.

Si el nodo objetivo fue encontrado mencionar éxito, de lo contrario anunciar falla. 

PROCEDIMIENTO A*

Es una búsqueda de ramificación y cota con: 

      ◦ Estimación de distancia restante 
      ◦ Eliminación de trayectorias redundantes

Si la estimación de la distancia restante es un limite inferior de la distancia real, entonces A* produce solucione. 
  

BÚSQUEDA HEURÍSTICA

 

Sirve para asignar a cada estado una estimación del coste optimo a la solución.

Se usa para resolver muchos problemas difíciles (explosión combinatoria), es necesario muchas veces llegar a un compromiso de los requerimientos de movilidad y sistematicidad y construir una estructura de control que no necesariamente garantiza el encontrar la mejor respuesta, sino que casi siempre encuentra una buena respuesta. 

Una técnica heurística mejora la eficiencia del proceso de búsqueda sacrificando, usualmente, exhaustividad. 

ALGORITMO BÁSICO

Formar una cola de trayectos parciales. Inicialmente sólo tiene el elemento raíz. 

Hasta que la cola se vacié o se alcance el nodo objetivo, determinar si el primer elemento alcanza el nodo objetivo. 

     ◦ Si alcanza el objetivo, salir. 

     ◦ Si no, entonces; 

           - Borrar el nodo de la cola 

           - Agregar sus hijos a la cola.

           - Ordenar los nodos por costo acumulado 

Si el nodo objetivo fue encontrado mencionar éxito, de lo contrario anunciar falla. 

ASEGURA LA RUTA OPTIMA

 

 

¿cuál es la respuesta del método? 

¿cómo podemos asegurar encontrar la ruta óptima? 

¿cuándo debemos terminar el algoritmo? 

◦ Cuando todas las rutas parciales tengan igual o mayor peso que la trayectoria