Ir al contenido principal

BÚSQUEDA POR PROFUNDIDAD

Teniendo en cuenta el siguiente algoritmo de busqueda por profundidad:
1. Lista L <- NODO RAIZ.
2. Si L pertenece a vacio FALLO STOP
   Sino  N<- extrae el primero 
3.Genera los sucesores de N. Si alguno  es solucion STOP
   Sino adiciona al inicio de L todos los sucesores 
4. Ir a 2


 PRUEBA DE ESCRITORIO:

Se tienen 3 sapos y 3 ranas, cada no de ellos  puede saltar por encima de otro solo si el lugar esta vacío.



S1S2S3R1R2R3
ROCAROCAROCAROCAROCAROCAROCA



1RRRSSS
2RRRSSS
3RRSRSS
4RRSRSS
5RRSSRS
6RRSSRS
7RRSSRS
8RRSRS
9RSRSRS
10SRSRSRS
11SRSRRS
12SRSRSR
13SRSRSR
14SRSSRR
15SSRSRR
16SSRSRR
17SSSRRR
18SSSRRR

¿Cuantos nodos genero?

  4^18 (4 son los primeros estados posibles y 18 son el numero de estados generados en la mejor solución)

¿Cuantos nodos se expandieron?

  4^17 (4  son los primeros estados posibles y 17 son los nodos expandidos)

FACTOR DE RAMIFICACIÓN: 4.

 ESTADOS POSIBLES: 7! 

Comentarios

Publicar un comentario

Entradas populares de este blog

REDES NEURONALES ARTIFICIALES

Redes Neuronales Inteligencia Artificial Historia de las Redes Neuronales: 1936: 1936 Alan Turing estudio el cerebro como una forma de ver el mundo de la computación. 1943: Warren McCulloch un neurofisiólogo y Walter Pitts un matemático crearon una teoría sobre la forma de trabajar de las neuronas. Ellos modelaron una red neuronal simple mediante circuitos eléctricos. 1949: Donald Hebb   expuso una idea, la cual   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. Escribió un importante libro en el que explicaba los procesos del aprendizaje desde un punto de vista psicológico. 1950: Karl Lashley trabajo el almacenamiento no centralizado, sino distribuido. 1954: Marvin Minsky dio el primer resultado de 40 neuronas trabajando aprendizaje hebbiano. 1956: 1°Congreso científico sobre redes neuronales. 1957: Frank Rosenblatt desarrolla el ...
Publicar un comentario
Leer más

A* ALGORITMO

Algoritmo A* El algoritmo A*es un algoritmo de búsqueda que puede ser empleado para el cálculo de caminos mínimos en una red. Se va a tratar de un algoritmo heurístico, ya que una de sus principales características es que hará uso de una función de evaluación heurística, mediante la cual etiquetará los diferentes nodos de la red y que servirá para determinar la probabilidad de dichos nodos de pertenecer al camino óptimo. Esta función de evaluación que etiquetará los nodos de la red estará compuesta a su vez por otras dos funciones. Una de ellas indicará la distancia actual desde el nodo origen hasta el nodo a etiquetar, y la otra expresará la distancia estimada desde este nodo a etiquetar hasta el nodo destino hasta el que se pretende encontrar un camino mínimo. Es decir, si se pretende encontrar el camino más corto desde el nodo origen s, hasta el nodo destino t, un nodo intermedio de la red n tendría la siguiente función de evaluación f(n) como etiqueta: f(n)= g(n) + h(n) Dond...
Publicar un comentario
Leer más