Busqueda por profundizacion iterativa y amplitud iterativa Inteligencia Artificial

taller
1) Para el grafo usted deberá llegar de A a H aplicando los algoritmos:
A) Interactive Debending (I D) Búsqueda profundización iterativa.
B) Amplitud iterativa.

2) Explicar:
A) El pseudocodigo de los algoritmos anteriores.
B) Su complejidad exponencial y temporal (mejor caso, peor caso, caso medio).
C) Completo? Justifique su respuesta.
D) Óptimo? Justifique su respuesta.

solución
profundización iterativa:
es un algoritmo que crea un limite de profundidad que nos permite recorrer el árbol y encontrar la solución, este algoritmo comienza desde la raíz que es el nivel 1 hasta N niveles de profundidad donde este la respuesta.
    
Árbol correspondiente al grafo 
basandonos en el árbol podemos notar que de A a K  hay 7 niveles de profundidad.
Es necesario recordar que el algoritmo se desarrolla nivel por nivel ejecutandose varias veces desde la raíz hasta el nodo que es la solución.

ahora realizamos la prueba de escritorio:
Profundidad               L             N      Sucesores
1                               A             A           CB
2                               CB          C            E
3                               EB           E            G
4                               GB          G            HF
5                               HFB         H     SOLUCION

el recorrido fue: A,C,E,G,H.





Pseudocodigo Interactive Debending (ID) Búsqueda profundización iterativa.

  1) Se define la profundidad.
 2) Se desarrolla el árbol realizando una búsqueda en profundidad hasta el limite definido en el punto anterior.
 3) Si se encuentra la solución termina.
 4) Sino se establece un nuevo limite y volvemos al segundo paso.

Su complejidad exponencial y temporal
d= profundidad b= nodos hijos
Tiempo: exponencial O(b^d)
(d)*b+(d-1)*b^2+....+(2)*b^d-1+(1)*b^d
Espacio: lineal O(b*d), O(d), O(1).

Completo? 
Si, porque se va ampliando por niveles y esto lo que hace es que se lleve una búsqueda limitada que permite tener varias búsquedas al tiempo y así lograr encontrar el resultado deseado.

Óptimo? 
Si porque a medida que se va haciendo la búsqueda por niveles va a encontrar la solución mas cercana a la raíz.

Amplitud iterativa.

Es un algoritmo que combina la búsqueda por anchura y las iteraciones por cada nivel aumentando el ancho del árbol en cada ciclo para así llegar a la solución. Es necesario especificar que este algoritmo puede caer en una rama infinita y no encontrar soluciones.

como podemos ver en el árbol que corresponde al grafo comenzamos a desarrollar el algoritmo de amplitud iterativa para encontrar la solución.

Extendiendo solo un hijo
Nivel      L                       N                SUCESORES
1            A                      A                       B
2            B                      B                       C
3            C                      C                  NO TIENE SUCESORES

Extendiendo dos hijos por nodo
               L                      N                   SUCESORES   
              A                      A                      CB
              CB                    C                      E
              EB                     E                     G
              GB                    G                      HF
              HFB                  H                 NO TIENE SUCESORES Y ES SOLUCIÓN
              FB                     F                      H
              HB                    H                  NO TIENE SUCESORES Y ES SOLUCIÓN
              B                       B                      D
              D                       D                      E
              E                        E                      G
              G                       G                      HF
              HF                     H                 NO TIENE SUCESORES Y ES SOLUCIÓN
              F                        F                       H

              H                       H                 NO TIENE SUCESORES Y ES SOLUCIÓN     

 recorrido es: A,C,E,G,H. 
pseudocodigo Amplitud iterativa.



                           
         







Su complejidad exponencial y temporal
b=nodos hijos
d=profundidad
Tiempo: O(b^d)
Espacio: O(bd)

Completo? 
Si, porque se va ampliando por niveles y el ancho del árbol, si existe una solución la encontrara. cabe aclarar que puede caer en ciclos infinitos y no encontrar la solución.

Óptimo? 
Si el coste de paso es 1.

Comentarios

Publicar un comentario

Entradas más populares de este blog

Proyecto Perceptron Simple (Código C++)

Imagen
INTRODUCCIÓN En 1936 Alan Turing estudio el cerebro como una forma de ver el mundo de la computación. Sin embargo, los primeros teóricos que concibieron los fundamentos de la computación neuronal fueron Warren McCulloch un neurofisiología y Walter Pitts un matemático quienes en 1943 lanzaron una teoría acerca de la forma de trabajar de las neuronas. Ellos modelaron una red neuronal simple mediante circuitos eléctricos. Años más tarde en 1949 Donald Hebb escribió un importante libro en el que explicaba los procesos del aprendizaje desde un punto de vista psicológico, desarrollando una regla de como el aprendizaje ocurría. Su idea fue que el aprendizaje ocurría cuando ciertos cambios en una neurona eran activados. Los trabajos de Hebb formaron las bases de la Teoría de las Redes Neuronales. Luego en 1957 Frank Rosenblatt desarrolla el Perceptrón, Esta es la red neuronal más antigua utilizándose hoy en día para aplicación como reconocedor de patrones. Este modelo era capaz de ge...
Leer más

IDA* Algoritmo Inteligencia Artificial

Imagen
El algoritmo de Búsqueda en Profundidad Iterativa, es un algoritmo ciego que aplica reiteradamente la búsqueda en profundidad. En cada aplicación incrementa en una unidad la profundidad de la búsqueda.  El algoritmo A*, se usa en problemas de optimización y es admisibilidad, esto es encuentra soluciones óptimas, si usa una heurística admisible.  El algoritmo IDA* Fase básica: Como el A* ordena los nodos según el valor de f(n) = g(n) + h(n), pero al expandir un nodo excluye como sucesores a aquellos nodos cuyo coste supere una cota prefijada. Si no alcanza solución. Fase de reiteración: Si todos los candidatos a sucesores han superado la cota, toma como nueva cota el coste del nodo menos transgresor y relanza de nuevo el algoritmo. IDA* es completo y optimo, pero al ser iterativo en profundidad, necesita menos memoria. complejidad espacial: O(b*d)=f*/minimo valor costes. d="profundidad" de lamejor solucion.
Leer más

Proyecto Minimax-Scout (Código C++)

Imagen
INTRODUCCIÓN La teoría de juegos plantea que debe haber una forma racional de jugar a cualquier «juego» (o de negociar en un conflicto), especialmente en el caso de haber muchas situaciones engañosas y segundas intenciones; así, por ejemplo, la anticipación mutua de las intenciones del contrario, que sucede en juegos como el ajedrez o el póquer, da lugar a cadenas de razonamiento teóricamente infinitas, las cuales pueden también trasladarse al ámbito de resolución de conflictos reales y complejos. En síntesis, y tal como se comentó, los individuos, al interactuar en un conflicto, obtendrán resultados que de algún modo son totalmente dependientes de tal interacción. Análisis Para el siguiente proyecto utilizaremos dos tipos de algoritmos por un lado Minimax y por el otro el algoritmo de Scout los cuales nos brindaran las mejores soluciones. El algoritmo de minimax consiste en la elección del mejor movimiento para el computador, suponiendo que el contrincante escogerá ...
Leer más