Partición de números codiciosos
En informática , la partición de números codiciosos es una clase de algoritmos codiciosos para la partición de números de varias vías . La entrada al 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 codiciosos 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 codicioso más simple se llama programación de lista . Simplemente procesa las entradas en el 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 que llegan los elementos.
Un algoritmo codicioso mejorado se llama programación LPT . Procesa las entradas por orden descendente de valor, de mayor a menor. Dado que necesita preordenar las entradas, solo se puede usar como un algoritmo fuera de línea . Garantiza que la suma más grande es, en la mayoría de los casos, la suma más grande óptima (mínima), y que la suma más pequeña es, al menos , la suma más pequeña (máxima) óptima. Consulte la programación de 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 clasificar 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 poner el número actual. Atravesar el árbol en primer orden en profundidad requiere solo O( n ) espacio, pero podría tomar O( k n) hora. El tiempo de ejecución se puede mejorar utilizando la heurística codiciosa: 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 codiciosa (LPT), pero luego procede a buscar mejores soluciones.
En el problema de asignación justa de artículos , hay n artículos y k personas, cada una de las cuales asigna un valor posiblemente diferente a cada artículo. El objetivo es repartir los artículos 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 del gráfico de envidia . Garantiza que la asignación es libre de envidia hasta como máximo un artículo (EF1). Además, si la instancia está ordenada (todos los agentes clasifican los elementos en el mismo orden), el resultado es EFX y garantiza a cada agente al menos su parte máxima . Si los artículos son tareas , entonces un algoritmo similar garantizaSMM. [3]
