búsqueda de haz es un algoritmo de búsqueda heurística que explora un gráfico al expandir el nodo más prometedor en un conjunto limitado. La búsqueda de haz es una optimización de la mejor búsqueda que reduce sus requisitos de memoria. Best-first search es una búsqueda gráfica que ordena todas las soluciones parciales (estados) de acuerdo con alguna heurística. Pero en la búsqueda de haces, solo un número predeterminado de las mejores soluciones parciales se mantienen como candidatos. [1] Por lo tanto, es un algoritmo codicioso .
Detalles [ editar ]
La búsqueda de haz utiliza la búsqueda de amplitud para construir su árbol de búsqueda . En cada nivel del árbol, genera todos los sucesores de los estados en el nivel actual, ordenándolos en orden creciente de costo heurístico. [3] Sin embargo, solo almacena un número predeterminado,, de los mejores estados en cada nivel (llamado ancho del haz). Solo esos estados se expanden a continuación. Cuanto mayor es el ancho del haz, menos estados se podan. Con un ancho de haz infinito, no se podan estados y la búsqueda de haz es idéntica a la búsqueda de amplitud . El ancho del haz limita la memoria requerida para realizar la búsqueda. Dado que un estado objetivo podría podarse potencialmente, la búsqueda de haz sacrifica la integridad (la garantía de que un algoritmo terminará con una solución, si existe). La búsqueda de haces no es óptima (es decir, no hay garantía de que encuentre la mejor solución).
En general, la búsqueda de haz devuelve la primera solución encontrada. La búsqueda de haces para la traducción automática es un caso diferente: una vez que alcanza la profundidad de búsqueda máxima configurada (es decir, la longitud de la traducción), el algoritmo evaluará las soluciones encontradas durante la búsqueda a varias profundidades y devolverá la mejor (la que tiene la mayor probabilidad).
El ancho del haz puede ser fijo o variable. Un enfoque que utiliza un ancho de haz variable comienza con el ancho como mínimo. Si no se encuentra una solución, el haz se ensancha y se repite el procedimiento. [4]
Usos [ editar ]
La búsqueda de haces se usa con mayor frecuencia para mantener la capacidad de seguimiento en sistemas grandes con una cantidad insuficiente de memoria para almacenar todo el árbol de búsqueda. [5] Por ejemplo, se utiliza en muchos sistemas de traducción automática . [6] Para seleccionar la mejor traducción, se procesa cada parte y aparecen muchas formas diferentes de traducir las palabras. Las mejores mejores traducciones según sus estructuras de oración se mantienen, y el resto se descarta. El traductor luego evalúa las traducciones de acuerdo con un criterio dado, eligiendo la traducción que mejor cumpla con los objetivos. El primer uso de una búsqueda de haz fue en el Sistema de reconocimiento de voz Harpy, CMU 1976. [7]
Variantes [ editar ]
La búsqueda del haz se ha completado combinándola con la búsqueda de profundidad primero , lo que resulta en la búsqueda de haz de haz [8] y la búsqueda de haz de profundidad primero , [5] y con búsqueda de discrepancia limitada, [9] resultando en la búsqueda de haz usando el retroceso de discrepancia limitado [5] (BOMBILLA). Los algoritmos de búsqueda resultantes son algoritmos en cualquier momento que encuentran rápidamente soluciones buenas pero probablemente subóptimas, como la búsqueda de haces, luego retroceden y continúan buscando soluciones mejoradas hasta la convergencia hacia una solución óptima.
En el contexto de una búsqueda local , llamamos a la búsqueda de haz local un algoritmo específico que comienza a seleccionar estados generados aleatoriamente y luego, para cada nivel del árbol de búsqueda, siempre considera nuevos estados entre todos los posibles sucesores de los actuales, hasta que alcance una meta. [10] [11]
Dado que la búsqueda de haz local a menudo termina en máximos locales, una solución común es elegir el siguiente estados de forma aleatoria, con una probabilidad dependiente de la evaluación heurística de los estados. Este tipo de búsqueda se llama búsqueda de haz estocástico . [12]
Otras variantes son la búsqueda de haz flexible y la búsqueda de haz de recuperación .
Best-first search es un algoritmo de búsqueda que explora un gráfico al expandir el nodo más prometedor elegido de acuerdo con una regla específica.
Judea Pearl describió la mejor búsqueda como la estimación de la promesa del nodo n mediante una "función de evaluación heurísticaque, en general, puede depender de la descripción de n , la descripción del objetivo, la información recopilada por la búsqueda hasta ese momento y, lo más importante, de cualquier conocimiento adicional sobre el dominio del problema ". [1] [2]
Algunos autores han utilizado la "búsqueda del mejor primero" para referirse específicamente a una búsqueda con una heurística que intenta predecir qué tan cerca está el final de una ruta a una solución, de modo que las rutas que se consideran más cercanas a una solución se extienden primero . Este tipo específico de búsqueda se denomina búsqueda codiciosa del mejor primero [2] o búsqueda heurística pura . [3]
La selección eficiente del mejor candidato actual para la extensión generalmente se implementa mediante una cola de prioridad .
El algoritmo de búsqueda A * es un ejemplo del mejor algoritmo de búsqueda, como lo es B * . Los algoritmos de mejor primero a menudo se usan para encontrar rutas en la búsqueda combinatoria . Ni A * ni B * son una búsqueda codiciosa, ya que incorporan la distancia desde el inicio, además de las distancias estimadas hasta la meta.
BFS codicioso [ editar ]
Usando un algoritmo codicioso , expanda el primer sucesor del padre. Después de que se genera un sucesor: [4]
- Si la heurística del sucesor es mejor que su padre, el sucesor se establece al frente de la cola (con el padre reinsertado directamente detrás de él) y el ciclo se reinicia.
- De lo contrario, el sucesor se inserta en la cola (en una ubicación determinada por su valor heurístico). El procedimiento evaluará los sucesores restantes (si los hay) de los padres.
Beam Stack Search [1] es un algoritmo de búsqueda que combina el retroceso cronológico (es decir, búsqueda de profundidad primero ) con búsqueda de haz y es similar a la búsqueda de profundidad de primer haz. [2] Ambos algoritmos de búsqueda son algoritmos en cualquier momento que encuentran rápidamente soluciones buenas pero probablemente subóptimas, como la búsqueda de haces, luego retroceden y continúan buscando soluciones mejoradas hasta la convergencia hacia una solución óptima.
Implementación [ editar ]
Beam Stack Search utiliza la pila de vigas como una estructura de datos para integrar el retroceso cronológico con la búsqueda de vigas y puede combinarse con la técnica del algoritmo de dividir y conquistar , lo que resulta en la búsqueda de dividir y conquistar la pila de vigas.
Alternativas [ editar ]
Haz Búsqueda Usando Limited Discrepancia Backtracking [2] (bombilla) es un algoritmo de búsqueda que combina la búsqueda discrepancia limitada con búsqueda en haz y por lo tanto lleva a cabo no cronológico marcha atrás , que a menudo supera al retroceso cronológico realizado por haz Pila de búsqueda y Profundidad-primer haz de búsqueda.
cola de prioridad es un tipo de datos abstractos que es como una estructura de cola o pila de datos normal , pero donde además cada elemento tiene una "prioridad" asociada. En una cola de prioridad, un elemento con alta prioridad se sirve antes que un elemento con baja prioridad. En algunas implementaciones, si dos elementos tienen la misma prioridad, se sirven de acuerdo con el orden en que fueron colocados en cola, mientras que en otras implementaciones, el orden de los elementos con la misma prioridad no está definido.
Si bien las colas de prioridad a menudo se implementan con montones , son conceptualmente distintas de los montones. Una cola prioritaria es un concepto abstracto como "una lista " o "un mapa "; así como una lista puede implementarse con una lista vinculada o una matriz , una cola prioritaria puede implementarse con un montón o una variedad de otros métodos, como una matriz no ordenada.
Operaciones [ editar ]
Una cola prioritaria debe al menos admitir las siguientes operaciones:
- is_empty : verifica si la cola no tiene elementos.
- insert_with_priority : agrega un elemento a la cola con una prioridad asociada.
- pull_highest_priority_element : elimina el elemento de la cola que tiene la máxima prioridad y lo devuelve.
- Esto también se conoce como " pop_element (Off) ", " get_maximum_element " o " get_front (most) _element ".
- Algunas convenciones invierten el orden de prioridades, considerando que los valores más bajos son de mayor prioridad, por lo que esto también se conoce como " get_minimum_element ", y a menudo se lo conoce como " get-min " en la literatura.
- En cambio, esto se puede especificar como funciones separadas " peek_at_highest_priority_element " y " delete_element ", que se pueden combinar para producir " pull_highest_priority_element ".
Además, peek (en este contexto a menudo llamado find-max o find-min ), que devuelve el elemento de mayor prioridad pero no modifica la cola, se implementa con mucha frecuencia y casi siempre se ejecuta en tiempo O (1) . Esta operación y su rendimiento O (1) es crucial para muchas aplicaciones de colas prioritarias.
Las implementaciones más avanzadas pueden admitir operaciones más complicadas, como pull_lowest_priority_element , inspeccionar los primeros elementos de mayor o menor prioridad, borrar la cola, borrar subconjuntos de la cola, realizar una inserción por lotes, fusionar dos o más colas en una, aumentar la prioridad de cualquier elemento, etc.
Uno puede imaginar una cola de prioridad como una cola modificada , pero cuando uno saca el siguiente elemento de la cola, el elemento de mayor prioridad se recupera primero.
Las pilas y las colas pueden modelarse como tipos particulares de colas prioritarias. Como recordatorio, así es como se comportan las pilas y colas:
- pila : los elementos se extraen en orden de último en entrar, primero en salir (por ejemplo, una pila de papeles)
- cola : los elementos se extraen en orden de primero en entrar, primero en salir (por ejemplo, una línea en una cafetería)
En una pila, la prioridad de cada elemento insertado está aumentando monotónicamente; por lo tanto, el último elemento insertado es siempre el primero recuperado. En una cola, la prioridad de cada elemento insertado está disminuyendo monotónicamente; así, el primer elemento insertado es siempre el primero recuperado.
Implementación [ editar ]
Implementaciones ingenuas [ editar ]
Hay una variedad de formas simples, generalmente ineficientes, de implementar una cola prioritaria. Proporcionan una analogía para ayudar a uno a entender qué es una cola prioritaria. Por ejemplo, uno puede mantener todos los elementos en una lista sin ordenar. Siempre que se solicite el elemento de mayor prioridad, busque en todos los elementos el que tenga la mayor prioridad. (En notación O grande : O (1) tiempo de inserción, O ( n ) tiempo de extracción debido a la búsqueda).
Implementación habitual [ editar ]
Para mejorar el rendimiento, las colas de prioridad generalmente usan un montón como su columna vertebral, lo que proporciona un rendimiento O (log n ) para inserciones y eliminaciones, y O ( n ) para construir inicialmente. Las variantes de la estructura básica de datos de almacenamiento dinámico, como los montones de pares o los montones de Fibonacci, pueden proporcionar mejores límites para algunas operaciones. [1]
Alternativamente, cuando se utiliza un árbol de búsqueda binario de equilibrio automático , la inserción y la eliminación también toman tiempo O (log n ), aunque construir árboles a partir de secuencias de elementos existentes toma tiempo O ( n log n ); Esto es típico cuando uno ya puede tener acceso a estas estructuras de datos, como con bibliotecas estándar o de terceros.
Desde el punto de vista de la complejidad computacional, las colas de prioridad son congruentes con los algoritmos de clasificación. La sección sobre la equivalencia de las colas de prioridad y los algoritmos de clasificación , a continuación, describe cómo los algoritmos de clasificación eficientes pueden crear colas de prioridad eficientes.
Montones especializados [ editar ]
Existen varias estructuras de datos de almacenamiento dinámico especializadas que proporcionan operaciones adicionales o superan las implementaciones basadas en almacenamiento dinámico para tipos específicos de claves, específicamente claves enteras.
- Cuando el conjunto de claves es {1, 2, ..., C }, y solo se necesita insertar , encontrar-min y extraer-min , se puede construir una cola de depósito como una matriz de listas enlazadas en C más una parte superior del puntero , inicialmente C . Insertar un elemento con la tecla k agrega el elemento a la k 'th y actualiza top ← min (top, k ) , ambos en tiempo constante. Extract-min elimina y devuelve un elemento de la lista con la parte superior del índice , luego incrementa la parte superiorsi es necesario hasta que apunte nuevamente a una lista no vacía; esto lleva tiempo O ( C ) en el peor de los casos. Estas colas son útiles para ordenar los vértices de un gráfico por su grado. [2] : 374
- Para el conjunto de teclas {1, 2, ..., C }, un árbol de Van Emde Boas apoyaría el mínimo , el máximo , insertar , eliminar , búsqueda , extracto-min , extraer-max , predecesoras y sucesoras operaciones en O ( log log C ) tiempo, pero tiene un costo de espacio para pequeñas colas de aproximadamente O (2 m / 2 ), donde m es el número de bits en el valor de prioridad. [3]
- El algoritmo de árbol Fusion de Fredman y Willard implementa la operación mínima en tiempo O (1) e inserta y extrae operaciones mínimas enSin embargo, el autor afirma que "nuestros algoritmos tienen solo interés teórico; los factores constantes involucrados en los tiempos de ejecución impiden la practicidad". [4]
Para las aplicaciones que realizan muchas operaciones de " peek " para cada operación "extract-min", la complejidad de tiempo para las acciones de peek se puede reducir a O (1) en todas las implementaciones de árbol y montón almacenando en caché el elemento de mayor prioridad después de cada inserción y eliminación. Para la inserción, esto agrega como máximo un costo constante, ya que el elemento recién insertado se compara solo con el elemento mínimo previamente almacenado en caché. Para la eliminación, esto a lo sumo agrega un costo adicional de "vistazo", que generalmente es más barato que el costo de eliminación, por lo que la complejidad general del tiempo no se ve significativamente afectada.
Las colas de prioridad monótonas son colas especializadas que están optimizadas para el caso en el que nunca se inserta ningún elemento que tenga una prioridad más baja (en el caso del almacenamiento dinámico mínimo) que cualquier elemento extraído previamente. Esta restricción se cumple con varias aplicaciones prácticas de colas prioritarias.
Resumen de tiempos de ejecución [ editar ]
Aquí hay complejidades de tiempo [5] de varias estructuras de datos de montón. Los nombres de funciones suponen un montón mínimo. Para el significado de " O ( f )" y " Θ ( f )" ver notación Big O .
| Operación | encontrar-min | delete-min | insertar | tecla de disminución | fusionar |
|---|---|---|---|---|---|
| Binario [5] | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
| Izquierdista | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
| Binomial [5] | Θ (log n ) | Θ (log n ) | Θ (1) [a] | Θ (log n ) | O (log n ) [b] |
| Fibonacci [5] [6] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
| Emparejamiento [7] | Θ (1) | O (log n ) [a] | Θ (1) | o (log n ) [a] [c] | Θ (1) |
| Brodal [10] [d] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Emparejamiento de rango [12] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [a] | Θ (1) |
| Fibonacci estricto [13] | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| 2-3 montón | ? | O (log n ) [a] | O (log n ) [a] | Θ (1) | ? |
- ^ a b c d e f g h i Tiempo amortizado.
- ^ n es el tamaño del montón más grande.
- ^ Límite inferior de[8] límite superior de[9]
- ^ Brodal y Okasaki describen más adelante unavariante persistente con los mismos límites, excepto para la tecla de disminución, que no es compatible. Los montones con n elementos se pueden construir de abajo hacia arriba en O ( n ). [11]
Equivalencia de colas prioritarias y algoritmos de clasificación [ editar ]
Usar una cola prioritaria para ordenar [ editar ]
La semántica de las colas prioritarias sugiere naturalmente un método de clasificación: inserte todos los elementos que se ordenarán en una cola prioritaria y elimínelos secuencialmente; saldrán en orden ordenado. Este es realmente el procedimiento utilizado por varios algoritmos de clasificación , una vez que la capa de se elimina abstracción proporcionada por la cola de prioridad. Este método de clasificación es equivalente a los siguientes algoritmos de clasificación:
| Nombre | Implementación de cola prioritaria | Mejor | Promedio | Peor |
|---|---|---|---|---|
| Heapsort | Montón | |||
| Smoothsort | Leonardo Heap | |||
| Tipo de selección | Matriz desordenada | |||
| Tipo de inserción | Matriz ordenada | |||
| Tipo de árbol | Árbol de búsqueda binaria autoequilibrante |
Usando un algoritmo de clasificación para hacer una cola prioritaria [ editar ]
Un algoritmo de clasificación también se puede utilizar para implementar una cola prioritaria. Específicamente, Thorup dice: [14]
Es decir, si hay un algoritmo de ordenación que puede ordenar en tiempo O ( S ) por tecla, donde S es alguna función de n y tamaño de palabra , [15] entonces uno puede usar el procedimiento dado para crear una cola de prioridad donde tirar el el elemento de mayor prioridad es el tiempo O (1), e insertar nuevos elementos (y eliminar elementos) es el tiempo O ( S ). Por ejemplo, si uno tiene un algoritmo de clasificación O ( n log log n ), se puede crear una cola prioritaria con O (1) tirando y O (log log n ) inserción.
Bibliotecas [ editar ]
La Biblioteca de plantillas estándar (STL) y el estándar C ++ 1998, se especifica si no se especifica), el contenedor subyacente para almacenar las estructuras de datos (por defecto es std :: vector ), y dos iteradores al principio y al final de una secuencia. A diferencia de los contenedores STL reales, no permite la iteración también tienen una implementación en el montón de bibliotecas.
priority_queuecomo uno de los adaptadores de contenedor STL de sus elementos (se adhiere estrictamente a su definición de tipo de datos abstracto). STL también tiene funciones de utilidad para manipular otro contenedor de acceso aleatorio como un montón dinámico binario. Las bibliotecas de Boost plantillas de clase de . Sin embargo, no especifica cómo deben servirse dos elementos con la misma prioridad y, de hecho, las implementaciones comunes no los devolverán de acuerdo con su orden en la cola. Implementa una cola de máxima prioridad y tiene tres parámetros: un objeto de comparación para ordenar, como un objeto de función (por defecto es menos
El módulo heapq de Python implementa un min-montón dinámico binario en la parte superior de una lista.
La biblioteca de Go contiene un módulo contenedor / montón , que implementa un montón mínimo encima de cualquier estructura de datos compatible.
El marco de la Core Foundation de Apple contiene una estructura CFBinaryHeap , que implementa un montón mínimo.
Aplicaciones [ editar ]
Gestión del ancho de banda [ editar ]
Las colas de prioridad se pueden usar para administrar recursos limitados, como el ancho de banda en una línea de transmisión desde un enrutador de red . En el caso de colas de tráfico salientes debido a un ancho de banda insuficiente, todas las demás colas se pueden detener para enviar el tráfico desde la cola de mayor prioridad a la llegada. Esto garantiza que el tráfico priorizado (como el tráfico en tiempo real, por ejemplo, un flujo RTP de una conexión VoIP ) se reenvíe con el menor retraso y la menor probabilidad de ser rechazado debido a que una cola alcanza su capacidad máxima. El resto del tráfico se puede manejar cuando la cola de mayor prioridad está vacía. Otro enfoque utilizado es enviar desproporcionadamente más tráfico desde colas de mayor prioridad.
Muchos protocolos modernos para redes de área local también incluyen el concepto de colas prioritarias en la subcapa de control de acceso a medios (MAC) para garantizar que las aplicaciones de alta prioridad (como VoIP o IPTV ) experimenten una latencia más baja que otras aplicaciones que se pueden atender con El mejor servicio de esfuerzo . Los ejemplos incluyen IEEE 802.11e (una enmienda a IEEE 802.11 que proporciona calidad de servicio ) y ITU-T G.hn (un estándar para la red de área local de alta velocidad que utiliza cableado doméstico existente ( líneas de alimentación , líneas telefónicas y cables coaxiales ).
Por lo general, se establece una limitación (regulador) para limitar el ancho de banda que puede tomar el tráfico de la cola de mayor prioridad, a fin de evitar que los paquetes de alta prioridad asfixien el resto del tráfico. Este límite generalmente nunca se alcanza debido a instancias de control de alto nivel como Cisco Callmanager , que se puede programar para inhibir llamadas que excederían el límite de ancho de banda programado.
Simulación discreta de eventos [ editar ]
Otro uso de una cola prioritaria es administrar los eventos en una simulación de eventos discretos . Los eventos se agregan a la cola con su tiempo de simulación utilizado como prioridad. La ejecución de la simulación continúa tirando repetidamente de la parte superior de la cola y ejecutando el evento al respecto.
Algoritmo de Dijkstra [ editar ]
Cuando el gráfico se almacena en forma de lista de adyacencia o matriz, la cola de prioridad se puede utilizar para extraer el mínimo de manera eficiente al implementar el algoritmo de Dijkstra , aunque también se necesita la capacidad de alterar la prioridad de un vértice particular en la cola de prioridad de manera eficiente.
Codificación Huffman [ editar ]
La codificación de Huffman requiere que uno obtenga repetidamente los dos árboles de menor frecuencia. Una cola prioritaria es un método para hacerlo .
Los mejores algoritmos de búsqueda primero [ editar ]
Los mejores algoritmos de búsqueda , como el algoritmo de búsqueda A * , encuentran la ruta más corta entre dos vértices o nodos de un gráfico ponderado , probando primero las rutas más prometedoras. Una cola de prioridad (también conocida como la franja ) se utiliza para realizar un seguimiento de las rutas inexploradas; aquel para el cual la estimación (un límite inferior en el caso de A *) de la longitud total de la ruta es más pequeña tiene la máxima prioridad. Si las limitaciones de memoria hacen que la mejor búsqueda no sea práctica, se pueden utilizar variantes como el algoritmo SMA * , con una cola de prioridad de doble extremo para permitir la eliminación de elementos de baja prioridad.
Algoritmo de triangulación ROAM [ editar ]
El algoritmo de mallas de adaptación óptima en tiempo real ( ROAM ) calcula una triangulación de un terreno que cambia dinámicamente. Funciona dividiendo triángulos donde se necesitan más detalles y fusionándolos donde se necesitan menos detalles. El algoritmo asigna a cada triángulo en el terreno una prioridad, generalmente relacionada con la disminución del error si ese triángulo se dividiera. El algoritmo usa dos colas prioritarias, una para triángulos que se pueden dividir y otra para triángulos que se pueden fusionar. En cada paso, el triángulo de la cola dividida con la prioridad más alta se divide, o el triángulo de la cola de fusión con la prioridad más baja se fusiona con sus vecinos.
Algoritmo de Prim para un árbol de expansión mínimo [ editar ]
Usando la cola de prioridad de almacenamiento dinámico mínima en el algoritmo de Prim para encontrar el árbol de expansión mínimo de un gráfico conectado y no dirigido , se puede lograr un buen tiempo de ejecución. Esta cola de prioridad de almacenamiento dinámico mínimo utiliza la estructura de datos de almacenamiento dinámico mínimo que admite operaciones como insertar , mínimo , extraer-min , tecla de disminución . [16] En esta implementación, el peso de los bordes se usa para decidir la prioridad de los vértices . Baje el peso, mayor prioridad y mayor peso, menor prioridad.
No hay comentarios:
Publicar un comentario