|
BÚSQUEDA COSTO UNIFORME
Integrantes:
- Mary Bermeo
- Lorena León
- Lourdes Moroch
Version 2
Expande un nodo n con el camino de costos más pequeños. El Algoritmo no se preocupa por el número de pasos que tiene que seguir sino de su costo más de su profundidad.
Si dos nodos tienen el mismo cambio elige uno y se convierte en búsqueda primero en anchura.
Mediante la búsqueda preferente por amplitud se encuentra el estado meta más próximo a la superficie, sin embargo éste no siempre es la solución de costo mínimo de la función general de costo de ruta.
En el caso de la BÚSQUEDA DE COSTO UNIFORME se modifica la estrategia preferente por amplitud en el sentido de expandir siempre el nodo de menor costo en el margen (medido por el costo de la ruta g(n)) en vez del nodo de menor profundidad.g(n) = PROFUNDIDAD(n).
LIMITACIONES
El costo uniforme se limita a hacer un test solo a los nodos que son seleccionados por la expansión
Si se cumplen ciertas condiciones, es seguro que la primera solución encontrada será la más barata, puesto que si hubiera una ruta más barata que fuese solución, ya se habría expandido anteriormente y ya habría sido encontrada. Esto se comprenderá más fácilmente considerando una estrategia en plena acción. Tómese el caso del problema de la determinación de ruta de la siguiente figura. El problema radica en ir de S a O, y va marcándose el costo de cada uno de los operadores. Con esta estrategia primero se expande el estado inicial, lo que produce rutas en dirección a A, E y C. Como la ruta que lleva a A es la más barata, se procede a expandirla y así generar la ruta SAO, que de hecho es una solución, si bien no es la óptima. Sin embargo, el algoritmo no admite a ésta como solución, ya que cuesta 11 y se le deja en la lista de espera, debajo de la ruta SE, cuyo costo es de 5. Es una pena crear una solución para dejarla olvidada en la lista, pero así debe ser si lo que se desea es encontrar la solución óptima, no cualquier solución. El paso siguiente es en expandir SE, generar SEO, y que ahora es la ruta más barata que queda la lista; se verifica la meta y se decide que es la solución.
DONDE SE PUEDE ENCONTRAR LA MEJORAs
Se podría encontrar una mejora con respecto al número de opciones que tenemos. Tratar de reducir al máximo las opciones para que el algoritmo no realice muchos test.
Mediante la búsqueda por costo uniforme se puede encontrar la solución más barata, siempre y cuando se satisfaga un requisito muy sencillo:
el costo de la ruta nunca debe ir disminuyendo conforme avanzamos por la ruta. En otras palabras, es importante que:
g(SUCESOR(n)) > g(n)
La restricción de que el costo de la ruta no vaya disminuyendo tiene sentido si se considera como costo de la ruta de un nodo a la suma de los costos de los operadores que configuran la ruta. Si el costo de todos los operadores no es negativo, el costo de una ruta nunca irá disminuyendo conforme se avanza, y mediante la búsqueda de costo uniforme será posible encontrar la ruta más barata sin tener que explorar el árbol de búsqueda en su totalidad. Pero si el costo de uno de los operadores es negativo, para hallar la solución óptima será necesario efectuar una búsqueda exhaustiva por todos los nodos, puesto que nunca será posible saber en qué momento una ruta (independientemente de su longitud y lo costosa que resulte) está a punto de estar en un paso con un elevado costo negativo y, en consecuencia, convertirse en la mejor de todas las rutas.
ALGORITMO
Formulación del Problema: Definir conjunto de estados y acciones que transfieren de un estado a otro
Planteamiento de Metas: Definir estado-inicial y estado-meta
Búsqueda: Evaluar entre posibles acciones y decidir "la más apropiada"
Ejecución: Efectuar acción seleccionada. Finalizar si estado-actual=estado-meta, si no regresar al paso anterior
PARTES DE UNA FUNCIÓN BIEN DEFINIDA
• Conjunto de Operadores
• Función Objetivo
• Función de Costo de Ruta
Búsqueda Primero Costo de Ruta Mínimo (COSTO UNIFORME)
Ejemplo: ?- main.
s-b-d-g
Costo = 15
/* GRAFO */
c(s,a,15). c(s,b,5). c(s,c,10).
c(a,f,3). c(b,d,5). c(b,e,8).
c(d,g,5). c(c,h,3). c(e,g,10).
c(f,g,3). c(h,g,3).
/* ESTRATEGIA: COSTO UNIFORME */
gen_nodos(X,L) :- findall(Y,c(X,Y,_),L).
hijo_mejor([Y],Y) :- !.
hijo_mejor([H1|T],Menor) :-
hijo_mejor(T,H2),
menor(H1,H2,Menor).
menor(A,B,A) :-
c(_,A,C),
c(_,B,D),
C < D, !.
menor(_,B,B).
search(X,X,0) :- write(X).
search(X,Z,C) :-
gen_nodos(X,Lista),
hijo_mejor(Lista,Menor),
c(X,Menor,C1),
write(X),write('-'),
search(Menor,Z,C2),
C is C1+C2.
main :-
search(s,g,C),
write('\nCosto'=C).
INTEGRANTES:
- ANGELICA ESPINOSA
- ANA PAZ
- JUAN PABLO JIMENEZ
ESTRATEGIAS DE BUSQUEDA
BUSQUEDA BIDIRECCIONAL
El propósito de la búsqueda bidireccional es encontrar su objetivo en el menor tiempo posible y esto se logra haciendo dos búsquedas simultáneas de ahí que el nombre de bidireccional.
- Cómo funciona el algoritmo.
Esta búsqueda hace uso de dos búsquedas las cuales se las conoce como:
- Búsqueda a la ancho o hacia adelante (En el siguiente ejemplo tenemos como objetivo F)
  
 
- Búsqueda hacia atrás: Aquí primeramente expandiremos los nodos hasta llegar a un nodo hoja, y a partir de ese nodo se empezara hacer las comparaciones. Y si el primer nodo hoja al que llegamos (al nodo que siempre llegaremos primero será el que se encuentra mas a la izquierda) no
- es el nodo objetivo entonces comparamos con el nodo que está a su derecha, y si este tampoco es entonces se empieza hacer la búsqueda hacia atrás.
 
En este punto como ya llegamos a un nodo hoja (D) y el objetivo que es F no fue encontrado busca en el siguiente nodo hoja (E) y el nodo D se elimina.
Como podemos darnos cuenta en ninguno de los dos nodos hojas se encuentra el nodo objetivo empezamos la búsqueda hacia atrás donde hacemos la comparación con el nodo B.
 
Como el nodo objetivo no se encontró en la parte izquierda empezamos a expandir el lado derecho del árbol.
Como podemos ver hemos llegado a un nodo hoja y como sabemos empezamos a comparar si dicho nodo es el nodo que estamos buscando, y como si lo es (Nodo F), hemos terminado la búsqueda.
 
NOTA: Para expandir el árbol siempre se la hace primero hacia la izquierda luego a la derecha.
Para finalizar como es el funcionamiento de la Búsqueda bidireccional solo nos queda decir que cuando se la implementada o se hace uso de esta, las dos búsquedas antes mencionadas (hacia adelante y hacia atrás), se ejecutan simultáneamente, hasta llegar a un punto donde se van a chocar o para ser más claros las dos han encontrado el Nodo Objetivo.
- Limitaciones que presenta el algoritmo.
Una de las limitaciones que presenta este tipo de búsqueda es que es que al menos uno de los arboles debe permanecer en memoria para realizara las comparaciones de pertenencia, a que nos referimos con comparaciones de pertenencia que si un árbol ya encontró el nodo objetivo (nodo que se está buscando), debe estar preguntándole al otro árbol (el cual está realizando el otro tipo de búsqueda que pude ser hacia atrás o hacia adelante) si el también ya lo encontró y comparar si es el mismo. El hacer esto implica consumo de memoria en comparación con las otras búsquedas.
Otra de las limitaciones es que en ocasiones los test de objetivo dan una descripción implícita de un conjunto posibles estados objetivo, lo que es un problema para la búsqueda hacia atrás, la cual debe construir todas las descripciones de las posibles soluciones, y cada una de estas soluciones, deben volver a ser probadas con la búsqueda hacia adelante.
- Donde se pude encontrar mejoras del algoritmo.
Una de las mejoras más significativas que se le puede hacer a este algoritmo de búsqueda es ver la manera de hacer que un árbol no esté siempre en memoria, lo que se podría hacer para solucionar esto, podría ser que para hacer las comparaciones de pertenencia solo se carguen los nodos a ser comparados y no todo el árbol.
- Características:
- Optimiza las búsquedas en comparación con las otras búsquedas.
- Realiza dos búsquedas en simultáneas en ves de solo una
-
-
BUSQUEDA BIDIRECCIONAL
== BÚSQUEDA PRIMERO EN PROFUNDIDAD CON PROFUNDIDAD ITERATIVA
==
Funcionamiento:
Combina la profundidad y anchura, ello representa un coste espacial lineal sin embargo asegura la solución óptima respecto a la longitud del camino. Y lo hace repitiendo sucesivamente el algoritmo de profundidad limitada agregando a cada iteración la profundidad máxima permitida. En cada paso se recorre un nivel mas del espacio de búsqueda. El coste espacial siempre es lineal porque las iteraciones son recorridos en profundidad.
Imagen:Ejemplo33.jpgen construcción
Recorre los nodos de un árbol en profundidad, pero con un valor de profundidad restringido, que aumentará en cada iteración. Esto evita el riesgo de internarse indefinidamente en una rama no finita, y evita también la necesidad de guardar pista de todos los nodos expandidos. Aplica la búsqueda de profundidad limitada incrementada.
Poder del algoritmo:
El requerimiento como tal de la memoria es mínimo al combinar primero en profundidad y porque optimiza el coste del camino en cuanto es una función que no disminuye con la profundidad del nodo. Además la uniformidad al expandir los nodos garantiza la mejor solución de búsqueda.
Limitaciones:
Cuando el algoritmo no hallase ninguna solución es conveniente imponer un límite máximo de profundidad en la búsqueda.
¿Donde se puede encontrar la mejora?
El número de nodos nuevos que recorremos al tener que repetir en cada iteración la búsqueda anterior, las repeticiones generan un factor constante respecto a los recorridos entonces la mejora sería que este factor sea solo a la última iteración.
Este algoritmo viene hacer uno de los utilizados cuando hay un espacio grande de búsqueda y no se conoce la profundidad de la solución.
La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayan expandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual se encuentra la solución más costosa de todas las ramas.
Algoritmo
Algoritmo Busqueda en profundidad iterativa (limite: entero)
pro f=1;
Est_abiertos.inicializar ( )
mientras (no es_final?(Actual)) y prof<l imite hacer
Est_abiertos.insertar (Estado inicial)
Actual= Est_abiertos.primero ( )
mientras (no es_final ?(Actual)) y no Est_abiertos.vacia? ( ) hacer
Est_abiertos.borrar_primero ( )
Est_cerrados.insertar (Actual)
si profundidad (Actual) <= prof entonces
Hijos= generar_sucesor es (Actual)
Hijos= tratar_repetidos ( Hijos,Est_cerrados,Est_abiertos )
fsi
Est_abiertos.insertar ( Hijos )
Actual= Est_abiertos.primero ( )
fmientras
prof=prof+1
Est_abiertos.inicializar ( )
fmientras
fAlgoritmo
Complejidad
Completitud: El algoritmo siempre encontrará la solución Complejidad temporal: La misma que la búsqueda en anchura. El regenerar el árbol en cada iteración solo añade un factor constante a la función de coste O(rp) Complejidad espacial: Igual que en la búsqueda en profundidad Optimalidad: La solución es óptima igual que en la búsqueda en anchura
Por:
María Susana Guasha
Iliana Burguán
BÚSQUEDA PRIMERO EN PROFUNDIDAD
La búsqueda primero en profundidad siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda. El progreso de la búsqueda lo podemos ilustrar en el siguiente gráfico:
La búsqueda procede inmediatamente al nivel más profundo del árbol de búsqueda, donde los nodos no tienen ningún sucesor. Cuando esos nodos se expanden, son quitados de la frontera, así entonces la búsqueda <<retrocede>> al siguiente nodo más superficial que todavía sucesores inexplorados.
IMPLEMENTACIÓN:
Esta estrategia puede implementarse por la BÚSQUEDA-ÁRBOLES con una cola última en entrar primero en salir (LIFO), también conocido como una pila. Como una alternativa a la implementación de la BÚSQUEDA-ÁRBOLES, es común aplicar la búsqueda primero en profundidad con una función recursiva que se llama en cada uno de sus hijos. El siguiente algoritmo primero en profundidad recursivo incorpora un límite de profundidad:
1.Características:
-Expande primero los nodos no expandidos más profundos. -Necesita almacenar sólo un camino desde la raíz a un nodo hoja, junto con los nodos hermanos restantes no expandidos para cada nodo del camino.
2.Capacidad del Algoritmo:
La búsqueda primero en profundidad tiene unos requisitos muy modestos de memoria.
3.Limitaciones:
El inconveniente de la búsqueda primero en profundidad es que puede hacer una elección equivocada y obtener un camino muy largo (o infinito) aún cuando una elección diferente llevaría a una solución cerca de la raíz del árbol de búsqueda. Ejemplo la búsqueda primero en profundidad explorará el subárbol izquierdo entero incluso si el nodo C es un nodo objetivo.
Imagen:arboll.jpg
4.Mejoras:
Una de las mejoras que se puede implementar en esta técnica de búsqueda primero en profundidad, es que al momento de recorrer o expandir los nodos, sólo se guarde en memoria el nodo izquierdo es decir el que se está expandiendo y no los dos hermanos, ya que esto ocupa mucho espacio de memoria para guardarlos.
5.Complejidad del Algoritmo:
Las complejidades temporal y espacial se miden en términos de:
b: máximo factor de ramificación del árbol de búsqueda
d: profundidad de la solución de menor coste
m: profundidad máxima del espacio de estados (puede ser ∞)
¿Completa? No: fallos en espacios de profundidad infinita, se debe evitar los estados repetidos a lo largo del camino.
-Completa en espacios finitos.
¿Tiempo? O(bm): terrible si m es mucho mayor que d. -si hay muchas soluciones puede ser mucho mas rápida que la búsqueda primero en anchura.
¿Espacio? O(bm), o sea, ¡lineal!
¿Óptima? No
- Esta estrategia debe evitarse cuando el espacio de búsqueda tiene una profundidad muy grande o incluso ∞.
Integrantes:
- Dante Casela
- Mayra Montalván I.
Búsqueda Primero en ProfundidadComo una variante a la búsqueda primero en profundidad apareció la búsqueda de profundidad limitada. La búsqueda primero en profundidad siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda, pero posee un gran inconveniente, el problema se da cuando en la búsqueda se hace una elección equivocada y producto de eso, el camino por recorrer se torna largo(o infinito). Un ejemplo claro podemos observar en la siguiente figura:
Imagen:Arbol2.PNG
Supongamos que el signo (*) fuera el nodo objetivo, la búsqueda primero en profundidad examinará el lado izquierdo del árbol, aun a sabiendas que el nodo objetivo se encuentra a la derecha , lo cual no resulta óptimo a la hora de evaluar el algoritmo, incluso si los símbolos (1 y /) fueran los nodos objetivos del problema; el algoritmo primero en profundidad devolverá como solución al problema el nodo que contiene “1” y esto no es del todo cierto ya que 1 es solo una parte de la solución. Además falta por mencionar el caso en el que el subárbol izquierdo tiene una profundidad ilimitada, el algoritmo caería en un ciclo infinito sin obtener nunca la respuesta, a esto se conoce profundidad ilimitada (árboles ilimitados). Para resolver el problema de profundidad ilimitada, se adicionó a la búsqueda primero en profundidad un límite l, que es predeterminado, el cual indica la profundidad hasta la que se debe evaluar el árbol, si bien es cierto esto contrarresta de manera efectiva la profundidad ilimitada, sin embargo plantea fuentes adicionales de incompletitud, y esta son: • L<d: Es decir cuando el límite l es demasiado corto (esto es probable cuando d es desconocido), tanto así para dejar al margen al nodo objetivo d de la búsqueda.
Imagen:Ld.jpg
• L > d: De forma contraria cuando l es demasiado amplio, el algoritmo deja de ser óptimo ya que como vimos empiezan buscando en el subárbol izquierdo y si el nodo objetivo se encuentra en el subárbol derecho, se hace un desperdicio de recursos y tiempo.
Imagen:Cosas.png
A continuacion una implentacion con clases, usando el lenguaje de programacion java, del algoritmo de busqueda con profundidad limitada, que muestra como es el flujo llevado a cabo para cumplir con el objetivo de encontrar una solucion al problema, Podemos apreciar tambien que este algoritmo esta basado en una busqueda normal en un arbol binario, podemos compararlo y decir que es un mejor del algorito de busqueda en PREORDEN(raiz, izquierdo, derecho), pero en el nuevo algoritmo ya trabajamos con pilas que almacenan toda la informacion desplegada para su posterior evaluacion/comparacion y liberacion.
Imagen:Algoritmo.jpg
El defecto por decirlo de esta manera, que presenta este algoritmo, es que al establecer un límite de búsqueda, estamos limitando la búsqueda hasta un cierto nivel en general, pero que pasaría si el elemento que esta siendo buscado se encuentra un nivel mas abajo del limite establecido, o simplemente se encuentre en cualesquiera de sus niveles, en este caso, si nos damos cuenta estamos suspendiendo la búsqueda cuando hay la posibilidad de encontrar una solución, y simplemente decimos que ya no existe tal solución.
Integrantes: Santiago Fernando Suáres/Luis Eduardo Ríos
BUSQUEDA BIDIRECCIONAL 1
INTEGRANTES:
Alex Gonzaga
Freddy Ojeda
¿Cómo funciona el algoritmo?
La búsqueda bidireccional funciona –como su nombre lo dice- haciendo búsquedas en ambas direcciones, la primera desde el inicio, y la segunda desde el último nodo que se tomará como un nodo objetivo ficticio, para esto se puede decir que se realiza una copia del árbol, para en el primer árbol realizar una búsqueda desde el inicio, que puede ser por ejemplo la búsqueda primero en anchura, y en el segundo realizar una búsqueda desde el ultimo nodo, es decir una búsqueda hacia atrás. La búsqueda se detiene cuando ambas búsquedas se encuentran en algún punto intermedio. Pero ¿cómo se realiza la búsqueda hacia atrás? Se definen los predecesores de un nodo n como todos aquellos nodos cuyo sucesor es n. La búsqueda hacia atrás implica la sucesiva generación de predecesores a partir del nodo objetivo. Si todos los operadores son reversibles, los conjuntos de predecesor y sucesor son idénticos; en algunos problemas, sin embargo, el cálculo de los predecesores puede resultar muy difícil, por ejemplo en el caso del ajedrez, si partimos desde el nodo objetivo jaque mate, ¿Cómo podemos regresar al estado anterior?, esto es muy difícil ya que existen muchísimos estados que pueden preceder a un jaque mate.
Imagen:Bidireccional.JPG
¿Qué capacidad tiene?
Este algoritmo tiene una gran ventaja sobre los demás en el tiempo de solución, debido a que divide la búsqueda en 2 tramos, por lo que la búsqueda en el peor de los casos tomaría .
¿Qué limitaciones tiene?
Tiene la limitación de que un árbol se debe mantener siempre en memoria, es decir que ocupa memoria durante todo el tiempo que tarde la búsqueda.
¿Cuál es su complejidad?
Su complejidad en tiempo es O(bd/2), el procedimiento que prueba la intersección de las fronteras de ambas búsquedas se efectúa en un tiempo constante. Para que las 2 búsquedas se encuentren en algún momento, los nodos de al menos uno de los árboles deberán permanecer en memoria. Es decir, la complejidad espacial en la búsqueda bidireccional es O(bd/2).
¿Cómo se podría mejorar este algoritmo?
Este algoritmo es bastante complejo, bastante optimo y completo, por lo que consideramos que mejorarlo sería una tarea ardua y complicada.
Algoritmo de Búsqueda de Profundidad Limitada
Pablo Jaramillo
Juan Pablo Sigcho
Para evitar caer en caminos de profunidad muy grande, a la mayoría de los algortimos que usan depth-first se les impone un límite de profundidad máxima. Si se sabe la profundidad de alguna meta, el algoritmo puede ser completo, pero sigue sin ser óptimo. Si la profunidad es , se tarda O(b^l) y ocupa O(b.l) . Cuando se tienen grafos altamente conectados hay que tener cuidado con el concepto de profundidad (una más que el padre menos profundo). Por lo que en este caso, se tienen que analizar todos los padres, lo cual implica requerimientos adicionales de memoria. En la práctica se puede tomar solo la profundidad del padre que lo generó haciendo una estrategia LIFO más ``pura
Función BÚSQUEDA-PROFUNDIDAD-LIMITADA (problema, límite) devuelve una solución o fallo/corte
devolver BPL-RECURSIVO(HACER-NODO(ESTADO-INICIAL[problema]), problema, límite)
función BPL-RECURSIVO(nodo, problema, límite) devuelve una solución o fallo/corte
ocurrió un corte --> falso
si TEST-OBJETIVO[problema] (ESTADO[nodo]) entonces devolver SOLUCIÓN (nodo)
en caso contrario si PROFUNDIDAD[nodo] = límite entonces devolver corte
en caso contrario para cada sucesor en EXPANDIR(nodo, problema) hacer
resultado BPL-RECURSIVO(sucesor, problema, límite)
si resultado = corte entonces ocurrió un corte --> verdadero
en otro caso si resultado ≠ fallo entonces devolver resultado
si ocurrió un corte? entonces devolver corte en caso contrario devolver fallo
Explicar el algoritmo
El algoritmo optimiza la búsqueda de información basándose en el algoritmo de búsqueda primero en profundidad, al igual que este lo que hace es realizar un recorrido por un árbol binario comenzando siempre por el nodo sucesor izquierdo de la cabeza de dicho árbol, conforme continúe la búsqueda seguirá descendiendo de nodo siempre enfilándose por dicha dirección hasta que llegue al límite establecido una vez que llegue a este lo que hará será devolver una bandera para confirmar si se ha encontrado el dato que se buscaba y si no se la encontrado, al ser recursivo el algoritmo, la búsqueda continuara por aquellos nodos que fueron obviados y seguirá hasta llegar al inicio de la búsqueda.
Poder del algoritmo
Este algoritmo es mucho más rápido y eficiente que aquel en que se basa puesto que permite bajo la observación del usuario establecer un límite para el mismo recortando por así decirlo de cierta manera el campo de búsqueda del mismo logrando así una búsqueda mucho más rápida y precisa, así mismo también se podría establecer (mediante observación por supuesto) un diámetro del espacio de estados que no es más que el límite de profundidad más preciso u óptimo para realizar la búsqueda en profundidad, pero como ya se aclaró anteriormente dicho límite de profundidad sólo podrá ser calculado una vez que se haya resuelto el problema o por lo menos realizado un recorrido previo por el mismo.
Limitaciones del algoritmo
El inconveniente de este algoritmo es que al momento de asignarle un límite para su búsqueda puede darse dos posibles fracasos: Valor de fracaso en el caso de que no haya ninguna solución Valor de corte en el caso de que no haya ninguna solución dentro del límite establecido El límite que se la daría a la búsqueda tiene que ser por así decirlo bastante equilibrada puesto que si es muy pequeña (en comparación a la profundidad del árbol) el resultado no será muy confiable y si es muy grande el tiempo de búsqueda del mismo será demasiado largo.
Optimización del algoritmo
El algoritmo podría ser mejorado pero solo en ciertas circunstancias como en el caso de un árbol binario puesto que dentro del mismo los nodos estarían ordenados secuencialmente por lo que dentro del algoritmo se podría colocar un proceso en el cual al empezar el recorrido en el nodo cabeza se pregunte si el elemento buscado es menor o mayor a dicho nodo cabeza para así restringir aún más la búsqueda del elemento reduciendo el tiempo de respuesta de la misma, pero como ya se dijo solo funcionaría dentro de árboles que se encuentren previamente ordenados.
== Busqueda Primero en Profundidad con Profundidad Iterativa ==
Explicación de cómo funciona el algoritmo
La búsqueda con profundidad iterativa combina la busqueda primero en profundidad con la busqueda primero en anchura. Encuentra el mejor límite de profundidad, ésto se hace aumentando el límite (primero 0, después 1, después 2, etc)hasta que encontramos un objetivo.
Poder del algoritmo
La profundidad iterativa es el método de búsqueda no informada preferido cuando hay un espacio grande de búsqueda y no se conoce la profundidad de la solución. La búsqueda con profundidad iterativa es mas rápida que la búsqueda primero en anchura. Más importante aún es el hecho de que la búsqueda con profundidad iterativa permite terminar la búsqueda en cualquier momento sin consecuencias nefastas.
Limitaciones del algoritmo
Ésta búsqueda deja de ser óptima cuando el nodo objetivo se encuentra a una profundidad (d) muy grande, ésto segun la ecuación de los nodos generados:
N(BPI)=(d)b+(d-1)b^2+...+(1)b^d
Ésto nos indica que el numero de nodos generados es grande, por tanto consume recursos de memoria.
Mejoras
Por cada nueva iteración evitar analizar nuevamente los nodos ya analizados en iteraciones anteriores.
Ejemplo:
Por ejemplo, con un factor de ramificación de 10 y con profundidad 5, los nodos expandidos serían:
1 + 10 + 100 + ... + 100,000 = 111,111,
con profundidad iterativa son:
(d + 1)1 + (d)b + (d-1)db^2 + ... + 1*b^d = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
approx 11% más de nodos.
Integrantes:
* Santiago Ortega
* Juan Pablo Ordoñez
BUSQUEDA COSTO UNIFORME V1
INTEGRANTES:
- Yesenia Carolina Pineda C.
- Adriana Belén Macas E.
EJEMPLO
Imagen:BUSQUEDA.JPG
Se genera el nodo inicial (S), el cual tiene ruta hacía A, B y C, la ruta de menos costo es A, por ese motivo es la que se toma y se expande SAG que tiene un costo total de 11, observe que G ya es una solución, pero se deja en una lista de espera, para verificar si hay otra ruta que produzca un costo menor en ese caso SBG que tiene un costo menor que la anterior y menor que la que queda, por ese motivo esa es la solución.
1) Explicación de cómo funciona el Algoritmo Búsqueda de Costo Uniforme
El algoritmo de Búsqueda de Costo Uniforme está dirigido por los costos de los caminos, es decir, realiza la búsqueda por los nodos que tienen el costo más pequeño para llegar al nodo objetivo, en el caso que todos los costos sean iguales se habla de una búsqueda primero en anchura.
2) Características del Algoritmo
El costo de un camino siempre aumenta cuando vamos por él.
Esta dirigido por los costos de los caminos más que por las profundidades.
C* es el costo de la solución óptima.
3) Limitaciones del Algoritmo
Es que explora los árboles grandes en pequeños pasos antes de explorar caminos que implican pasos grandes y que pueden ser útiles.
4) Mejoras
Una de las mejoras que implementaríamos en nuestro algoritmo es que cuando realice una búsqueda y los costos sean iguales no haga lo que hace el algoritmo primero en anchura ya que hay un desperdicio de recurso y tiempo, porque recorre el algoritmo en anchura pudiendo saltar algunos pasos.
|
