Búsqueda por profundidad Inteligencia Artificial

Algoritmo 


1) Lista L<- nodo raíz.
2) Si (L ϵ 0) fallo stop.
Sino N <- extrae el primero.
3) Genera los sucesores de N. Si alguno es solución stop.
Sino adicionara al principio de L todos los sucesores.
4) Ir a 2






Complejidad:
Tiempo
Peor caso:

Mejor caso: (b*d).

Espacio:





Desarrollar el siguiente problema por el método de profundidad y responder:

Se tienen 3 sapos y 3 ranas cada sapo y cada rana solo puede saltar por encima de otro si el lugar esta vació, ej: el sapo2 puede saltar por encima del sapo3 y quedar en el espacio en blanco o la rana1 puede saltar al espacio en blanco. con base en los ejemplos queda demostrado las dos formas de moverse.

Estado inicial:                                                                                   




 Estado final:
Operadores:
Saltar 1 hacia la derecha espacio en blanco.
Saltar 1 hacia la izquierda espacio en blanco.
Saltar 2 hacia la derecha espacio en blanco.
Saltar 2 hacia la izquierda espacio en blanco.





Cuantos nodos genero:
Nodos generados: 4^18
4 ya que son los posibles comienzos a la 18 que son los movimientos en resolverse.

Cuanto se expandió:
Nodos expandidos: 4^17
4 ya que son los posibles comienzos a la 17 ya que el ultimo nodo no se abre.

factor de ramificacion: 4
Estados posibles: 7! =5040.

podemos deducir que el algoritmo de busqueda en profundidad encontraria la mejor solucion en 18 pasos, si y solo si los sucesores se dan de la manera en que aparecen en la imagen, de tal forma que siempre escogeria el mejor camino y daria con la solucion.
En caso de que los sucesores se den de otra manera, podria demorarse mas en la solucion, y por ende podria entrar en un ciclo y nunca encontrar la solucion al problema planteado.

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