En informática , la partición de números voraz es una clase de algoritmos voraces para la partición de números de múltiples vías . La entrada del algoritmo es un conjunto S de números y un parámetro k . La salida requerida es una partición de S en k subconjuntos, de modo que las sumas en los subconjuntos sean lo más iguales posible. Los algoritmos voraces procesan los números secuencialmente e insertan el siguiente número en un contenedor en el que la suma de los números es actualmente la más pequeña.
El algoritmo de partición voraz más simple se denomina programación de listas . Simplemente procesa las entradas en cualquier orden en que llegan. Siempre devuelve una partición en la que la suma más grande es, en la mayoría de los casos, la suma más grande óptima (mínima). [1] Esta heurística se puede utilizar como un algoritmo en línea , cuando no se puede controlar el orden en el que llegan los elementos.
Un algoritmo voraz mejorado se denomina programación LPT . Procesa las entradas en orden descendente de valor, de mayor a menor. Dado que necesita preordenar las entradas, solo se puede utilizar como un algoritmo fuera de línea . Garantiza que la suma más grande sea, como máximo, la suma más grande óptima (mínima), y que la suma más pequeña sea, como mínimo, la suma más pequeña óptima (máxima). Consulte la programación LPT para obtener más detalles.
El algoritmo voraz completo (CGA) es un algoritmo exacto , es decir, siempre encuentra una solución óptima. Funciona de la siguiente manera. Después de ordenar los números en orden descendente (como en LPT), construye un árbol k -ario. Cada nivel corresponde a un número, y cada una de las k ramas corresponde a un conjunto diferente en el que se puede colocar el número actual. Recorrer el árbol en orden de profundidad requiere solo O( n ) espacio, pero podría tomar O( k n ) tiempo. El tiempo de ejecución se puede mejorar utilizando la heurística voraz: en cada nivel, desarrolle primero la rama en la que se coloca el número actual en el conjunto con la suma más pequeña. Este algoritmo encuentra primero la solución voraz (LPT), pero luego procede a buscar mejores soluciones.
Se pueden utilizar varias heurísticas adicionales para mejorar el tiempo de ejecución: [2]
En el problema de asignación justa de elementos , hay n elementos y k personas, cada una de las cuales asigna un valor posiblemente diferente a cada elemento. El objetivo es dividir los elementos entre las personas de la manera más justa posible. La generalización natural del algoritmo de partición de números codiciosos es el algoritmo de grafo de envidia . Garantiza que la asignación esté libre de envidia hasta un elemento como máximo (EF1). Además, si la instancia está ordenada (- todos los agentes clasifican los elementos en el mismo orden), entonces el resultado es EFX y garantiza a cada agente al menos su parte maximin . Si los elementos son tareas domésticas , entonces un algoritmo similar garantiza MMS. [3]
