Una introducción a la Inteligenca Artificial (IA)



Descargar 2.01 Mb.
Página18/29
Fecha de conversión20.03.2018
Tamaño2.01 Mb.
Vistas524
Descargas0
1   ...   14   15   16   17   18   19   20   21   ...   29

3.4. Búsqueda de soluciones.



Como ya se mencionó, una vez representado el problema con el método espacio-estados, lo único que resta es encontrar el estado meta a través de una trayectoría que comienza en el estado inicial. Existen diferentes métodos de búsqueda, cada uno con sus respectivas ventajas y desventajas. En esta unidad nos enfocaremos a los más básicos: búsqueda en profundidad y búsqueda en amplitud.
Para explicar estos métodos suponga que desea hallar una trayectoria de una ciudad a otra mediante un mapa de carreteras como el de la figura 3.3. La trayectoria deberá empezar en la ciudad S, su punto inicial y terminar en la ciudad G, su meta.
La manera más sencilla de encontrar una solución es:

  1. Considerar todas las trayectorias posibles.

  2. Descartar las trayectorias que pasan más de una vez por una ciudad.

  3. Ordenar todas las trayectorias posibles a partir del nodo inicial en un árbol de búsqueda.


En la figura 3.4. se muestra el árbol de búsqueda que representa todas las trayectorias posibles que salen del nodo inicial de la red de la figura 3.3.





Figura 3.3. Mapa de carreteras de una ciudad a otra





Figura 3.4. Árbol de búsqueda del mapa de carreteras de la figura 3.2
Nótese que el número de trayectorias se expande exponencialmente a medida que aumenta la profundiad del árbol. Por lo que, para realizar una búsqueda siempre se debe intentar aplicar un método de búsqueda que tenga probabilidad de desarrollar el menor número de trayectorias posibles.


3.4.1 Búsqueda primero profundidad

Una forma sencilla de hallar una trayectoria es tomar uno de los hijos en cada nodo que se visita, y avanzar a partir de ese hijo. Otras alternativas del mismo nivel se ignoran por completo, en tanto haya posibilidad de alcanzar la meta mediante la selección original. Esta estrategia es la esencia de la búsqueda primero en profundidad. Un ejemplo de búsqueda en profundidad se muestra en la figura 3.5. A partir del nodo inicial (S) se elige una alternativa y se le sigue en cada nodo hasta llegar a la meta o a un nodo en el que ya no es posible seguir hacia abajo, la búsqueda se reinicia en el antecesor más cercano que posea hijos sin explorar




Figura 3.5. Búsqueda en profundidad del mapa de la figura 3.3


El algoritmo para la búsqueda en profundidad se enlista a continuación:


  1. Forme una lista con la trayectoria que contiene el nodo inicial.

  2. Hasta que la lista esté vacía

2a. Elimine la primer trayectoria de la lista

2b. Si la trayectoria llega al nodo meta vaya al paso 3

2c. Si no, genere nuevas trayectorias extendiendo la trayectoria eliminada

2d. Si alguna trayectoria generada contiene ciclos, elimínela

2e. Agrege las trayectorias generadas, si existen, al inicio de la lista


  1. Si se encontró el nodo meta notificar éxito, si no notificar fracaso.


3.4.2 Búsqueda en amplitud

La búsqueda en amplitud revisa todas las trayectorias de una longitud dada antes de avanzar a una trayectoria más larga. En la figura 3.6, la búsqueda en amplitud encuentra una trayectoria completa al nodo G en el cuarto nivel a partir del nivel raíz.




















Figura 3.6. Búsqueda en profundidad del mapa de la figura 3.3.

El algoritmo de búsqueda en amplitud se muestra a continuación:




  1. Forme una lista con la trayectoria que contiene el nodo inicial.

  2. Hasta que la lista esté vacía

2a. Elimine la primer trayectoria de la lista

2b. Si la trayectoria llega al nodo meta vaya al paso 3

2c. Si no, genere nuevas trayectorias extendiendo la trayectoria eliminada

2d. Si alguna trayectoria generada contiene ciclos, elimínela



2e. Agrege las trayectorias generadas, si existen, al final de la lista

  1. Si se encontró el nodo meta notificar éxito, si no notificar fracaso.



Ventajas y desventajas de cada método:

Búsqueda en Profundidad

Ventaja:

  • La búsqueda en profundidad resulta una buena idea cuando se tiene la confianza de que todas las trayectorias parciales llegan a callejones sin salida o se vuelven completas después de un número razonable de pasos.


Desventaja

  • Si existen trayectorias largas, incluso infinitamente largas, que no llegan a callejones sin salida ni se vuelven completas. En tales ocasiones se requieren métodos alternativos de búsqueda.


Búsqueda en Amplitud

Ventaja:

  • La búsqueda en amplitud funciona aun con árboles infinitamente profundos o de profundidad prácticamente infinita.

  • La búsqueda en amplitud resulta una buena idea cuando se tiene la certeza de que el factor de ramificación es pequeño.

    • También se puede optar por la búsqueda en amplitud, en lugar de la búsqueda en profundidad, si preocupa el hecho de que puede haber trayectorias largas y hasta infinitas, incapaces de llegar a callejones sin salida o volverse completas.

Desventaja:

  • L a búsqueda en amplitud constituye un desperdicio cuando todas las trayectorias conducen a la meta aproximadamente a la misma profundidad.

  • La búsqueda en amplitud no es una buena idea si el factor de ramificación es grande o infinito, debido a la expansión exponencial.



Ejercicio 3.4.


Realiza la búsqueda en profundidad y amplitud siguiendo los algoritmos respectivos para los siguientes mapas en donde la ciudad inicial es la S y la final es la G








Ejercicio 3.5.


Realiza el árbol de búsqueda en profundidad y amplitud para resolver el problema de las jarras de agua y el problema de los caníbales siguiendo los algoritmos respectivos






Solución propuesta Problema de las Jarras:

Asignando x=3l, y=4l, representando estados (x,y).

Estado inicial: (0,0) => Estado final: (x,2)

Inicio de árbol:


(0,0)

(3,0) (4,0)



Solución propuesta Problema de los canibales:

Estado inicial: (3m,3c,1,0m,0c,0)= 3 misioneros, 3 canibales, 1 barca y cero en otro lado.

Estado final: (0m,0c,0,3m,3c,1)= 0 misioneros, 0 canibales, 0 barca, y todos del otro lado.

Inicio de árbol:


(3m,3c,1,0,0,0)

1m,1c 2c 2m

(2m,2c,0,1m,1c,1) (3m,1c,0,2c,0,1) (1m,3c,0,2m,0,1)

(3m,3c,1,0,0,0) (3m,2c,1,0,1c,0)




se elimina el nodo que repite un estado




Compartir con tus amigos:
1   ...   14   15   16   17   18   19   20   21   ...   29


La base de datos está protegida por derechos de autor ©psicolog.org 2019
enviar mensaje

enter | registro
    Página principal


subir archivos