El algoritmo Even-Paz es un algoritmo computacionalmente eficiente para un corte de pastel justo . Se trata de un determinado recurso heterogéneo y divisible, como un pastel de cumpleaños, y n socios con diferentes preferencias sobre diferentes partes del pastel. Permite a las n personas lograr una división proporcional .
Historia
El primer algoritmo publicado para la división proporcional de un pastel fue el último algoritmo reductor , publicado en 1948. Su complejidad en tiempo de ejecución fue O ( n ^ 2). en 1984, Shimon Even y Azaria Paz publicaron su algoritmo mejorado, cuya complejidad en tiempo de ejecución es solo O ( n log n ). [1]
Descripción
El algoritmo utiliza una estrategia de divide y vencerás, es posible lograr una división proporcional en el tiempo O ( n log n ).
- A cada participante se le pide que dibuje una línea que divida el pastel en una parte derecha e izquierda de manera que crea que la razón es ⌊ n / 2⌋: ⌈ n / 2⌉. Se requiere que los cortes no se crucen; una forma sencilla de garantizar esto es permitir solo líneas horizontales o solo líneas verticales.
- El algoritmo ordena las n líneas en orden creciente y corta el pastel en la mediana de las líneas, es decir, en la ⌊ n / 2⌋ línea. Por ejemplo, si hay 5 socios que dibujan líneas en x = 1, x = 3, x = 5, x = 8 yx = 9, entonces el algoritmo corta el pastel verticalmente en x = 5.
- El algoritmo asigna a cada una de las dos partes los socios cuya línea está dentro de esa parte, es decir, los socios que dibujaron las primeras ⌊ n / 2⌋ líneas se asignan a la parte izquierda, los demás a la parte derecha. Por ejemplo, los socios que trazaron líneas en x = 1, x = 3 y x = 5 se asignan a la parte izquierda y los demás socios se asignan a la parte derecha. Cada parte se divide de forma recursiva entre los socios asignados a ella.
Es posible probar por inducción que a cada socio que juega según las reglas se le garantiza una pieza con un valor de al menos 1 / n , independientemente de lo que hagan los demás socios.
Gracias a la estrategia de divide y vencerás, el número de iteraciones es solo O (log n ), en contraste con O ( n ) en el procedimiento Last Diminisher. En cada iteración, se requiere que cada socio haga una sola marca. Por lo tanto, el número total de puntos requeridos es O ( n log n ).
Optimalidad
Varios años después de la publicación del algoritmo Even-Paz, se demostró que todo procedimiento de división proporcional determinista o aleatoria que asigna a cada persona una pieza contigua debe utilizar acciones Ω ( n log n ). [2]
Además, todo procedimiento de división proporcional determinista debe utilizar acciones Ω ( n log n ), incluso si se permite que el procedimiento asigne a cada socio una pieza no contigua, e incluso si se permite que el procedimiento solo garantice una equidad aproximada . [3]
Estos resultados de dureza implican que el algoritmo Even-Paz es el algoritmo más rápido posible para lograr proporcionalidad total con piezas contiguas, y es el algoritmo determinista más rápido posible para lograr proporcionalidad incluso parcial e incluso con piezas desconectadas. El único caso en el que se puede mejorar es con algoritmos aleatorizados que garanticen proporcionalidad parcial con piezas desconectadas; consulte el algoritmo de Edmonds-Pruhs .
Versión aleatoria
Es posible utilizar la aleatorización para reducir el número de marcas. La siguiente versión aleatoria del procedimiento recursivo de reducción a la mitad logra una división proporcional utilizando solo consultas de marca O ( n ) en promedio. [1] La idea es que, en cada iteración, en lugar de pedir a todos los socios que hagan una marca de medio valor, solo a algunos socios se les pide que hagan tales marcas, mientras que los otros socios solo eligen la mitad que prefieren. Los socios se envían al oeste o al este según sus preferencias, hasta que el número de socios en cada lado sea n / 2. Luego se hace un corte y cada grupo de n / 2 socios divide su mitad de forma recursiva. [4]
En el peor de los casos, todavía necesitamos n -1 marcas por iteración, por lo que el número de marcas requerido en el peor de los casos es O ( n log n ). Sin embargo, en promedio, solo se requieren marcas O (log n ) por iteración; resolviendo una fórmula de recurrencia es posible mostrar que el número promedio de puntos requeridos es O ( n ).
Tenga en cuenta que el número total de consultas sigue siendo O ( n log n ), ya que cada socio tiene que seleccionar la mitad.
Referencias
- ^ a b Incluso, S .; Paz, A. (1984). "Una nota sobre el corte de la torta". Matemáticas aplicadas discretas . 7 (3): 285. doi : 10.1016 / 0166-218x (84) 90005-2 .
- ^ Sgall, Jiří; Woeginger, Gerhard J. (2007). "Sobre la complejidad del corte de la torta". Optimización discreta . 4 (2): 213–220. doi : 10.1016 / j.disopt.2006.07.003 .
- ^ Edmonds, Jeff (2006). Cortar un pastel realmente no es pan comido . Actas del Decimoséptimo Simposio Anual ACM-SIAM sobre Algoritmos Discretos - SODA '06 . págs. 271-278. doi : 10.1145 / 1109557.1109588 . ISBN 978-0898716054., Edmonds, Jeff (2011). "Cortar un pastel realmente no es pan comido". Transacciones ACM sobre algoritmos . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi : 10.1145 / 2000807.2000819 .
- ^ Este algoritmo de reducción a la mitad recursivo aleatorio es similar a un algoritmo aleatorio bien conocido para Clasificación : encontrar elelemento de rango r en una matriz de números