En informática , la partición de números de múltiples vías es el problema de dividir un conjunto múltiple de números en un número fijo de subconjuntos, de modo que las sumas de los subconjuntos sean lo más similares posible. Fue presentado por primera vez por Ronald Graham en 1969 en el contexto del problema de programación de multiprocesador . [1] : sec.5 El problema se parametriza mediante un entero positivo k , y se denomina partición de números de k vías . [2] La entrada al problema es un conjunto múltiple S de números (por lo general los números enteros), cuya suma es k * T .
El asociada problema de decisión es decidir si S se puede dividir en k subconjuntos de tal manera que la suma de cada subconjunto es exactamente T . También hay un problema de optimización : encuentre una partición de S en k subconjuntos, de modo que las k sumas estén "lo más cerca posible". El objetivo de optimización exacto se puede definir de varias formas:
- Minimice la diferencia entre la suma más grande y la suma más pequeña. Este objetivo es común en artículos sobre particiones numéricas de múltiples vías, así como en artículos que se originan en aplicaciones físicas. [2]
- Minimice la suma más grande. Este objetivo es equivalente a un objetivo para la programación de máquinas idénticas . Hay k procesadores idénticos y cada número en S representa el tiempo necesario para completar un trabajo de un solo procesador. El objetivo es dividir los trabajos entre los procesadores de modo que se minimice el tiempo de espera (el tiempo de finalización del último trabajo).
- Maximice la suma más pequeña. Este objetivo corresponde a la aplicación de la asignación justa de partidas , particularmente la participación maximin . También aparece en los problemas de manipulación de la votación [3] y en la secuenciación de las acciones de mantenimiento de los motores de aviones de turbinas de gas modulares. [4]
Estas tres funciones objetivo son equivalentes cuando k = 2, pero todas son diferentes cuando k ≥3. [5]
Todos estos problemas son NP-hard , [6] pero existen varios algoritmos que lo resuelven eficientemente en muchos casos.
Algunos problemas estrechamente relacionados son:
- El problema de la partición : un caso especial de partición numérica de múltiples vías en el que el número de subconjuntos es 2.
- El problema de las 3 particiones : un problema diferente y más difícil, en el que el número de subconjuntos no se considera un parámetro fijo, sino que está determinado por la entrada (el número de conjuntos es el número de enteros dividido por 3).
- El problema del embalaje en contenedores : un problema dual en el que la suma total de cada subconjunto está limitada, pero k es flexible; el objetivo es encontrar una partición con la menor k posible . Los objetivos de optimización están estrechamente relacionados: el número óptimo de bins de tamaño d es como máximo k , si si el tamaño óptimo de un subconjunto más grande en una partición k es como máximo d . [7]
- El problema de programación de máquinas uniformes : un problema más general en el que diferentes procesadores pueden tener diferentes velocidades.
Algoritmos de aproximación
Existen varios algoritmos que obtienen una aproximación garantizada de la solución óptima en tiempo polinomial. Existen diferentes algoritmos de aproximación para diferentes objetivos.
Minimizando la mayor suma
La razón de aproximación en este contexto es la suma más grande en la solución devuelta por el algoritmo, dividida por la suma más grande en la solución óptima (la razón es mayor que 1). La mayoría de los algoritmos a continuación se desarrollaron para la programación de máquinas idénticas .
- La partición codiciosa de números (también llamada el mayor tiempo de procesamiento en la literatura de programación) recorre los números y coloca cada número en el conjunto cuya suma actual es más pequeña. Si los números no están ordenados, entonces el tiempo de ejecución es y la relación de aproximación es como máximo . Ordenar los números aumenta el tiempo de ejecución ay mejora la relación de aproximación a 7/6 cuando k = 2, yen general. Si los números se distribuyen uniformemente en [0,1], entonces la relación de aproximación es como máximo casi seguro , y a la espera.
- El método de diferenciación más grande (también llamado algoritmo Karmarkar-Karp ) ordena los números en orden descendente y reemplaza repetidamente los números por sus diferencias. La complejidad del tiempo de ejecución es. En el peor de los casos, su relación de aproximación es similar: como máximo 7/6 para k = 2, y como máximoen general. Sin embargo, en el caso promedio, funciona mucho mejor que el algoritmo codicioso: para k = 2, cuando los números se distribuyen uniformemente en [0,1], su relación de aproximación es como máximoa la espera. También funciona mejor en experimentos de simulación.
- El algoritmo Multifit utiliza una búsqueda binaria combinada con un algoritmo para empaquetar contenedores . En el peor de los casos, su intervalo de espera es como máximo 8/7 para k = 2, y como máximo 13/11 en general.
Se han desarrollado varios esquemas de aproximación de tiempo polinomial (PTAS):
- Graham [1] : sec.6 presentó el siguiente algoritmo. Para cualquier entero r> 0 , elija los r números más grandes en S y particínelos de manera óptima. Luego asigne los números restantes arbitrariamente. Este algoritmo tiene una relación de aproximación y corre a tiempo .
- Sahni [8] presentó un PTAS que alcanza (1 + ε) OPT en el tiempo. Es un FPTAS si k es fijo. Para k = 2, el tiempo de ejecución mejora a. El algoritmo utiliza una técnica llamada partición de intervalo .
- Hochbaum y Shmoys [7] presentaron los siguientes algoritmos, que funcionan incluso cuando k es parte de la entrada.
- Para cualquier r > 0, un algoritmo con una relación de aproximación como máximo (6/5 + 2 - r ) en el tiempo.
- Para cualquier r > 0, un algoritmo con una relación de aproximación como máximo (7/6 + 2 - r ) en el tiempo.
- Para cualquier ε > 0, un algoritmo con una relación de aproximación como máximo (1 + ε) en el tiempo. Este es un PTAS .
Maximizando la suma más pequeña
La razón de aproximación en este contexto es la suma más pequeña en la solución devuelta por el algoritmo, dividida por la suma más pequeña en la solución óptima (la razón es menor que 1).
- Para la partición codiciosa de números , si los números no están ordenados, la relación de aproximación del peor de los casos es 1 / k . [4] Ordenar los números aumenta la relación de aproximación a 5/6 cuando k = 2, yen general, y es estrecho. [9]
- Woeginger [4] presentó un PTAS que alcanza un factor de aproximación de a tiempo , dónde una enorme constante que es exponencial en el factor de aproximación requerido ε. El algoritmo utiliza el algoritmo de Lenstra para la programación lineal de enteros .
Otras funciones objetivas
Sea s i (para i entre 1 y k ) la suma del subconjunto i en una partición dada. En lugar de minimizar la función objetivo max ( s i ), se puede minimizar la función objetivo max ( f ( s i )), donde f es cualquier función fija. De manera similar, se puede minimizar la suma de la función objetivo ( f ( s i )), o maximizar min (f ( s i )), o maximizar la suma ( f ( s i )). Alon, Azar, Woeginger y Yadid [10] presentaron un PTAS general, que funciona para cualquier f que satisfaga una determinada condición de continuidad, y sea convexo (para los problemas de minimización) o cóncavo (para los problemas de maximización). Su algoritmo generaliza los PTAS-s de Sanhi, Hochbaum y Shmoys y Woeginger. El tiempo de ejecución de su PTAS es lineal en n , pero exponencial en la precisión de aproximación. Muestran que, para algunas funciones f que no satisfacen estas condiciones, no existe PTAS a menos que P = NP .
Algoritmos exactos
Hay algoritmos exactos , que siempre encuentran la partición óptima. Dado que el problema es NP-hard, tales algoritmos pueden llevar un tiempo exponencial en general, pero pueden ser prácticamente utilizables en ciertos casos.
- La partición de números de tiempo pseudopolinomial toma O ( n ( k - 1) m k - 1 ) de memoria, donde m es el número más grande en la entrada. Es práctico solo cuando k = 2, o cuando k = 3 y las entradas son números enteros pequeños. [11]
- El algoritmo codicioso completo (CGA) considera todas las particiones mediante la construcción de un árbol k - ario . Cada nivel del árbol corresponde a un número de entrada, donde la raíz corresponde al número más grande, el nivel inferior al siguiente número más grande, etc. Cada una de las k ramas corresponde a un conjunto diferente en el que se puede colocar el número actual . Atravesar el árbol en orden de profundidad requiere solo O ( n ) espacio, pero puede tomar O ( k n ) tiempo. El tiempo de ejecución se puede mejorar utilizando una 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 encontrada por la partición numérica codiciosa , pero luego procede a buscar mejores soluciones.
- El algoritmo completo de Karmarkar-Karp (CKK) considera todas las particiones mediante la construcción de un árbol de grados. Cada nivel corresponde a un par de k -tuplas, y cada uno de losramas corresponde a una forma diferente de combinar estas k -tuplas. Este algoritmo encuentra primero la solución encontrada por el método de diferenciación más grande , pero luego procede a encontrar mejores soluciones. Para k = 2 y k = 3, CKK se ejecuta sustancialmente más rápido que CGA en instancias aleatorias. La ventaja de CKK sobre CGA es mucho mayor en el último caso (cuando existe una partición igual) y puede ser de varios órdenes de magnitud. En la práctica, con k = 2, CKK puede resolver problemas de tamaño arbitrario si los números tienen como máximo 12 dígitos significativos ; con k = 3, como máximo 6 dígitos significativos. [12] CKK también puede ejecutarse como un algoritmo en cualquier momento : primero encuentra la solución KK y luego encuentra soluciones progresivamente mejores a medida que el tiempo lo permite (posiblemente requiriendo tiempo exponencial para alcanzar la optimización, en los peores casos). [13] Para k ≥ 4, CKK se vuelve mucho más lento y CGA funciona mejor.
- El particionamiento numérico recursivo (RNP) utiliza CKK para k = 2, pero para k > 2 divide de forma recursiva S en subconjuntos y divide k en mitades. Funciona mucho mejor que CKK. [11]
- Korf, Schreiber y Moffitt presentaron algoritmos híbridos, combinando CKK, CGA y otros métodos del problema de la suma de subconjuntos y el problema del empaquetado de contenedores para lograr un rendimiento aún mejor. [14] [15] [16] [17]
Reducción del embalaje en contenedores
El problema del embalaje de contenedores tiene muchas soluciones rápidas. Se puede utilizar un solucionador de BP para encontrar una partición numérica óptima. [18] La idea es utilizar la búsqueda binaria para encontrar la configuración óptima. Para inicializar la búsqueda binaria, necesitamos un límite inferior y un límite superior:
- Algunos límites inferiores en el Makingpan son: (suma S ) / k - el valor promedio por subconjunto, s 1 - el número más grande en S , y s k + s k + 1 - el tamaño de un contenedor en la partición óptima de solo los números k +1 más grandes.
- Se pueden alcanzar algunos límites superiores ejecutando algoritmos heurísticos, como el algoritmo codicioso o KK.
Dado un límite inferior y superior, ejecute el solucionador de BP con un tamaño de contenedor medio: = (inferior + superior) / 2.
- Si el resultado contiene más de k contenedores, entonces el intervalo óptimo debe ser mayor: establecer de menor a medio y repetir.
- Si el resultado contiene como máximo k contenedores, entonces el intervalo óptimo puede ser más pequeño, más alto a medio y repetir.
Variantes
En el problema de partición de números balanceados , la cardinalidad de cada subconjunto debe ser piso ( n / k) o techo (n / k), es decir, la cardinalidad de todos los subconjuntos debe ser la misma hasta 1. [19]
Una variante reciente es la partición numérica multidimensional de múltiples vías. [20]
Aplicaciones
Una aplicación del problema de la partición es la manipulación de las elecciones . Suponga que hay tres candidatos (A, B y C). Se debe elegir a un solo candidato utilizando la regla del voto con veto, es decir, cada votante vetos a un solo candidato y el candidato con menos vetos gana. Si una coalición quiere asegurarse de que C sea elegido, debe dividir sus vetos entre A y B para maximizar el menor número de vetos que cada uno de ellos obtiene. Si los votos están ponderados, entonces el problema puede reducirse al problema de la partición y, por lo tanto, puede resolverse de manera eficiente utilizando CKK. Para k = 2, lo mismo es cierto para cualquier otra regla de votación que se base en la puntuación. Sin embargo, para k > 2 y otras reglas de votación, se requieren algunas otras técnicas. [3]
Referencias
- ↑ a b Graham, Ron L. (1 de marzo de 1969). "Límites de anomalías de sincronización de multiprocesamiento" . Revista SIAM de Matemática Aplicada . 17 (2): 416–429. doi : 10.1137 / 0117039 . ISSN 0036-1399 .
- ^ a b Mertens, Stephan (2006), "El problema difícil más fácil: Partición numérica" , en Allon Percus; Gabriel Istrate; Cristopher Moore (eds.), Complejidad computacional y física estadística , Oxford University Press US, p. 125, arXiv : cond-mat / 0310317 , Bibcode : 2003cond.mat.10317M , ISBN 978-0-19-517737-4
- ^ a b Walsh, Toby (11 de julio de 2009). "¿Dónde están los problemas de manipulación realmente difíciles? La fase de transición en la manipulación de la regla del veto" . Actas de la 21ª Conferencia Internacional de Jont sobre Inteligencia Artificial . IJCAI'09. Pasadena, California, EE.UU .: Morgan Kaufmann Publishers Inc .: 324–329.
- ^ a b c Woeginger, Gerhard J. (1 de mayo de 1997). "Un esquema de aproximación de tiempo polinomial para maximizar el tiempo mínimo de finalización de la máquina" . Cartas de investigación operativa . 20 (4): 149-154. doi : 10.1016 / S0167-6377 (96) 00055-7 . ISSN 0167-6377 .
- ^ Korf, Richard Earl (25 de agosto de 2010). "Funciones objetivas para el particionamiento numérico multidireccional" . Tercer Simposio Anual de Búsqueda Combinatoria .
- ^ Garey, Michael R .; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de NP-Completeness . WH Freeman and Company. pag. 238 . ISBN 978-0716710448.
- ^ a b Hochbaum, Dorit S .; Shmoys, David B. (1 de enero de 1987). "Utilización de algoritmos de aproximación dual para la programación de resultados teóricos y prácticos de problemas" . Revista de la ACM . 34 (1): 144-162. doi : 10.1145 / 7531.7535 . ISSN 0004-5411 . S2CID 9739129 .
- ^ Sahni, Sartaj K. (1 de enero de 1976). "Algoritmos para programar tareas independientes" . Revista de la ACM . 23 (1): 116-127. doi : 10.1145 / 321921.321934 . ISSN 0004-5411 .
- ^ Csirik, János; Kellerer, Hans; Woeginger, Gerhard (1 de junio de 1992). "El límite LPT exacto para maximizar el tiempo mínimo de finalización" . Cartas de investigación operativa . 11 (5): 281-287. doi : 10.1016 / 0167-6377 (92) 90004-M . ISSN 0167-6377 .
- ^ Alon, Noga; Azar, Yossi; Woeginger, Gerhard J .; Yadid, Tal (1998). "Esquemas de aproximación para la programación en máquinas paralelas" . Diario de programación . 1 (1): 55–66. doi : 10.1002 / (SICI) 1099-1425 (199806) 1: 1 <55 :: AID-JOS2> 3.0.CO; 2-J . ISSN 1099-1425 .
- ^ a b Korf, Richard E. (2009). Partición numérica multidireccional (PDF) . IJCAI .
- ^ Korf, Richard E. (20 de agosto de 1995). "De soluciones aproximadas a óptimas: un estudio de caso de partición numérica" . Actas de la XIV Conferencia Conjunta Internacional sobre Inteligencia Artificial - Volumen 1 . IJCAI'95. Montreal, Quebec, Canadá: Morgan Kaufmann Publishers Inc .: 266–272. ISBN 978-1-55860-363-9.
- ^ Korf, Richard E. (1 de diciembre de 1998). "Un algoritmo completo en cualquier momento para la partición numérica" . Inteligencia artificial . 106 (2): 181-203. doi : 10.1016 / S0004-3702 (98) 00086-1 . ISSN 0004-3702 .
- ^ Korf, Richard E. (16 de julio de 2011). "Un algoritmo de partición de números de múltiples vías recursivo híbrido" . Actas de la Vigésima Segunda Conferencia Conjunta Internacional sobre Inteligencia Artificial - Volumen Uno . IJCAI'11. Barcelona, Cataluña, España: AAAI Press: 591–596. ISBN 978-1-57735-513-7.
- ^ Schreiber, Ethan L .; Korf, Richard E. (27 de julio de 2014). "Debilitamiento iterativo en caché para una partición numérica multidireccional óptima" . Actas de la XXVIII Conferencia AAAI sobre Inteligencia Artificial . AAAI'14. Ciudad de Québec, Québec, Canadá: AAAI Press: 2738–2744.
- ^ Richard E. Korf, Ethan L. Schreiber y Michael D. Moffitt (2014). "Partición numérica secuencial óptima de varias direcciones" (PDF) .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Schreiber, Ethan L .; Korf, Richard E .; Moffitt, Michael D. (25 de julio de 2018). "Partición óptima de números de múltiples vías" . Revista de la ACM . 65 (4): 24: 1–24: 61. doi : 10.1145 / 3184400 . ISSN 0004-5411 . S2CID 63854223 .
- ^ Schreiber, Ethan L .; Korf, Richard E. (3 de agosto de 2013). "Mejora de la terminación de contenedores para un óptimo empaquetado de contenedores y partición de números" . Actas de la Vigésima Tercera Conferencia Conjunta Internacional sobre Inteligencia Artificial . IJCAI '13. Beijing, China: AAAI Press: 651–658. ISBN 978-1-57735-633-2.
- ^ Yakir, Benjamin (1 de febrero de 1996). "El algoritmo de diferenciación LDM para particionamiento: una prueba de una conjetura de Karmarkar y Karp" . Matemáticas de la investigación operativa . 21 (1): 85–99. doi : 10.1287 / moor.21.1.85 . ISSN 0364-765X .
- ^ Pop, Petrică C .; Matei, Oliviu (1 de noviembre de 2013). "Un enfoque de algoritmo memético para resolver el problema de partición de números multidimensional de múltiples vías" . Modelado matemático aplicado . 37 (22): 9191–9202. doi : 10.1016 / j.apm.2013.03.075 . ISSN 0307-904X .