Búsqueda a ciegas o de generación y prueba:
Se le llama así, porque no tienen información suficiente que les guié a
hacia el estado final o objetivo.
por lo tanto realizara una búsqueda, evaluando cada uno de los
estados hasta encontrar el estado deseado.
Se puede correr con la suerte de que el primer elemento
evaluado sea el objetivo, Pero también cabe la posibilidad de que
sea el ultimo de una gran lista de elementos.
Este tipo de búsqueda tiene dos variantes representativas:
Búsqueda en amplitud y búsqueda en profundidad.
El método búsqueda en profundidad
Este método consiste en desplazarse por cada una de las ramas
de nuestro árbol o grafo, hasta llegar o encontrar
nuestro estado final. habitualmente se le debe de dar un orden para
orientar la búsqueda.
Para un árbol, puede ser de derecha a izquierda o viceversa,
para un grafo puede ir de un sentido horario o anti-horario
El método de búsqueda por amplitud
A diferencia del anterior, este método en lugar de desplazarse
por las ramas, evalúa cada estado por niveles.
un nivel esta compuesto por los sucesores del estado
del nivel anterior, a excepción del nodo inicial
que no tiene ningún antecesor.
Búsquedas Heurísticas:
Son técnicas que permiten mejorar El desempeño de la
búsqueda.
haciéndose valer de estrategias para limitar el espacio.
están se plantean con el uso de una función heurística, a la cual
utilizara información adicional, ya sea de costos, tiempos,
distancia, etc. para llegar de un estado al otro o aun
objetivo.
En este método no se garantizan soluciones optimas,
pero si se pueden considerar lo bastante aceptables tal como
lo podría ser un ser humano.
Busque por Escalada simple:
Para este y otros métodos de búsqueda heurísticas, se utiliza
una tabla con la cual se ve la relación de costos que hay
de un estado a otro, esto nos ayuda a elegir una ruta dependiendo
de lo que queramos mejorar, ya sea maximizar o minimizar una
variable.
en este método se espante a un modo, a un estado dependiendo.
si esta mas cercano a satisfacer la función objetivo.
Para esto el estado actual realiza las evaluaciones del primer
nodo sucesor, en el sentido que quiera asignarle.
en este caso tiene que ser anti-horario. si este le demuestra que es una
mejor opción para llegar al objetivo aunque en realidad no lo sea y
nos lleva a un callejón sin salida, sera elegido como un nodo
actual.
De lo contrario se elegiría otro sucesor que haya sido generado.
y esto se repite hasta que llegue al objetivo.
o la desventaja es que si no encuentra una mejor ruta
en sus sucesores, se encontrara atrapado en un callejón
sin salida, terminando sin éxito la búsqueda.
Búsqueda Por Máxima pendiente:
Se parece al método de la escalada simple, pero con la diferencia
de que todos los estados sucesores del estado actual, serán
evaluados y se elegirá al que tenga una mejor valoración, para
convertirse en el nuevo estado actual. Si es nodo final
terminara la búsqueda, de lo contrario se repetirá el siglo.
este método es mas eficiente ya que permite que haya mas
diversidad a la hora de evaluar a mas estados.
Ademas, de que reduce el tiempo de búsqueda.
pero aun tiene la desventaja de que la nueva ronda de estados o
sucesores sus resultados no sean tan satisfactorios, por lo tanto
puede quedar atorado en un callejón sin salida.
Búsqueda por primero mejor:
Conjunta las técnicas de búsqueda en profundidad que es expandir una rama hasta su máxima
longitud, Y el de la búsqueda en amplitud, que lo hará saltar de rama en rama, para evitar callejón
sin salida. este método genera a los sucesores del estado actual y los deja en una lista de estados
abiertos o sin revisar.
Elegirá al estad mas prometedor y sera evaluado.
Si es estado final, terminara la búsqueda. sino, este pasara a ser el estado actual y se quitara de las lista
de los estados abiertos. Si tiene sucesores, los agregara a las listas de los estados abiertos, En caso de que este sea un estado terminal se marcara como revisado y se elegirá al mas prometedor de la lista de los estados abiertos. y se repetirá hasta encontrar el estado final.
Bueno pues en la actividad se pedía describir a profundidad cual era el método que nos interesaba,
y yo describir los que encontré respectivamente.
Pero a Decir verdad, yo prefiero los heurísticos, ya que estos se pueden equivocar, al igual que un ser humano.
Referencias:
http://ia2010fisig1.netne.net/docs/AIA00_04.ppt
http://www.oocities.org/ohcop/ayuda33.html
No hay comentarios:
Publicar un comentario