Algoritmos De Búsqueda

25 10 2007

Algoritmo A* De BúsquedaMap

El algoritmo A* es usualmente utilizado en los problemas para encontrar la mejor ruta o camino, lo que realiza el algoritmo es construir todas las rutas desde un punto inicial hasta encontrar alguna que llegue al nodo final o meta. De éste modo solamente construye aquellas rutas que son candidatas a formar una solución o camino desde el inicio hasta el nodo final.


Para poder determinar que rutas son las que tienen mayor probabilidad de llegar al nodo meta, el algoritmo utiliza una heurística basada en la distancia de cualquier punto dado hacía la meta. Donde se diferencia el algoritmo A* de otros algoritmos avaros de “best-first search” es el hecho de que va tomando en cuenta la distancia que ya ha recorrido hasta el momento, haciendo de este modo una respuesta mucho más completa y óptima.

A* es una combinación entre los algoritmos de búsqueda de anchura con algoritmos de profundidad, esto debido a la función que utiliza f(n)= g(n)+h(n), dónde h(n) [que tiende primero a profundidad] representa el valor heurístico del nodo a evaluar y g(n) [que tiende a primero en anchura] representa el costo real del camino recorrido para poder llegar al nodo. Lo anterior lo posibilita a cambiar de camino de búsqueda cuando se encuentra un camino que pareciera ser más óptimo.
Los usos que se le pueden dar a éste algoritmo son el de trazar las rutas para llegar de una ciudad a otra, algo como lo que tiene la Secretaría de Comunicaciones y Transportes para trazar la ruta de una ciudad a otra sacando el menor costo y recorrido posible. La aplicación se llama “Traza Tú Ruta”
.

Algoritmo “Best-First-Search”
Éste algoritmo es una optimización de “breadth-first search” y lo mejora al expandir el nodo más prometedor a través de alguna regla dada. Lo que intenta realizar el algoritmo es estimar el porcentaje de probabilidad de que el nodo “n” sea la mejor opción al utilizar una heurística de evaluación de una función f(n), que depende mayormente en la descripción de “n”, es decir en la habilidad para poder describir la meta y la información que se conoce hasta el punto en el que el algoritmo se encuentra así como cualquier otra información que sea relevante para el problema.


Así el algoritmo busca predecir que tan cercano a una solución es un camino dado, esto lo realiza extendiendo los caminos que se encuentran más cercanos a dicha solución primero, el modo específico de búsqueda se conoce como “greedy best-first search”. La implementación más eficiente para la selección del mejor candidato por extensión es a través de una cola de prioridad.
domino
Creo que uno de los mejores uso que se le puede dar a éste algoritmo es la teoría de juego. Podemos ver claramente como la computadora va a ser capaz de ir seleccionando “la mejor opción hasta el momento” para ganar, o ir prediciendo cuales son los movimiento que podrán seguirle a cierta tirada.


Aunque debemos de tener en cuenta que no podrá ser aplicable para todos los juegos puesto que por ejemplo en el ajedrez simplemente para el 4to movimiento el número de posibles jugadas o movimientos es de 9,100,000, y este es un número que va aumentando exponencialmente, llegando a un total posible en el orden de los veinte septillones, es decir 20×1042.

Simulated Annealing
Éste es un algoritmo de probabilidad que busca y localiza la mejor aproximación posible para el resultado óptimo de una función dada dentro de un universo de búsqueda amplio. Se utiliza generalmente cuando el campo de búsqueda es discreto, por ejemplo los tours que visitan determinadas ciudades.


Su nombre y la idea principal provienen del método en la metalurgia de recocido, que conllevan el calentamiento y enfriamiento controlado de los materiales para elevar el número de cristales y reducir sus defectos.recocido
En éste algoritmo cada punto “s” del universo de búsqueda es comparado con el estado de algún sistema físico, y la función que se utiliza E(s) es interpretada como la energía interna del sistema en ese estado dado. La meta es llevar al sistema de un punto aleatorio inicial a un estado en el cual éste tenga la menor cantidad posible de energía.


En cada paso el algoritmo considera a algunos de los vecinos del actual estado “s”, y probabilísticamente calcula y decide si debe de moverse a alguno de ellos. Las probabilidades son escogidas de tal forma que el sistema tienda a tener menor cantidad de energía. Éste paso es repetido uno número de iteraciones determinadas por el programador o hasta que se alcance un estado de energía que sea aceptable para el sistema.

Para poder aplicar éste algoritmo a un problema en específico es necesario que uno le proporcione los siguientes parámetros: el universo de estados, la meta en energía de la función E(s), la forma de generar a los candidatos a través de una función vecinos(), el nivel de aceptación probabilística en función P() y el itinerario de recocido temp(). Todos estos parámetros tienen un impacto significativo en la eficiencia del método. Lamentablemente no existe un modo de determinar que opciones de valores serán los mejores para cada problema, y no hay forma de encontrarlos para u n problema en específico.

Su uso puede ser para cualquier problema de búsqueda de mejor camino, o mejor opción siempre y cuando se puede generar los parámetros arriba mencionados que se necesitan para el funcionamiento del mismo.

Hill Climbing
Éste algoritmo pertenece a los de búsqueda local, y su implementación es bastante sencilla lo cual lo hace muchas veces la opción favorita por muchos a pesar de que existan algoritmos que puedan dar mejores y más exactos resultados.

El algoritmo puede ser utilizado en la resolución de problemas que tienen varias posibles soluciones pero en las cuales algunas son mejores que otras. El algoritmo se comienza con una de estas soluciones escogidas al azar. Y poco a poco va buscando una mejora a dicha solución, por más mínima que ésta sea. Hasta que el algoritmo llega a un punto en el que ya no puede encontrar ninguna mejora a la solución y es entonces cuando termina. Por lo general cuando llega a éste punto la solución es bastante cercana a la más optima, aunque nunca se puede garantizar que llegue a la óptima.

Lo que realiza el algoritmo es el buscar maximizar o minimizar una función f(x) dada, donde “x” se refiere a estados discretos del problema. Estos estados usualmente son representados por vértices en una gráfica. Así el algoritmo va a seguir una gráfica de vértice a vértice, siempre aumentando o disminuyendo localmente el valor de la función hasta encontrar un máximo o mínimo local.

Ant Colony Optimization
Es un algoritmo que utiliza probabilidad para solucionar problemas computacionales a través de la búsqueda de los mejores caminos en un grafo. Está inspirado en el modo en como las hormigas pueden encontrar el mejor camino hacía su colonia desde un punto dado.

Básicamente lo que éste algoritmo hace es tener una o varías hormigas dentro del grafo que van a ir recorriendo dicho grafo a través de diferentes caminos y/o decisiones, y van a ir depositando un valor de “feromona” en los caminos que utilizen para realzar la importancia del mismo. Cada feromona en el camino va a ir disminuyendo un porcentaje que el programador decide, esto es para que si éste durante un dado periodo no es visitado pierda la importancia.

De éste modo el algoritmo va a ir encontrando un camino óptimo para poder visitar todos los nodos del algoritmo de una manera sencilla (no se puede asegurar que la más óptima). El algoritmo se corre tantas veces como el programador lo requiera o hasta que no exista alteraciones sustanciales en los valores del camino encontrado, lo cual indica que el algoritmo a llegado a un punto estable.

Éste algoritmo se puede utilizar para encontrar las mejores (no se sabe si óptimas) rutas para visitar cierto “universo” de ciudades o lugares dados, o como lo mencioné en un principio cualquier problema computacional que pueda ser representado a través de grafos.


Acciones

Information

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s




A %d blogueros les gusta esto: