Diferencia entre revisiones de «Algoritmo voraz»

← Ir a diferencia anterior Ir a siguiente diferencia →

Contenido eliminado Contenido añadido

En renglón

Revisión del 21:34 26 may 2009

Un algoritmo voraz (también conocido como ávido o devorador) 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.

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 rechazado o 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.

Una vez finalizado el bucle, el algoritmo comprueba si el conjunto $S$ es una solución o no, devolviendo el resultado apropiado en cada caso. El algoritmo se muestra a continuación:

 // Esquema general de un algoritmo voraz
 
 función  $\mathrm {voraz} (C)\,$ 
   // $C$  es el conjunto de candidatos//
    $S\gets \emptyset$ 
   mientras  $C\neq \emptyset$  y no solución(S) hacer
      $x\gets \mathrm {seleccionar} (C)$ 
      $C\gets C\setminus \{x\}$ 
     si  $\mathrm {factible} (S\cup \{x\})$  entonces
        $S\gets S\cup \{x\}$ 
   si solución(S) entonces
     devolver  $S\,$  // $S$  es una solución//
   si no
     devolver  $\emptyset$  //No hay soluciones//

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 alberga un libro o manual sobre Algoritmia/Algoritmos voraces.

En inglés:

@@ Línea 5: / Línea 5: @@
 Cada conjunto <math>S</math> 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 <math>S</math> es una ''solución óptima''.
-=== Elementos de los que consta la técnica ===hola
+=== Elementos de los que consta la técnica ===
 *El conjunto <math>C</math> 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).