Algoritmo voraz

Algoritmo voraz

Un algoritmo voraz (también conocido como ávido, devorador o goloso) es aquel que, para resolver un determinado problema, sigue una metaheurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

Contenido

Esquema

Dado un conjunto finito de entradas C, un algoritmo voraz devuelve un conjunto S (seleccionados) tal que S\subseteq C y que además cumple con las restricciones del problema inicial. Cada conjunto S que satisfaga las restricciones se le suele denominar prometedor, y si éste además logra que la función objetivo se minimice o maximice (según corresponda) diremos que S es una solución óptima.

Elementos de los que consta la técnica

  • El conjunto C de candidatos, entradas del problema.
  • Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución (no importa si es óptima o no lo es).
  • Función de selección. Informa de cuál es el elemento más prometedor para completar la solución. Éste no puede haber sido escogido con anterioridad. Cada elemento es considerado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a C\setminus S.
  • Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.
  • Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.

Funcionamiento

El algoritmo escoge en cada paso al mejor elemento x\in C posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos (C\gets C\setminus\{x\}) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados (S\cup \{x\}) produce una solución factible.

En caso de que así sea, se incluye ese elemento en S. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.

Ejemplos de algoritmos voraces

Temas relacionados

Referencias

  • Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces». Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X. 

Enlaces externos

Wikilibros

En inglés:


Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Algoritmo para la ubicación óptima — El algoritmo que se muestra a continuación nos da una idea del funcionamiento de un algoritmo voraz usado para ayudar a las empresas o multinacionales a ubicar óptimamente sus almacenes principales dependiendo de la ubicación de las ciudades… …   Wikipedia Español

  • Algoritmo de búsqueda A* — Ejemplo de aplicación del algoritmo 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… …   Wikipedia Español

  • Algoritmo de Kruskal — El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el… …   Wikipedia Español

  • Algoritmo probabilista — Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma de algunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problema planteado para cualquier distribución de los datos… …   Wikipedia Español

  • Algoritmo de Bellman-Ford — El algoritmo de Bellman Ford (algoritmo de Bell End Ford), genera el camino más corto en un Grafo dirigido ponderado (en el que el peso de alguna de las aristas puede ser negativo). El algoritmo de Dijkstra resuelve este mismo problema en un… …   Wikipedia Español

  • Problema de la mochila — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 22 de julio de 2007. También puedes… …   Wikipedia Español

  • Merkle-Hellman — (MH) fue uno de los primeros criptosistemas de llave pública y fue inventado por Ralph Merkle y Martin Hellman en 1978.[1] Aunque sus ideas eran elegantes, y mucho más simples que RSA, no tuvo el mismo éxito que éste último, debido a que MH ya… …   Wikipedia Español

  • Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… …   Wikipedia Español

  • Sucesión de Sylvester — Demostración gráfica de la convergencia de la suma a 1. Cada fila de k cuadrados de lado tiene un área total de , y todos los cuadra …   Wikipedia Español

  • Teorema de Brooks — En teoría de grafos, el teorema de Brooks establece la relación entre la valencia máxima del grafo con el número cromático: Si G es un grafo conexo que no sea completo ni un ciclo de longitud impar, entonces R. L. Brooks, (1941) …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”