Hill Climbing Search

Hill Climbing Search
Método:
La escalada de la búsqueda se basa en primer lugar la búsqueda de profundidad. Una heurística es usada para mejorar la eficiencia de búsqueda. En cada paso, se puede estimar si una elección es probable que sea mejor que otro y para las decisiones en consecuencia.

Hill-Escalada Metodología
1. Construir una solución sub-óptima que cumpla con las restricciones del
Problema.
2. Tome la solución y hacer una mejora en ella
3. Repetidamente mejorar la solución hasta que no mejoras más son necesarias / posibles

Demostración:
Animación de ondas de choque (36k) - ver la escalada de la búsqueda
Algoritmo:
Algoritmo 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.
En estos debates vamos a suponer que estamos tratando de maximizar una función. Es decir, estamos tratando de encontrar un punto en el espacio de búsqueda que es mejor que todos los demás. Y por "mejor" queremos decir que la evaluación es más alta. También podríamos decir que la solución es de mejor calidad que todos los demás.
No hay razón para que no se debe tratar de minimizar una función, pero lo hace para facilitar la lectura, si asumimos que siempre están tratando de maximizar la función en lugar de mantenimiento de tener que recordar de lo que podría minimizar o maximizar.
La idea detrás de la escalada es el siguiente.
1. Elija un punto al azar en el espacio de búsqueda.
2. Considere todos los vecinos de la situación actual.
3. Elija el vecino con la mejor calidad y pasar a ese estado.
4. Repita los pasos 2 a 4 hasta que todos los estados vecinos son de menor calidad.
5. Devuelve el estado actual como el estado de disolución.

También puede presentar este algoritmo de la siguiente manera (es tomado del libro AIMA (Russell, 1995) y sigue las convenciones que hemos estado utilizando en este curso cuando se mira en las búsquedas ciegas y heurística).
Función en escalada (Problema) devuelve un estado de solución
Entradas: Problema, problema
Las variables locales: Actual, un nodo
A continuación, un nodo
Actual = MAKE-NODO (INICIAL-state [problema])
Bucle do
Siguiente = un sucesor de mayor valor de la actual
Si VALOR [Siguiente]
Actual = Siguiente
Fin
Debe tener en cuenta que este algoritmo no mantiene un árbol de búsqueda. Sólo se devuelve una solución final.
Además, si dos vecinos tienen la misma evaluación y que son a la vez la mejor calidad, entonces el algoritmo se elige entre ellos al azar.
Evaluación

Las desventajas de esta técnica puede visualizarse considerando la analogía hillclimbing:

Local Máxima: Si empieza escalador comienza a los pies, pasa mucho tiempo de subir a las cumbres de las estribaciones y estar decepcionado de que no son el objetivo.

Mesetas: Si comienza en una llanura plana en algún lugar va a vagar sin rumbo por comparación locales no determinará la mejor dirección.

Crestas: si se encuentra encima de una loma de suave pendiente, la mayoría se mueve lo llevará hacia abajo, pero no se halla en una cumbre.

Se trata de una búsqueda completa.

Costo de la búsqueda
Con esta búsqueda variable como esta es imposible determinar lo que, en su caso, la mejora de la eficiencia se hará. Una naturaleza heurística desafía dicha evaluación.

No óptimas
Este algoritmo no necesariamente encontrará la ruta más eficiente a través del espacio de estados.
Siguiente: La búsqueda del haz
Método informado: Volver.

INTEGRANTES:
ABRAHAM CHAVEZ MALFAVÓN
JESÚS ALEJANDRO GUZMÁN CHÁVEZ
ANA KAREN RIOS ROMERO
KEREN BERENICE SANTOS AGUILAR
DIANA KARINA HERNANDEZ SANTIAGO.

-- A* -- (A asterisco o A estrella)

Integrantes del equipo:

Norma Angélica Villatoro Pérez
Deydre Itzel Molina Espinosa
Alexander Vázquez Sarmiento
Everardo Martínez Vázquez
José de Jesús Sánchez de la Cruz
Josué Caleb Molina Zepeda

**************************************************************************************

Búsqueda por el método algorítmico A*

El algoritmo de búsqueda A*(pronunciado “A asterisco” o “A estrella”) se clasifica dentro de los algoritmos de búsqueda en  grafos. Presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bertram Raphael, el algoritmo A* encuentra, siempre y cuando se cumplan unas determinadas condiciones, el camino de menor coste entre un nodo origen y uno objetivo.

Él método busca el camino en un grafo de un vértice inicial hasta un vértice final. Él es la combinación de aproximaciones heurísticas como del algoritmo Best-first  Search.

Su aplicación va desde aplicativos para encontrar rutas de desplazamiento entre localidades la resolución de problemas, como la resolución de uno quiebra-cabezas. Él es muy usado en juegos.

Método.

La búsqueda del algoritmo  A* busca mejorar la ramificación y acotación utilizando la programación dinámica. La heurística busca el aumento  en la eficiencia en la búsqueda.

Para que el algoritmo A * pueda  encontrar la ruta más óptima y admisible debe usarse la heurística

Demostración

Animación onda de choque (k) - ver una búsqueda A *

Algoritmo

1.- formar una cola de Q  caminos parciales. Dejar  que la inicial Q consiste en la de costo-cero,  a cero-paso por camino desde la raíz a ninguna parte.

2.-Hasta que Q está vacío o el objetivo se ha llegado a determinar si el primer camino

  En Q llega a la meta.

     a. Si lo hace, no hacer nada

     b. si no:

              2b1. Retire el primer camino de Q

           2b2. Formulario de nuevos caminos mediante la ampliación de un paso.

           2b3. Añadir los nuevos caminos a la Q

           2b4.If dos o más caminos llegan (o contener) un nodo común,

                  Eliminar todos menos el camino que llega al nodo común con

                  el más bajo costo. (Programación dinámica)

           2B5. clase Q por la suma del costo real de la medida heurística (la

          Estimación de límite inferior de los costes restantes.)

3.- Si el objetivo es alcanzado, se llega al el éxito, si no se obtiene  el fracaso.

Aplicación de 2B4  REQUIERE  una lista separada de los nodos que han sido

Ampliado y los costos más bajos asociados con llegar a ellos.

Evaluación.

La búsqueda es completada. Si todos los nodos  son abiertos y si el resultado es encontrado, si esto sucede es finalizado.

Costo de la búsqueda

La eficiencia de este tipo de búsqueda es muy difícil de precisar. Por lo tanto no puede ser representado con una expresión matemática

Óptima

Este algoritmo encontrará definitivamente la ruta más eficiente a través del espacio del Estado.

Siguiente: redondear al alza

Atrás: Marca y atado con subestima

IMPLEMENTACION PSEUDOCODIGO

Tratar punto

.:= . // coste del camino hasta . caso . = . perteneciente a () si g(.) < g(.) entonces // (-----) // nos quedamos con el camino de menor coste .:= MEJORNODO actualizar g(.) y f'(.) propagar g a . de . eliminar . añadir . a ._MEJORNODO caso . = . perteneciente a )-----( si g(.) < g(.) entonces // nos quedamos con el camino de menor coste .:= MEJORNODO actualizar g(.) y f'(.) eliminar . añadir . a ._MEJORNODO caso . no estaba en ).( ni (.) añadir . a ).( añadir . a ._MEJORNODO f'(.) := g(.) + h'(.)

Implementación en pseudocódigo

ABIERTOS := [INICIAL] //inicialización CERRADOS := [] f'(INICIAL) := h'(INICIAL) repetir si ABIERTOS = [] entonces FALLO si no // quedan nodos extraer MEJORNODO de ABIERTOS con f' mí­nima // cola de prioridad mover MEJORNODO de ABIERTOS a CERRADOS si MEJORNODO contiene estado_objetivo entonces SOLUCION_ENCONTRADA := TRUE si no generar SUCESORES de MEJORNODO para cada SUCESOR hacer TRATAR_SUCESOR hasta SOLUCION_ENCONTRADA o FALLO

Tratar_Sucesor

SUCESOR.ANTERIOR := VIEJO // coste del camino hasta SUCESOR caso SUCESOR = VIEJO perteneciente a CERRADOS si g(SUCESOR) < g(VIEJO) entonces // (no si monotoní­a) // nos quedamos con el camino de menor coste VIEJO.ANTERIOR := MEJORNODO actualizar g(VIEJO) y f'(VIEJO) propagar g a sucesores de VIEJO eliminar SUCESOR añadir VIEJO a SUCESORES_MEJORNODO caso SUCESOR = VIEJO perteneciente a ABIERTOS si g(SUCESOR) < g(VIEJO) entonces // nos quedamos con el camino de menor coste VIEJO.ANTERIOR := MEJORNODO actualizar g(VIEJO) y f'(VIEJO) eliminar SUCESOR añadir VIEJO a SUCESORES_MEJORNODO caso SUCESOR no estaba en ABIERTOS ni CERRADOS añadir SUCESOR a ABIERTOS añadir SUCESOR a SUCESORES_MEJORNODO f'(SUCESOR) := g(SUCESOR) + h'(SUCESOR)

 **************************************************************************************

Beam Search (BS)

El algoritmo de Beam Search (BS) es un derivado de un branch-and-bound que utiliza la búsqueda de primero en anchura, e incorpora una heurística para escoger en cada nivel solo los mejores β nodos. Los mejores nodos se guarnan en lo que llama el bear, y β suele denominarse bear width. Este método sacrifica completitud a cambio de un enfoque heurístico muy efectivo.

Los mejores β nodos son seleccionador por funciones de evaluación de un paso, las cuales estiman el costo de expandir la solución actual. Note se que los nodos en el vean representan soluciones parciales (evita el problema de la explosión combinatoria  de búsqueda en amplitud por primera ez por ampliar solo los β nodos más prometedores en cada nivel. Una heurística se utiliza para predecir cuales nodos son propensos a ser el mas cerca a la meta o goal).

Algoritmo 1

1. Formar una cola de un elemento Q que consiste en el nodo raíz

2. Hasta que Q está vacío o el objetivo se ha llegado a determinar si alguno de los elementos de Q es el objetivo.

a. Si es así, no hacen nada

b. Si no es así, quitar los elementos de Q y añadir a sus hijos, en su caso, la parte posterior de Q.

c. Ordenar Q por heurística.

d. Quite todos, pero los primeros p nodos de Q

3. Si el objetivo es alcanzado, éxito, si no fracaso

Algoritmo 2

COLA <- la ruta solo contiene al padre;

While COLA no está vacía and nodo destino no encontrado

do	/ Borrar todos las turas contenidas en la COLA; | Crear nuevas rutas de todos sus hijos; | Ordena nueva lista de menor a mayor según los | valores heurística del último nodo; \ Añadir las nuevas “beam” rutas al final de la COLA;

If nodo destino encontrado

                Then return (éxito);

                Else return (fracaso);

Evaluación

Si hay más de un nodo objetivo, siempre coger el más cercano al nodo en generaciones. Esto tiene un valor si el árbol está desequilibrado, pero inútil si los nodos meta se encuentran en niveles similares.

Esta es una búsqueda incompleta. Existe el peligro de que un objetivo encontrar la ruta será removido de Q antes de que pueda ser explorado. Esto puede llevar a no encontrar ningún objetivo en absoluto.

Costo de la búsqueda

En cada nivel sólo hay p nodos almacenados. Esto evita el problema de la explosión exponencial de la búsqueda en amplitud en primer lugar.

Tiempo de eficiencia es del orden de bd. Esto es muy eficiente.

Espacio La eficiencia es también de orden bd. Esto es muy eficiente.

No óptimas

Este algoritmo no necesariamente encontrará la ruta más eficiente a través del espacio de estados.

No tiene retroceso.

Exhaustividad: NO asegura encontrar una ruta si esta existe.

Tiempo: Es una constante O(beam*m) si existe una soluci´on o O(beam*d) si la solución no la encuentra.

Memoria: Es una constante O(beam)



Integrantes de equipo:

Alma Georgina De León De León

Francisco Josué Gordillo Mayor

Alermo Hernández Valenzuela

Ever López Martínez

José Giovanny Solís Niño

 

Breadth first search

Breadth  first search (primera extensión de búsqueda).

Método

Esto busca el nodo objetivo entre todos los nodos de una generación particular, antes de expandirse aún más.

Algoritmo
1. Formar una cola de un elemento de Q, que consiste en el nodo raíz
2. Hasta que Q es vacío o el objetivo se ha alcanzado BBC, determina si el primer elemento de Q es el objetivo. si lo es, no hacer nada b. si no es así, eliminar el primer elemento de Q y añadir los niños del primer elemento, si lo tiene a la parte posterior P.
3. Si el objetivo es alcanzado, el éxito, el fracaso más.

Evaluación
si hay más de un nodo objetivo, siempre coger el más cercano al nodo en la generación. esto es de valor si los tres si no balanceada, pero inútil si los nodos meta se encuentran en niveles similares.
Esto es una búsqueda completa.

Costo de la búsqueda
considerar un factor de tres con ramificación b. a una profundidad d, habrá nodos b. esto provoca una explosión exponencial de tamaño del árbol.

Aprovechamiento del tiempo es de orden b. esto es muy ineficiente.

Espacio La eficiencia es también de orden b. esto es muy ineficiente.

No óptimas
este algoritmo no necesariamente encontrará la ruta más eficiente a través del espacio de estados.

Escuchar

Leer fonéticamente

Diccionario - Ver diccionario detallado

1.prefijo

1.no-

2.in-

3.des-

Best First Search (Búsqueda "Mejor el Primero")

Best First Search

Esta búsqueda es basada libremente en el Dip Best search nuevamente el método heurístico es usado para mejorar la búsqueda eficientemente cada paso de la expansión de los nodos es resumido desde el primer nodos hasta el ultimo, no importa en donde esta en el árbol

ALGORITMO

1.- Forma a un elemento constante Q consistente desde el modo raíz.

2.-  Hasta que Q esté vacía o el objetivo haya sido alcanzado, se determina si el primer elemento en Q es el objetivo.

• a) Si lo es hacemos nada.

• b) Si no lo es, remover el elemento de Q y agregar el primer elemento hijo de Q.

• c) Ordenar Q  estimando la distancia.

4.- Si el objetivo es alcanzado, felicidades. Si no, fracasaste.

EVALUACIÓN.

Este es una búsqueda completa.

Costo de la Búsqueda.

Con una variable de búsqueda, ya que es imposible de terminar lo que, en su caso mejorará la eficacia de la búsqueda.

Una naturaleza heurística desafía dicha evaluación.

NO ÓPTIMO

Este algoritmo no necesariamente encontrara la ruta más eficiente a través del estado del espacio, encontrando la mejor ruta es el tema de la sig. Sección.

EJEMPLO 

Referencias:
www.ii.uam.es/~fdiez/docencia/.../busqueda-con-informacion.ppt

Integrantes del equipo

Caballero Hernández Alí
Cañaveral Cruz Àngel Andrès
Dominguez Pérez Didier Uriel
Gonzalez Sánchez Victor Manuel
Mendez Cruz Daniel
Ortega Solis Artemio
Vázquez Sánchez Gladis

Depth first search (Primera profundidad de la búsqueda)

Definición:

Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.

Para recorrer los medios para visitar los vértices en un orden sistemático. Debe estar familiarizado con varios métodos de recorrido de árboles:

    preorden: visitar cada nodo antes de sus hijos.
    postorden: visitar cada nodo después de sus hijos.
    finde (por árboles binarios solamente): subárbol visita a la izquierda, el nodo, subárbol derecho.

Primera profundidad de la búsqueda

La búsqueda en profundidad primero es otra manera de atravesar los gráficos, que está estrechamente relacionado con el recorrido preorden de un árbol. Recordemos que recorrido preorden simplemente visita cada nodo antes de sus hijos. Es muy fácil de programar como una rutina recursiva:
    preorden (nodo v)
    {
    visita (v);
    para cada hijo w de v
        preorden (w);
    }
Para convertir esto en un algoritmo de recorrido gráfico, básicamente reemplazar "niño" por "vecino". Pero para evitar bucles infinitos, sólo quiere visitar una vez cada vértice. Al igual que en BFS podemos utilizar las marcas para hacer un seguimiento de los vértices que ya han sido visitados, y no visitar de nuevo. Además, al igual que en BFS, podemos utilizar esta búsqueda de construir un árbol de expansión con ciertas propiedades útiles.
    dfs (vértice v)
    {
    visita (v);
    para cada vecino w de v
        si w es no visitados
        {
        DFS (w);
        añadir vw borde de árbol T
        }
    }
El general algoritmo de profundidad primera búsqueda simplemente inicializa una serie de marcadores para que podamos saber qué vértices son visitados, elige un vértice de partida x, inicializa árbol T a x, y pide dfs (x). Al igual que en la amplitud de la búsqueda en primer lugar, si un vértice tiene varios vecinos, sería igualmente correcto para ir a través de ellos en cualquier orden. No se limitó a decir "para cada vecino no visitados de v" porque es muy importante para retrasar la prueba para saber si un vértice es visitado hasta las llamadas recursivas para los vecinos anteriores terminado.
La prueba de que esto produce un árbol de expansión (el árbol de profundidad primera búsqueda) es esencialmente el mismo que el de BFS, así que no voy a repetir. Sin embargo, mientras el árbol BFS es típicamente "corto y espeso", el árbol DFS suele ser "largo y fibroso".

Al igual que hicimos para BFS, podemos utilizar DFS para clasificar las aristas de G en tipos. Cualquiera de un vw borde está en el árbol DFS sí mismo, v es un antecesor de w, o w es un ancestro de v. (Estos dos últimos casos deben ser considerados como un solo tipo, ya que sólo difieren en qué orden nos fijamos en los vértices pulgadas) Lo que esto significa es que si v y w son diferentes en subárboles de v, no podemos tener una ventaja de v a w. Esto es porque si por ejemplo un borde existido y (dicen) v se visitaron en primer lugar, entonces la única forma que se evite agregar vw al árbol DFS sería si w fueron visitadas durante una de las llamadas recursivas de v, v, pero luego se le un antepasado de w.

Como un ejemplo de por qué esta propiedad puede ser útil, vamos a probar el hecho siguiente: en cualquier grafo G, el G tiene camino de longitud por lo menos k. o G O (kn) bordes.

Prueba: Buscar en la trayectoria más larga en el árbol DFS. Si tiene una longitud de al menos k, hemos terminado. De lo contrario, ya que cada arista conecta un antepasado y un descendiente, podemos limitan el número de aristas, contando el número total de los antepasados de cada descendiente, pero si el camino más largo es más corto que k, tiene cada descendiente en la mayoría de k-1 antepasados. Por lo tanto no puede haber más en los bordes (k-1) n.

Este hecho puede ser utilizado como parte de un algoritmo para encontrar las rutas de largo en G, otro problema isomorfismo subgrafo estrechamente relacionado con el problema del vendedor ambulante. Si k es una constante pequeña (como por ejemplo 5) se pueden encontrar caminos de longitud k en un tiempo lineal (medida en función de n). Sin embargo, medido en función de k, el tiempo es exponencial, lo que no es de extrañar porque este problema está estrechamente relacionado con el problema del vendedor ambulante. Para más información sobre este problema en particular, ver a Michael R. Fellows y Michael A. Langston, "En la búsqueda, de decisiones y la eficiencia de los algoritmos de tiempo polinómico", 21 Symp del ACM. Teoría de la Computación, 1989, pp 501-512.

Relación entre BFS y DFS

Puede que no sea claro en el pseudo-código anterior, pero BFS y DFS están estrechamente relacionados entre sí. (De hecho en la clase he tratado de describir una búsqueda en la que he modificado el "añadir al final de la lista" línea en el pseudocódigo BFS "añadir al principio de la lista", pero el algoritmo de recorrido resultante no era la misma DFS).
Con un poco de cuidado se puede hacer BFS y DFS parecen casi lo mismo que los demás (lo más parecido, por ejemplo, Prim y los algoritmos de Dijkstra son entre sí):

    BFS (G)
    {
    lista L = vacío
    T = árbol vacío
    elegir un vértice de partida x
    búsqueda (x)
    al mismo tiempo (no vacío L)
        quitar el borde (v, w) desde el inicio de la L
        si no w visitado aún
        {
        añadir (v, w) a T
        búsqueda (w)
        }
    }

    DFS (G)
    {
    lista L = vacío
    T = árbol vacío
    elegir un vértice de partida x
    búsqueda (x)
    al mismo tiempo (no vacío L)
        quitar el borde (v, w) del extremo de la L
        si no w visitado aún
        {
        añadir (v, w) a T
        búsqueda (w)
        }
    }

    búsqueda (vértice v)
    {
    visita (v);
    para cada arista (v, w)
        agregar borde (v, w) al final de la L
    }
Ambos algoritmos de búsqueda ahora mantener una lista de los bordes para explorar, la única diferencia entre ambos es que, si bien ambos algoritmos añade elementos al final de L, BFS los elimina desde el principio, lo que resulta en el mantenimiento de la lista como una cola , mientras que DFS las aleja de la final, el mantenimiento de la lista como una pila.
BFS y DFS en grafos dirigidos

Aunque hemos discutido para grafos no dirigidos, las rutinas misma búsqueda de trabajo sin modificar esencialmente para grafos dirigidos. La única diferencia es que cuando la exploración de un vértice v, que sólo quiere ver en los bordes (v, w) de salir de v; ignoramos los bordes que entra a v.
Para grafos dirigidos, también, podemos probar las propiedades de Niza de la BFS y el árbol DFS que ayudan a clasificar a los bordes de la gráfica. Para BFS en grafos dirigidos, cada borde de la gráfica o conecta dos vértices en el mismo nivel, se pone exactamente un nivel, o va a cualquier número de niveles. Para DFS, cada borde o conecta un antepasado a un descendiente, un descendiente de un antepasado, o un nodo a un nodo en un árbol visitado. No es posible obtener "los bordes hacia adelante" que conecta un nodo a un subárbol visitó antes de ese nodo.Vamos a utilizar esta propiedad la próxima vez para comprobar si un grafo dirigido es fuertemente conectados (cada vértice puede llegar a cualquier otro).

Referencia:

http://es.wikipedia.org/wiki/B%C3%BAsqueda_en_profundidad

 http://www.ics.uci.edu/~eppstein/161/960215.html

ICS 161 - Departamento de Información y Ciencias de la Computación - UC Irvine
Última actualización: 07 de mayo de 2004, 15:27:14 CEST