HILL CLIMBING SEARCH

En ciencias de la computación, la escalada es una optimización matemática técnica que pertenece a la familia de búsqueda local. Es un algoritmo iterativo que comienza con una solución arbitraria a un problema, a continuación, intenta encontrar una solución mejor forma incremental de cambiar un solo elemento de la solución. Si el cambio produce una mejor solución, un cambio gradual que se haga a la nueva solución, repetir hasta que no haya más mejoras se pueden encontrar.

Escalada Hill es bueno para encontrar un óptimo local (una buena solución que se encuentra relativamente cerca de la solución inicial), pero no está garantizado para encontrar la mejor solución posible (el óptimo global ) de todas las soluciones posibles (el espacio de búsqueda ).

La relativa simplicidad del algoritmo que hace que una elección popular el primer lugar entre la optimización de algoritmos. Se utiliza ampliamente en la inteligencia artificial , para llegar a un estado final de un nodo de inicio. Elección del siguiente nodo y el nodo de partida se puede variar para dar una lista de algoritmos relacionados. A pesar de algoritmos más avanzados tales como recocido simulado o búsqueda tabú puede dar mejores resultados, en algunas situaciones colina escalada funciona igual de bien. De subida de pendientes a menudo se puede producir un resultado mejor que otros algoritmos cuando la cantidad de tiempo disponible para realizar una búsqueda se limita, por ejemplo con sistemas de tiempo real.


Descripción matemática

Escalada intentos Hill para maximizar (o minimizar) un objetivo de la función , Donde es un vector de valores continuos o discretos.

En cada iteración, la escalada se modifica un solo elemento en y determinar si el cambio mejora el valor de . (Tenga en cuenta que esta diferencia de gradiente de descenso métodos, que modifica todos los valores en en cada iteración de acuerdo a la pendiente de la colina.) Con la escalada, cualquier cambio que mejora la es aceptada, y el proceso continúa hasta que no cambia se pueden encontrar para mejorar el valor de . Entonces se dice que es "óptimo local".

En los espacios vectoriales discretos, cada valor posible para puede ser visualizado como un vértice en un grafo . La escalada seguirá la gráfica de vértice a vértice, siempre a nivel local aumentando (o disminuyendo) el valor de , hasta un máximo local(o mínimo local) X m se alcanza.

Variantes

En colina simple escalada, cuanto más cerca del primer nodo que se elija, mientras que en el ascenso más empinado cerro subir todos los sucesores se comparan y el más cercano a la solución elegida es. Ambas formas de error si no hay ningún nodo más cercano, lo que puede suceder si hay máximos locales en el espacio de búsqueda que no son soluciones. Ascensión colina Steepest escalada es similar al de sesiones de la búsqueda mejor , que trata de todas las extensiones posibles de la ruta actual en lugar de uno solo.

Aleatorios reiniciar la escalada es un meta-algoritmo basado en la parte superior de la escalada algoritmo colina. También es conocida como colina escopeta escalada. Es iterativa se en escalada, cada vez con una condición inicial aleatoria x 0. La mejor m x se mantiene: si una carrera nueva escalada de la colina produce una x m mejor que el estado almacenado, que sustituye el estado almacenado.

Una visualización de una superficie con dos máximos locales. (Sólo uno de ellos es el máximo nivel mundial.) Si un escalador de montaña se inicia en una mala ubicación, puede converger con la máxima más baja.

Un problema con la escalada es que se encuentra sólo máximos locales . A menos que la heurística es convexa, no podrá alcanzar un máximo global. Otros algoritmos de búsqueda local de tratar de superar este problema, tales como colina estocástico escalada , paseos aleatorios y recocido simulado .

Cordilleras y Vida

Las crestas son un reto para los escaladores de montaña que optimizan los espacios continuos. Debido a que los escaladores colina sólo modifica un elemento en el vector a la vez, cada paso se mueve en un eje de dirección-alineados. Si la función objetivo crea una cresta estrecha que sube en un tercer eje alineado a la dirección (o si el objetivo es reducir al mínimo, un estrecho callejón que desciende en dirección del eje no alineados), el escalador de montaña sólo se puede subir a la canto (o bajar por el callejón) por el zig-zag. Si los lados de la cresta (o el callejón) son muy empinadas, el escalador de montaña puede ser obligado a tomar medidas muy pequeñas, ya que en zig-zag hacia una mejor posición. Por lo tanto, es posible que una duración excesiva de tiempo para que pueda subir a la cresta (o bajar por el callejón).

Por el contrario, los métodos de gradiente de descenso puede moverse en cualquier dirección que la cresta o callejón puede ascender o descender. Por lo tanto, el descenso del gradiente es generalmente preferible a la escalada en la función objetivo es diferenciable. Escaladores Hill, sin embargo, tienen la ventaja de no requerir la función objetivo a ser diferenciable, por lo que los escaladores colina puede ser preferible cuando la función objetivo es compleja.

Meseta

Otro problema que a veces ocurre con la escalada es la de una meseta. Una meseta se encuentra en el espacio de búsqueda es plana, o lo suficientemente plana que el valor devuelto por la función de destino se confunde con el valor devuelto de regiones cercanas debido a la precisión utilizada por el equipo que representará a su valor. En tales casos, el escalador monte no se puede ser capaz de determinar en qué dirección se debe intensificar, y puede caminar en una dirección que no conduce a la mejora.



En Pseudocódigo Seria:

Discreta Hill Escalada Espacio Algoritmo

CurrentNode = startNode;
bucle do
L = VECINOS (CurrentNode);
nextEval =-INF;
NextNode = NULL;
para todo x en L
if (EVAL (x) nextEval>)
NextNode = x;
nextEval = EVAL (x);
si nextEval <= EVAL (CurrentNode) / / Nodo de retorno de corriente, ya que no existen vecinos más volver CurrentNode; CurrentNode = NextNode; Hill Espacio continua escalada Algoritmo punto actual initialPoint = / / el vector cero grados de magnitud es común stepSize = initialStepSizes; / / un vector de todos los 1 es común = aceleración someAcceleration / / un valor como 1.2 es común candidatos [0] = aceleración; candidatos [1] = -1 / aceleración; candidatos [2] = 0; candidatos [3] = 1 / aceleración; candidatos [4] = aceleración; bucle do antes = EVAL (punto actual); para cada elemento i en el punto actual se mejor = -1; bestScore =-INF; para j 0-4 / / tratar cada uno de los 5 lugares candidatos punto actual [i] = punto actual [i] + stepSize [i] * candidato [j]; temp = EVAL (punto actual); punto actual [i] = punto actual [i] - stepSize [i] * candidato [j]; si (temperatura> bestScore)
bestScore = temp;
mejor = j;
si el candidato [mejor] no es 0
punto actual [i] = punto actual [i] + stepSize [i] * candidato [mejores];
stepSize [i] = stepSize [i] * candidato [mejores]; / / acelerar
if (EVAL (punto actual) - antes) retorno punto actual;

BEAM SEARCH

Beam Search Algorithm

Objetivos

• Para mostrar cómo el haz de búsqueda algoritmo utiliza una función heurística y un ancho de haz dado en un intento de simular la búsqueda primero en amplitud de una manera eficiente en la memoria.
• Para enfatizar la importancia de limitar el consumo de un gráfico en la búsqueda de la memoria cuando la búsqueda de soluciones a los espacios de gran problema.
• Para demostrar las fortalezas y debilidades del algoritmo de la viga de la búsqueda.

Preparación

Para entender este algoritmo, debe estar familiarizado con el concepto de un gráfico como un grupo de nodos o vértices y aristas que conectan estos nodos. También es útil para entender el cómo un árbol de búsqueda se puede utilizar para mostrar el progreso de una búsqueda gráfica. Además, el conocimiento del algoritmo de búsqueda ª Manga es necesario porque la viga de la búsqueda es una modificación de este algoritmo.

Haz algoritmo de búsqueda

Aunque la prioridad a la amplitud de la búsqueda algoritmo está garantizado para encontrar el camino más corto desde un nodo inicial a un nodo objetivo en un gráfico sin ponderar, es imposible utilizar este algoritmo de búsqueda en espacios grandes debido a que su consumo de memoria es exponencial. Esto hace que el algoritmo se quede sin memoria principal antes de una solución se puede encontrar a la mayoría de grandes, los problemas no triviales. Por esta razón, haz la búsqueda se desarrolló en un intento de lograr la mejor solución encontrada por el algoritmo de búsqueda primero en amplitud de memoria sin consumir demasiado.

Para lograr este objetivo, haz la búsqueda utiliza una función heurística, h , para estimar el costo para alcanzar la meta de un nodo dado. También utiliza un ancho de haz, B , que especifica el número de nodos que se almacenan en cada nivel de la-Primera búsqueda en amplitud. Así, mientras que el-primer Buscar tiendas amplitud todos los nodos frontera (los nodos conectados a los vértices de clausura) en la memoria, la viga de algoritmos de búsqueda sólo se almacena la B los nodos con los mejores valores heurística en cada nivel de la búsqueda. La idea es que la función heurística permitirá que el algoritmo para seleccionar los nodos que lo llevará hasta el nodo objetivo, y la anchura del haz hará que el algoritmo para almacenar sólo estos nodos importantes en la memoria y evitar quedarse sin memoria antes de encontrar el estado de la meta .

En lugar de la lista abierta utilizada por el algoritmo de búsqueda-Primera Manga, el Rayo de algoritmos de búsqueda utiliza el HAZ para almacenar los nodos que se ampliarán en el siguiente bucle del algoritmo. Una tabla hash se utiliza para almacenar los nodos que se han visitado, al igual que la lista cerrada -utilizado en la Primera búsqueda en amplitud. Haz la búsqueda inicialmente añade el nodo de inicio al HAZ y la tabla hash . Entonces, cada vez que a través del bucle principal del algoritmo, haz la búsqueda agrega todos los nodos conectados a los nodos en el HAZ a su JUEGO de nodos sucesores y, a continuación añade el B los nodos con los mejores valores de la heurística JUEGO al HAZ y la tabla hash . Tenga en cuenta que un nodo que ya está en la tabla hash no se agrega a la VIGA por un camino más corto a ese nodo ya ha sido encontrado. Este proceso continúa hasta que el nodo meta se encuentra, la tabla hash se llena (lo que indica que la memoria disponible se ha agotado), o el HAZ está vacía después de que el bucle principal ha terminado (lo que indica un callejón sin salida en la búsqueda).
El haz de la búsqueda del algoritmo se muestra por el pseudocódigo a continuación. Este pseudocódigo se supone que la búsqueda de la viga se utiliza en un grafo no ponderado para la variable g se utiliza para no perder de vista la profundidad de la búsqueda, que es el costo de llegar a un nodo en ese nivel.

Pseudocódigo para el algoritmo de búsqueda de haz

/ * Inicialización * / g = 0; tabla_hash = {Inicio}; HAZ = {Inicio} / * * bucle principal / while (HAZ ≠ ∅) {/ / bucle hasta que el rayo no contiene nodos JUEGO = ∅; / / la conjunto vacío / * * JUEGO generar los nodos / for (cada estado en el HAZ) {for (cada sucesor de estado) {if (sucesor == meta) g regreso + 1; JUEGO DE CONJUNTO = ∪ {sucesor}; / / añadir sucesor a SET}} HAZ = ∅; / / el conjunto vacío g = g + 1; / * llenar el HAZ para el siguiente bucle * / while ((SET ≠ ∅) Y (B> | HAZ |)) {/ / establecer no está vacío y el número de nodos en el haz es menor que el sucesor de B = estado en conjunto con menor valor h; JUEGO DE CONJUNTO = \ {estado}; / / eliminar el estado de SET si (estado ∉ tabla_hash) {/ / Estado no es en el caso de tabla_hash (tabla_hash está llena) ∞ retorno; tabla_hash = ∪ tabla_hash {estado} / / añadir un estado a tabla_hash HAZ HAZ ∪ = {estado} / / añadir un estado a HAZ}}} / / meta no se ha encontrado, y HAZ está vacío - Haz la búsqueda no pudo encontrar la vuelta ∞ objetivo;

Ejemplo de seguimiento del algoritmo de búsqueda de haz

Las huellas de los siguientes algoritmos de búsqueda utilizan haz dos filas para representar cada bucle principal del algoritmo de la ejecución. La primera fila de cada bucle numerada muestra los nodos agregados a la AJUSTE . Estos nodos están ordenados por su valor heurístico, con el orden alfabético para ordenar los nodos con idéntica h valores. Desde el JUEGO es un conjunto matemático, si un nodo se inserta en el JUEGO más de una vez de los padres múltiples, que sólo aparece en el JUEGO vez. La segunda fila de cada bucle de listas numeradas de los ganglios del JUEGO que se agregan a la VIGA en la segunda parte del bucle principal. Ambas filas también mostrar la tabla hash para mostrar su estado actual. Observe que la tabla hash tiene sólo siete ranuras, lo que indica que el tamaño de la memoria de este ejemplo de seguimiento es de siete. Un sencillo esquema de hashing lineal con los valores fundamentales determinadas por los nombres de nodo 'mod valores ASCII 7 se utiliza para la simplicidad. En los tres de estas listas, los nodos se muestran en el formato nombre_nodo (predecessor_name) . El algoritmo se traza cuatro veces con diferentes valores de B para demostrar las fortalezas y debilidades del algoritmo. Cada traza incluye un árbol de búsqueda que muestra la VIGA en cada nivel de la búsqueda. En la gráfica, los números en los nombres de nodo son los h los valores de los nodos. Estos restos muestran cómo la viga de la búsqueda intenta encontrar el camino más corto desde el nodo que el nodo B en el gráfico se muestra en la Figura 1. (Figura 1 se incluye por encima de cada traza para mayor comodidad.)

Figura 1

Trace 1, B = 1

lazo
número JUEGO (primera fila por lazo paginación)
HAZ (segunda fila por lazo paginación) tabla_hash

HAZ = {I (null)} tabla_hash = {_, I (nulo), _ _ _ _ _}
1 JUEGO = {G (I), J (I), E (I), H (I)} tabla_hash = {_, I (nulo), _ _ _ _ _}
1 HAZ = {G (I)} tabla_hash = {_, I (nulo), _ _ _ _, G (I)}
2 JUEGO = {D (G), J (G), I (G)} tabla_hash = {_, I (nulo), _ _ _ _, G (I)}
2 HAZ = {D (G)} tabla_hash = {_, I (nulo), _, D (G), _, _, G (I)}
3 JUEGO = {G (D)} tabla_hash = {_, I (nulo), _, D (G), _, _, G (I)}
3 HAZ = {} tabla_hash = {_, I (nulo), _, D (G), _, _, G (I)}

En este punto, el HAZ está vacío, y el Rayo de algoritmos de búsqueda ha llegado a un callejón sin salida en su búsqueda. Desde el nodo G en el JUEGO ya estaba en la tabla hash , no podía ser añadido al HAZ , que dejó el HAZ vacío. Este seguimiento se muestra la mayor debilidad del algoritmo de búsqueda Manga: Una función heurística incorrecta puede llevar el algoritmo en una situación en la que no puede encontrar un objetivo, aunque el camino hacia la meta existe. Al tiempo que aumenta el valor de B puede permitir que la viga de la búsqueda para encontrar el objetivo, el aumento de B por un exceso puede provocar que el algoritmo se quede sin memoria antes de que se encuentra la meta. Por esta razón, la elección de B tiene un gran impacto en la búsqueda de rendimiento de la viga. La figura 2 muestra el HAZ nodos en cada nivel en esta gama de búsqueda muertos.

Figura 1

Trace 2, B = 2

lazo
número JUEGO (primera fila por lazo paginación)
HAZ (segunda fila por lazo paginación) tabla_hash

HAZ = {I (null)} tabla_hash = {_, I (nulo), _ _ _ _ _}
1 JUEGO = {G (I), J (I), E (I), H (I)} tabla_hash = {_, I (nulo), _ _ _ _ _}
1 HAZ = {G (I), J (I)} tabla_hash = {_, I (nulo), J (I), _, _, _, G (I)}
2 JUEGO = {A (J), D (G), G (J), J (G), E (J), I (G)} tabla_hash = {_, I (nulo), J (I), _, _, _, G (I)}
2 HAZ = {A (J), D (G)} tabla_hash = {A (J), I (nulo), J (I), D (G), _, _, G (I)}
3 JUEGO C = {(A), G (D), J (A)} tabla_hash = {A (J), I (nulo), J (I), D (G), _, _, G (I)}
3 HAZ = {C (A)} tabla_hash = {A (J), I (nulo), J (I), D (G), C (A), _, G (I)}
4 JUEGO B = {(C) [meta que se encuentran - devuelve el algoritmo], A (C)} tabla_hash = {A (J), I (nulo), J (I), D (G), C (A), _, G (I)}

Figura 3

za, el Rayo de la búsqueda algoritmo con éxito el objetivo que se encuentran a través de la ruta de acceso IJACB . Aunque se encontró una solución, esta solución no es óptima debido a IECB es una ruta más corta al nodo objetivo. Una vez más, una función heurística inexacta reduce la eficacia de los algoritmos de búsqueda de haz. La Figura 3 muestra el HAZ nodos en cada nivel de la búsqueda. Tenga en cuenta que sólo un nodo aparece en el HAZ en el nivel tres en el árbol. Esto demuestra que la viga de la búsqueda siempre puede no ser capaz de llenar el HAZ en cada nivel en la búsqueda. En el último nivel del árbol, el nodo A se añaden por primera vez a la CONJUNTO , a continuación, el nodo B (el nodo meta) que se encontró y provocó la búsqueda para completar.

En esta tra

Figura 1

Trace 3, B = 3

lazo
número JUEGO (primera fila por lazo paginación)
HAZ (segunda fila por lazo paginación) tabla_hash
HAZ = {I (null)} tabla_hash = {_, I (nulo), _ _ _ _ _}
1 JUEGO = {G (I), J (I), E (I), H (I)} tabla_hash = {_, I (nulo), _ _ _ _ _}
1 HAZ = {G (I), J (I), E (I)} tabla_hash = {_, I (nulo), J (I), _, E (I), _, G (I)}
2 JUEGO = {A (J), C (E), D (G), H (E), G (J), J (E), E (J), H (E), I (E)} tabla_hash = {_, I (nulo), J (I), _, E (I), _, G (I)}
2 HAZ = {A (J), C (E), D (G)} tabla_hash = {A (J), I (nulo), J (I), C (E), E (I), D (G), G (I)}
3 JUEGO B = {(C) [meta que se encuentran - devuelve el algoritmo], A (C), C (A), J (A)} tabla_hash = {A (J), I (nulo), J (I), C (E), E (I), D (G), G (I)}

Figura 4

Con B = 3, el algoritmo de búsqueda haz encontrado el camino óptimo para la meta. Sin embargo, el ancho del haz mayor causado el algoritmo para llenar toda la memoria disponible para la tabla hash. Figura 4 muestra el HAZ nodos en cada nivel en la búsqueda. En el último nivel del árbol, los nodos A , C y J fueron agregados a la JUEGO , y luego el nodo objetivo B se encontró, lo que provocó la búsqueda para completar.


Eficiencia / Análisis de Algoritmos

Por lo general, eficaces para analizar los algoritmos de búsqueda en grafos, considerando cuatro características:

• Integridad: Un algoritmo de búsqueda es completa si se encuentra una solución (nodo meta) cuando existe una solución.
• Optimalidad: Un algoritmo de búsqueda es óptimo si encuentra la solución óptima. En el caso del algoritmo de la viga de la búsqueda, esto significa que el algoritmo debe encontrar el camino más corto desde el nodo inicial al nodo meta.
• complejidad Tiempo: Esta es una orden de estimación de magnitud de la velocidad del algoritmo. La complejidad de tiempo se determina analizando el número de nodos que se generan durante la ejecución del algoritmo.
• complejidad espacial: Esta es una orden de estimación de magnitud del consumo de memoria del algoritmo. La complejidad del espacio está determinada por el número máximo de nodos que se deben almacenar en cualquier momento durante la ejecución del algoritmo.

Integridad

En general, la viga de algoritmos de búsqueda no es completa. Esto se ilustra en seguimiento 1. A pesar de que la memoria no se agota, el algoritmo no logró encontrar el objetivo, ya que no podía añadir nodos al HAZ . Por lo tanto, incluso con tiempo ilimitado y la memoria, es posible que el haz de búsqueda algoritmo perder el nodo objetivo cuando no hay un camino desde el nodo inicial al nodo meta. Una función heurística más precisa y un ancho de haz más grandes pueden mejorar la viga de la búsqueda de posibilidades de encontrar el objetivo. Sin embargo, esta falta de integridad es una de las debilidades principales de los algoritmos de búsqueda de haz.

Optimalidad

Así como el haz de búsqueda algoritmo no es completa, tampoco es garantía de ser óptima. Esto se muestra por Trace 2. En este ejemplo, haz búsqueda encontró el nodo meta, pero no logró encontrar el camino óptimo para la meta, a pesar de que la heurística en la figura 1 es admisible (subestima el costo de la meta de cada nodo) y consistente (subestima el costo entre los nodos vecinos ). Esto sucedió porque el ancho de la viga y una función heurística inexacta causado el algoritmo de perder la ampliación del camino más corto. Una función heurística más precisa y un ancho de haz más grande se puede hacer haz Buscar más probabilidades de encontrar la ruta óptima a la meta.

Tiempo Complejidad

El tiempo para el Rayo algoritmos de búsqueda para completar tiende a depender de la precisión de la función heurística. Una función heurística inexacta por lo general obliga al algoritmo para ampliar más nodos para encontrar la meta e incluso puede hacer que no logran encontrar el objetivo. En el peor de los casos, la función heurística conduce haz Buscar en todo el camino hasta el nivel más profundo en el árbol de búsqueda. Por lo tanto, el caso peor momento es O (Bm) , donde B es el ancho del haz y m es la profundidad máxima de cualquier ruta en el árbol de búsqueda. Esta complejidad de tiempo es lineal porque el haz algoritmos de búsqueda sólo se expande B nodos en cada nivel, no se ramifican más ampliamente en cada nivel, como los algoritmos de búsqueda que tienen muchas complejidades tiempo exponencial. La velocidad con la que este algoritmo se ejecuta es una de sus mayores fortalezas.

Espacio Complejidad

Búsqueda de consumo de memoria del haz es su rasgo más deseable. Debido a que el algoritmo sólo almacena B nodos en cada nivel en el árbol de búsqueda, el caso del espacio de complejidad-peor es O (Bm) , donde B es el ancho del haz y m es la profundidad máxima de cualquier ruta en el árbol de búsqueda. Este consumo de memoria lineal permite la viga de la búsqueda para investigar muy profundamente en los espacios de búsqueda grandes y, potencialmente, encontrar soluciones que otros algoritmos no pueden llegar.

Comparar con su libro de texto

Algoritmos puede mirar de manera diferente, pero siguen operando en casi la misma manera. Comparar el pseudocódigo anterior con la descripción de tu libro de texto (si está disponible).

A continuación, considere estas preguntas:

1. ¿Tiene su libro de texto de usar una tabla hash para almacenar los nodos que se han ampliado? Si no, ¿cómo almacenar estos nodos?
2. ¿Tiene su libro de texto de explicar qué tipo de estructura se debe utilizar para implementar el JUEGO ? Si es así, ¿qué estructura que se utiliza?

Explorando el comportamiento dinámico del algoritmo

Explora el algoritmo en JHAVÉ

Se puede practicar la viga algoritmos de búsqueda usando el sistema de visualización JHAVÉ algoritmo. Si usted no ha utilizado JHAVÉ antes, por favor, tómese el tiempo para ver las instrucciones en JHAVÉ utilizando en primer lugar. Si su navegador compatible con Java Webstart, puede iniciar una visualización de los algoritmos de búsqueda de haz directamente desde este enlace .

La búsqueda de la visualización del haz tiene quince ejemplo gráficos con los que usted puede experimentar. Los cuatro primeros ejemplos, perfect1 , perfect2 , perfect3 y perfect4 , tienen perfecta funciones heurísticas que permiten que el algoritmo para encontrar la ruta óptima si se dispone de memoria suficiente. Los siguientes siete gráficos, errant1 , errant2 , errant3 , errant4 , errant5 , errant6 y errant7 , han inexacta funciones heurístico que puede conducir el algoritmo para encontrar caminos que son más largos que el óptimo si la anchura del haz es demasiado pequeño. Los últimos cuatro gráficos, END1 , end2 , end3 y end4 , como resultado de fin de búsquedas muertos cuando se utiliza más pequeños anchos de haz. Para cada uno de estos ejemplos, puede establecer los valores de la anchura del haz, B , y el tamaño de la memoria, M , para ver cómo diferentes valores de estos parámetros afectan el resultado del algoritmo en el gráfico. Por último, el nivel de detalle opción le permite controlar cómo los pasos de animación a través de la pseudocódigo. La opción de alto detalle muestra cómo cada nodo se agrega a la AJUSTE uno por uno y es útil cuando se están menos familiarizados con el algoritmo. La opción de detalle bajo genera todos los nodos en el JUEGO en un solo paso, para que pueda centrarse más fácilmente en los demás aspectos del algoritmo.

Paso a través de los ejemplos de la visualización y la prueba de cómo los diferentes parámetros modificar los resultados obtenidos por el algoritmo de la viga de la búsqueda. Responda a las preguntas que aparecen durante la visualización para evaluar su comprensión del algoritmo. Cuando constantemente puede responder a las preguntas correctamente, pruebe los ejercicios siguientes.

DEPTH FIRST SEARCH

Primera búsqueda en profundidad (DFS) es un algoritmo para recorrer o buscar un árbol, estructura de árbol, o gráfico. Uno empieza en la raíz (la selección de algún nodo como raíz en el caso gráfico), y analiza la medida de lo posible a lo largo de cada rama antes de dar marcha atrás.

El tiempo y el espacio de análisis de la DFS es diferente de acuerdo a su área de aplicación. En ciencias de la computación teórica, DFS se utiliza normalmente para recorrer todo un gráfico, y toma tiempo O (| V | + | E |) , lineal en el tamaño del gráfico. En estas aplicaciones, también utiliza el espacio O (| V |) en el peor de los casos para almacenar la pila de los vértices de la ruta de búsqueda actual, así como el conjunto de vértices ya visitados. Por lo tanto, en este escenario, el tiempo y el espacio los límites son los mismos que para el primer manga de la búsqueda y la elección de cuál de los dos algoritmos para el uso no depende tanto de su complejidad y más en las diferentes propiedades de los ordenamientos vértice de los dos algoritmos de producir .

Para las aplicaciones de la DFS para buscar problemas en la inteligencia artificial , sin embargo, el gráfico que se debe buscar es a menudo demasiado grandes para visitar en su totalidad o incluso infinito, y DFS pueden sufrir de no terminación cuando la longitud de una ruta en el árbol de búsqueda es infinito. Por lo tanto, la búsqueda sólo se realiza a una profundidad limitada, y debido a una limitada disponibilidad de memoria normalmente no utiliza estructuras de datos que no perder de vista el conjunto de todos los vértices visitados anteriormente. En este caso, el tiempo sigue siendo lineal en el número de vértices y aristas ampliado (aunque este número no es lo mismo que el tamaño de todo el gráfico debido a que algunos vértices se pueden buscar más de una vez y otros no en todos), pero el espacio complejidad de esta variante de la DFS sólo es proporcional al límite de profundidad, mucho menor que el espacio necesario para buscar a la misma profundidad usando la búsqueda primero en amplitud.

Para tales aplicaciones, DFS también se presta mucho mejor a la heurística métodos de elegir una rama de futuro probable. Cuando un límite de profundidad adecuada, no se conoce a priori, iterativo en profundidad de la búsqueda profundización DFS se aplica en varias ocasiones con una secuencia de aumento de los límites, en el modo de la inteligencia artificial de análisis, con un factor de ramificación más de uno, iterativo aumenta la profundización del tiempo de funcionamiento por sólo un factor constante en el caso en que el límite de la profundidad correcta es conocido por el crecimiento geométrico del número de nodos por nivel.

Ejemplo

Para el siguiente gráfico:

una búsqueda en profundidad a partir de A, suponiendo que el borde izquierdo de la gráfica que se muestra son elegidos antes de los bordes derecho, y asumiendo la búsqueda recuerda nodos previamente visitados y no los repita (ya que es un pequeño gráfico), visitará la nodos en el siguiente orden: A, B, D, F, E, C, G. Los bordes recorrido de esta forma buscar un árbol Tremaux , una estructura con importantes aplicaciones en la teoría de grafos .

Realizar la misma búsqueda sin recordar visitado resultados nodos en visitar los nodos en el orden A, B, D, F, E, A, B, D, F, E, etc para siempre, atrapada en la F A, B, D, , el ciclo de E y nunca llegar a C o G.

Profundización iterativa es una técnica para evitar este bucle infinito, y que llegar a todos los nodos.

La producción de una primera búsqueda en profundidad-

Los cuatro tipos de bordes definidos por un árbol de expansión

El resultado más natural de una primera búsqueda en profundidad de un gráfico (si se considera como una función en lugar de un procedimiento ) es un árbol de expansión de las cimas alcanzadas durante la búsqueda. Sobre la base de este árbol de expansión, los bordes de la gráfica original se puede dividir en tres clases: los bordes hacia adelante, que apuntan de un nodo del árbol de uno de sus descendientes, de nuevo los bordes, que apuntan de un nodo a uno de sus antepasados, y los bordes de cruz, que no hacen ninguna. A veces los bordes de árboles, bordes que pertenecen al árbol de expansión en sí, se clasifican por separado de los bordes hacia adelante. Se puede demostrar que si la gráfica original es no dirigida entonces todos sus bordes son bordes de árboles o bordes posteriores.

Ordenamientos Vertex

También es posible utilizar la búsqueda en profundidad para ordenar linealmente los vértices de la gráfica original (o árbol). Hay tres formas comunes de hacerlo:

• Un preorden es una lista de los vértices en el orden en que fueron visitados por primera vez por el primer algoritmo de búsqueda exhaustiva. Esta es una forma compacta y natural de describir el progreso de la búsqueda, como se hizo anteriormente en este artículo.

Un preorden de un árbol de expresión es la expresión en notación polaca .

• Un postordering es una lista de los vértices en el orden en que fueron visitados por última vez por el algoritmo. Un postordering de un árbol de expresión es la expresión en notación polaca inversa .

• Un postordering inversa es el reverso de un postordering, es decir, una lista de los vértices en el orden inverso de su última visita. Al buscar un árbol, postordering inversa es lo mismo que preorden, pero en general son diferentes cuando se busca un gráfico. Por ejemplo, al buscar la grafo dirigido

Comenzando en el nodo A, una visita a los nodos en orden, ya sea para producir listas ABDBACA o ACDCABA (dependiendo de si el algoritmo elige para visitar B o C primero). Tenga en cuenta que las visitas repetidas en la forma de dar marcha atrás a un nodo, para comprobar si tiene aún sin visitar los vecinos, se incluyen aquí (incluso si se encuentra que no tiene ninguno). Así, el preorderings posibles ABCD y ACDB (orden por la ocurrencia más a la izquierda del nodo en la lista de arriba), mientras que la inversa postorderings posibles ACBD y ABCD (orden por la ocurrencia más a la derecha del nodo en la lista de arriba). Invertir postordering produce una ordenación topológica de un grafo acíclico dirigido . Este orden también es útil para análisis de flujo de control , ya que a menudo representa una linealización natural del flujo de control.

La gráfica anterior podría representar el flujo de control en un fragmento de código como
si (A) entonces {
B
Else {}
C
}
D
y es natural considerar el código siguiente en el orden ABCD o ACBD, pero no natural de usar el orden ABDC o B. ACD

Pseudocódigo

Entrada: Un grafo G y un vértice v de G
Salida: Un etiquetado de los bordes de la componente conexa de v como bordes descubrimiento y bordes posteriores
Un procedimiento DFS (G, v):
2 etiqueta v como se analiza
3 para todos los correos en los bordes G.incidentEdges (v) hacer
4 si arista e es entonces inexplorada
5 w ← G.opposite (V, E)
6 si w vértice está sin explorar a continuación,
7 etiqueta e como un borde descubrimiento
8 llamada recursiva DFS (G, w)
9 más
10 etiqueta de correo como un borde posterior

Aplicaciones

Los algoritmo aleatorio similar a la búsqueda en profundidad utilizada en la generación de un laberinto.

Los algoritmos que utilizan la búsqueda primero en profundidad como un bloque de construcción incluyen:

• Encontrar los componentes conectados .
• clasificación topológica .
• Resultado 2 - (lado o vértice) conectado a los componentes.
• Encontrar los componentes fuertemente conectados .
• Prueba de planaridad
• Resolviendo puzzles con una sola solución, tales como laberintos . (DFS se puede adaptar a encontrar todas las soluciones a un laberinto al incluir únicamente los nodos de la ruta actual en el conjunto visitó.)
• generación Laberinto puede utilizar una profundidad de sesiones de la búsqueda al azar.
• Encontrar biconnectivity en los gráficos .

BREADTH-FIRST SEARCH

Método

Breadth-First Search es una manera de encontrar todos los vértices alcanzables desde el origen de un vértice dado, s. Al igual que la primera búsqueda de profundidad, BFS atraviesa un componente conexo de un grafo dado, y define un árbol de expansión. Intuitivamente, la idea básica del primer aliento de la búsqueda es la siguiente: enviar una onda a cabo desde la fuente s. La ola golpea todos los vértices de un borde de s. A partir de ahí, la ola golpea todos los vértices y los dos bordes de s. el uso de colas FIFO 'Q' para mantener el frente de onda: v es en Q si y sólo si la onda ha afectado v, pero no ha salido de v todavía.

Algoritmo

Estrategia Global del Algoritmo

Breadth-first search comienza en un vértice dado s, que es en el nivel 0. En la primera etapa, que visita todos los vértices que están en la distancia de un borde de distancia. Cuando visitamos allí, pintamos como "visitado", los vértices adyacentes al iniciar el vértice s - estos vértices se sitúan en el nivel 1. En la segunda etapa, visitamos todos los nuevos vértices, podemos llegar a la distancia de los dos bordes de distancia desde el vértice fuente s. Estos nuevos vértices, que son adyacentes al nivel 1 vértices y no asignados previamente a un nivel, se colocan en el nivel 2, y así sucesivamente. El recorrido BFS termina cuando cada vértice ha sido visitado.Para realizar un seguimiento de los progresos, Breadth-first search colorea cada vértice. Cada vértice de la gráfica se encuentra en uno de tres estados:

1. Sin descubrir.
2. Date a conocer, pero no totalmente exploradas.
3. Explorado a fondo.

El estado de un vértice, u , se almacena en una variable de color de la siguiente manera:

1. color [ u ] = Blanco - para el "desconocido" del Estado,
2. color [ u ] = gris - para el "descubierto, pero no completamente explorado" el estado, y
3. color [ u ] = Negro - para el "explorado" el estado.

El BFS (G, s) desarrolla un algoritmo de búsqueda primero de árboles amplitud con el vértice origen, s, como su raíz. El padre o el antecesor de cualquier otro vértice en el árbol es el vértice de la que fue descubierto por primera vez. Para cada vértice v, el padre de v se coloca en la variable π [v]. Otra variable, d [v], calculado por BFS contiene el número de aristas del árbol en el camino de s a v.

Breadth-first search utiliza una cola FIFO, Q, para almacenar vértices gris.

Algoritmo: Transversal de breadth-first search.

BFS (V, E, s )

1. para cada u en V - { s } ▷ para cada vértice u en V [G], excepto s.
2. hacer de color [ u ] ← BLANCO.
3. d [ u ] ← infinito.
4. π [ u ] ← NIL.
5. color [ s ] ← GRIS vértice Fuente ▷ descubierto.
6. d [ s ] ← 0 ▷ inicializar.
7. π [ s ] ← NIL ▷ inicializar.
8. Q ← {} ▷ Borrar la cola Q.
9. Poner en cola (Q, s).
10 , mientras que Q es no vacío.
11. hacer u ← quitar de la cola (Q) ▷ Es decir, u = cabeza [Q].
12. para cada v adyacente a u ▷ de bucle por cada nodo a lo largo con el .borde.
13. hacer si el color [v] ← BLANCO ▷ si el color es el blanco que nunca has visto antes.
14. continuación, color [v] ← GRIS
15. d [v] ← d [u] + 1.
16. π [v] ← u.
17. Poner en cola (Q, v).
18. Quitar de la cola (Q).
19. color [u] ← NEGRO.

Evaluación

Ejemplo: La siguiente figura (de CLR) ilustra el progreso de la búsqueda en amplitud de sesiones en el gráfico de la muestra sin dirección.

a. Después de la inicialización (pintar cada vértice blanco, conjunto d [u] hasta el infinito para cada vértice u, y establecer que el padre de cada vértice a ser el NIL), el vértice de origen se descubre en la línea 5. Líneas 8-9 inicializar Q para contener sólo el vértice fuente
s.

b. El algoritmo descubre todos los vértices de un borde de s, es decir, descubrir todos los vértices (w y r) en el nivel 1.

c.

d. El algoritmo descubre todos los vértices dos bordes de la s, es decir, descubrir todos los vértices ( t , x , y v ) en el nivel 2.

e.

f.

g. El algoritmo descubre todos los vértices 3 aristas de s, es decir, descubrir todos los vértices (u y y) en el nivel 3.

h.

i. El algoritmo termina cuando todos los vértices se ha explorado completamente.

Análisis

• El bucle while en la búsqueda primero en amplitud se ejecuta en la mayoría de | veces | V. La razón es que cada vértice en cola en la mayoría de una sola vez. Por lo tanto, tenemos O (V).

• El ciclo for dentro del bucle while se ejecuta en la mayoría de | E | veces si G es un grafo dirigido o 2 | E | veces si G es no dirigido. La razón es que cada vértice desencolan en más de una vez y examinamos ( u , v ) sólo cuando u es quitado de la cola. Por lo tanto, cada arista examinados más de una vez si se dirige, a lo sumo dos veces si no dirigido. Por lo tanto, tenemos O (E).

Por lo tanto, el tiempo total acumulado de recorrido de la búsqueda primero en amplitud es O (V+E).

PODA-ALFA-BETA

Ejemplo de poda alfa-beta.

La poda alfa beta es una técnica de búsqueda que reduce el número de nodos evaluados en un árbol de juego por el algoritmo Minimax. Se trata de una técnica muy utilizada en programas de juegos entre adversarios como el ajedrez, el tres en raya o el Go.

Entre los pioneros en el uso de esta técnica encontramos a Arthur Samuel, D.J Edwards y T.P. Hart, Alan Kotok, Alexander Brudno, Donald Knuth y Ronald W. Moore.

El problema de la búsqueda Minimax es que el número de estados a explorar es exponencial al número de movimientos. Partiendo de este hecho, la técnica de poda alfa-beta trata de eliminar partes grandes del árbol, aplicándolo a un árbol Minimax estándar, de forma que se devuelva el mismo movimiento que devolvería este, gracias a que la poda de dichas ramas no influye en la decisión final.

Desarrollo del algoritmo

La búsqueda minimax es primero en profundidad, por ello en cualquier momento sólo se deben considerar los nodos a lo largo de un camino en el árbol.

La poda alfa-beta toma dicho nombre de la utilización de dos parámetros que describen los límites sobre los valores hacia atrás que aparecen a lo largo de cada camino.

α es el valor de la mejor opción hasta el momento a lo largo del camino para MAX, esto implicará por lo tanto la elección del valor más alto

β es el valor de la mejor opción hasta el momento a lo largo del camino para MIN, esto implicará por lo tanto la elección del valor más bajo.

Esta búsqueda alfa-beta va actualizando el valor de los parámetros según se recorre el árbol. El método realizará la poda de las ramas restantes cuando el valor actual que se está examinando sea peor que el valor actual de α o β para MAX o MIN, respectivamente.

El desarrollo del algoritmo en pseudocódigo será el siguiente:

función alfabeta(nodo, profundidad, α, β)
si nodo es un nodo terminal o profundidad = 0
devolver el valor heurístico del nodo
para cada hijo de nodo
α := max(α, -alfabeta(hijo, profundidad-1, -β, -α))
si β≤α
break
devolver α
(* Llamada inicial *)
alfabeta(origen, profundidad, -infinito, +infinito)


Ejemplo de poda alfa-beta

La figura muestra un ejemplo de la poda alfa-beta. Cada nivel representa la jugada de los jugadores MAX y MIN, que tendrán que definir un valor α o β respectivamente.

A continuación se presenta un ejemplo de aplicación del algoritmo para el árbol de la figura. En ella los nodos podados al aplicar el algoritmo se presentan sombreados en gris.

Comenzamos con la búsqueda de primero en profundidad. El padre de los nodos hoja más a la izquierda, etiquetados con 5 y 6 respectivamente, deberá escoger un valor β al tratarse de un nivel MIN, esto implica que deberá escoger el valor mínimo entre dichos nodos, es decir 5.

Siguiendo el desarrollo, se expandirán el resto de sucesores del padre. En este caso se expande el camino que conduce a los nodos hoja 7 y, buscando un valor β menor, el nodo etiquetado con 4. En este momento el valor momentáneo de β en ese nivel es 4 (el mínimo entre 7 y 4). Esto implica que en este momento en el nivel superior, el padre del nodo que etiquetamos anteriormente con β igual a 5, y de este β igual a 4 momentáneo, debe decidir el mejor valor, el más alto al encontrarse en un nivel MAX), si siguiéramos expandiendo hijos del nodo MIN padre de 7 y 4, sólo podríamos conseguir valores menores a 4, lo que seguiría implicando una elección de la jugada izquierda en el nivel MAX, por lo tanto, podemos podar el resto de hijos, tal y como se muestra en la Figura.

El resto del desarrollo del árbol se seguiría utilizando los criterios mencionados con anterioridad.

Eficacia de la poda alfa-beta

La eficacia de la poda alfabeta depende del orden en el que se examinan los sucesores, es decir, el algoritmo se comportará de forma más eficiente si examinamos primero los sucesores que probablemente serán los mejores.

Si esto pudiera hacerse, implicaría que alfa-beta sólo tendría que examinar O(bd / 2) en lugar de los O(bd) de Minimax. Esto implica que el factor de ramificación eficaz será de en lugar de b. En otras palabras, alfa-beta podría mirar hacia delante aproximadamente dos veces más que Minimax en la misma cantidad de tiempo.

Si se recurre a una ordenación aleatoria en lugar de primero el mejor en los sucesores, el número aproximado de nodos examinados sería de O(b3d / 4) para un valor moderado de b. En ajedrez se puede realizar una función de ordenación sencilla teniendo en cuenta primero capturas de fichas, después amenazas, movimientos hacia delante y por último movimientos hacia detrás, esto conseguiría aproximadamente un factor de dos del resultado O(bd / 2) del mejor caso. La inclusión de esquemas dinámicos para ordenar movimientos, basados en experiencia podrían acercarse al límite teórico.

MINIMAX

Teorema Minimax

John von Neumann es el creador del teorema minimax, quien dio la siguiente noción de lo que era un juego:

"Un juego es una situación conflictiva en la que uno debe tomar una decisión sabiendo que los demás también toman decisiones, y que el resultado del conflicto se determina, de algún modo, a partir de todas las decisiones realizadas."

También afirmó que:

"Siempre existe una forma racional de actuar en juegos de dos participantes, si los intereses que los gobiernan son completamente opuestos."

La demostración a esa afirmación se llama Teoría Minimax y surge en 1926.

Este teorema establece que en los juegos bipersonales de suma nula, donde cada jugador conoce de antemano la estrategia de su oponente y sus consecuencias, existe una estrategia que permite a ambos jugadores minimizar la pérdida máxima esperada. En particular, cuando se examina cada posible estrategia, un jugador debe considerar todas las respuestas posibles del jugador adversario y la pérdida máxima que puede acarrear. El jugador juega, entonces, con la estrategia que resulta en la minimización de su máxima pérdida. Tal estrategia es llamada óptima para ambos jugadores sólo en caso de que sus minimaxes sean iguales (en valor absoluto) y contrarios (en signo). Si el valor común es cero el juego se convierte en un sinsentido.

Algoritmo Minimax con movimientos alternativos

Pasos del algoritmo Minimax:

1. Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal.
2. Cálculo de los valores de la función de utilidad para cada nodo terminal.
3. Calcular el valor de los nodos superiores a partir del valor de los inferiores. Alternativamente se elegirán los valores mínimos y máximos representando los movimientos del jugador y del oponente, de ahí el nombre de Minimax.
4. Elegir la jugada valorando los valores que han llegado al nivel superior.

El algoritmo explorará los nodos del árbol asignándoles un valor numérico mediante una función de evaluación, empezando por los nodos terminales y subiendo hacia la raíz. La función de utilidad definirá lo buena que es la posición para un jugador cuando la alcanza. En el caso del ajedrez los posibles valores son (+1, 0,-1) que se corresponden con ganar, empatar y perder respectivamente. En el caso del backgammon los posibles valores tendrán un rango de [+192,-192], correspondiéndose con el valor de las fichas. Para cada juego pueden ser diferentes.

Si Minimax se enfrenta con el dilema del prisionero escogerá siempre la opción con la cual maximiza su resultado suponiendo que el contrincante intenta minimizarlo y hacernos perder.

Min y Max

Muy pocos juegos de mesa son para un único jugador, ¿cómo podemos añadir esta eventualidad en nuestro árbol? Piensa sobre ello, cuando jugamos nuestros movimientos estamos intentando maximizar nuestra puntuación, así que nuestro oponente querrá minimizar nuestra puntuación. Vamos a mirar a un árbol de juego - aunque este está limitado a una profundidad de 2 capas. Este es nuestro árbol de juego con evaluaciones asignadas a los nodos finales:

Ahora, los valores asignados son para juegos representando los juegos que eligen nuestro oponente. N1 es el juego actual, N2-N4 son nuestros tres posibles movimientos y N5-N13 son los posibles movimientos que hará a continuación nuestro oponente. Como nuestro oponente intentará minimizar nuestras posibilidades de ganar*, calcularemos el mínimo valor para cada nodo y se lo asignaremos a su padre. N2 será igual a 0, N3 igual a 3 y N4 igual a 2. Al hacer una elección para nuestro mejor posible movimiento, escogeremos el máximo de estos valores - que es 3 (N3).

Ejemplo

En el siguiente ejemplo puede verse el funcionamiento de Minimax en un árbol generado para un juego imaginario. Los posibles valores de la función de utilidad tienen un rango de [1-9]. En los movimientos del contrincante suponemos que escogerá los movimientos que minimicen nuestra utilidad, en nuestros movimientos suponemos que escogeremos los movimientos que maximizan nuestra utilidad.

El primer paso será calcular los nodos terminales, en verde. Posteriormente calcularemos el cuarto nivel, movimiento min, minimizando lo elegido (5, 2 y 1). Después podremos calcular el tercer nivel, movimiento max, maximizando la utilidad (5, 9). El segundo nivel es un movimiento min (5, 3 y 1). Finalmente llegamos al primer nivel, el movimiento actual, elegiremos el nodo que maximice nuestra utilidad (5).


Optimización

En la práctica el método Minimax es impracticable excepto en supuestos sencillos. Realizar la búsqueda completa requeriría cantidades excesivas de tiempo y memoria.

Claude Shannon en su texto sobre ajedrez de 1950 (Programming a Computer for Playing Chess) propuso limitar la profundidad de la búsqueda en el árbol de posibilidades y determinar su valor mediante una función heurística. Para optimizar Minimax puede limitarse la búsqueda por nivel de profundidad o por tiempo de ejecución. Otra posible técnica es el uso de la poda alfa-beta. Esta optimización se basa en la suposición que el jugador contrario no nos permitirá jugar nuestras mejores jugadas.