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.

S1	S2	S3		R1	R2	R3
ROCA	ROCA	ROCA	ROCA	ROCA	ROCA	ROCA

1	R	R	R		S	S	S
2	R	R		R	S	S	S
3	R	R	S	R		S	S
4	R	R	S		R	S	S
5	R	R	S	S	R		S
6	R	R	S	S		R	S
7	R	R	S		S	R	S
8	R			R	S	R	S
9		R	S	R	S	R	S
10	S	R	S	R	S	R	S
11	S	R	S	R		R	S
12	S	R	S	R	S	R
13	S	R	S	R	S		R
14	S	R	S		S	R	R
15	S		S	R	S	R	R
16	S	S		R	S	R	R
17	S	S	S	R		R	R
18	S	S	S		R	R	R

¿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

Entradas populares de este blog

TALLER SEMANTICA

Ejercicio: I. Responder las siguientes preguntas. 1. Explique cada una de las componentes de las redes semánticas 2. Cuales son las ventajas y desventajas del uso de RS como forma de RC. 3. Señale la importancia del manejo de herencia en RS 4. Para que y como se utiliza la operación de confrontación. Explique con un ejemplo. II. Represente utilizando redes semánticas el siguiente conocimiento. · Los platelmintos, son animales de simetría bilateral, cuerpo aplanado y vida parasitaria. · Los moluscos son animales con simetría bilateral cuerpo blando y vida marina · Los artrópodos son animales con simetría bilateral, cuerpo anillado y vida acuática y terrestre · Los phylum cordados son del reino anima...

BUSQUEDA HEURISTICA POR COSTO UNIFORME Y HEURISTICA PURA

TORRES DE HANOI: En la imagen se muestra el grafo de la solución, se señala la mejor solución con color morado. HANOI COSTO UNIFORME LISTA NODO SUCESORES I I II(1), III(2) II(1), III(2) II(1) IV(2+1) III(2), IV(3) III(2) V(1+2) IV(3), V(3) IV(3) VI(1+3), VII(1+3) V(3), VI(4), VII(4) V(3) VIII(3+2), IX(3+1) VI(4), VII(4), VIII(5), IX(4) VI(4) STOP VII(4), VIII(5), IX(4) VII(4) VI(4+2), VIII(4+1) VIII(5), IX(4), VI(6), VIII(5) IX(4) VIII(4+1) VIII(5), VI(6), VIII(5), VIII(5) VIII(5) VII(5+1) VIII(5), VI(6), VIII(5), VII(6) VIII(5) VII(5+1) VI(6), VIII(5), VII(6), VII(6) VIII(5) IX(5+1) VI(6),VII(6), VII(6), IX(6) VI(6) STOP VII(6...

TALLER PROFUNDIDAD - AMPLITUD ITERATIVA

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. ¿Es Completo? Justifique su respuesta. D. ¿Es Optimo? Justifique su respuesta. SOLUCIÓN: 1.El problema con exigir un límite de profundidad, está precisamente en escoger un límite adecuado. Profundidad iterativa va aumentando gradualmente la profundidad hasta encontrar una meta. Es óptimo y completo. PRUEBA DE ESCRITORIO. AMPLITUD ITERATIVA: PSEUDOCODIGOS: Búsqueda en profundidad iterativa (límite: entero) prof=1; Est_abiertos.inicializar() Mientras no es_final?(Actual) y prof<limite hacer Est_abiertos.insertar(Estado inicial) Actual= Est_abierto...

INTELIGENCIA ARTIFICIAL

Buscar este blog