Algoritmo Even-Paz

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de febrero de 2020; la verificación requiere 1 edición .

El algoritmo Even-Paz es un algoritmo computacionalmente eficiente para cortar el pastel de manera justa . Es para algún recurso divisible heterogéneo, como un pastel de cumpleaños, entre n participantes con diferentes preferencias por diferentes partes del pastel. El algoritmo permite que n personas obtengan una división proporcional .

Historia

El primer algoritmo publicado para la división proporcional del pastel fue el último algoritmo decreciente , publicado en 1948, que tenía complejidad . En 1984, los matemáticos israelíes Shimon Even y Azariah Paz publicaron un algoritmo mejorado cuya complejidad era [1] . $O(n^{2})$ $O(n\log n)$

Descripción

El algoritmo utiliza una estrategia de divide y vencerás y es capaz de dar una división proporcional en el tiempo . $O(n\log n)$

Se le pide a cada compañero que dibuje una línea que divida el pastel en partes izquierda y derecha para que (en su opinión) la proporción sea ⌊ n /2⌋:⌈ n /2⌉. Se requiere que las líneas no se crucen. Una manera fácil de garantizar esto es permitir solo líneas horizontales o solo líneas verticales.
El algoritmo ordena n líneas y corta el pastel a lo largo de la mediana de las líneas, es decir, a lo largo de la línea ⌊ n /2⌋. Por ejemplo, si hay 5 socios que han dibujado las líneas x = 1, x = 3, x = 5, x = 8 y x = 9, entonces el algoritmo corta el pastel verticalmente a lo largo de la línea x = 3.
El algoritmo asigna a cada una de las mitades socios cuyas líneas pertenecen a esta parte, es decir, los socios que dibujaron las primeras ⌊ n /2⌋ líneas se asignan al lado izquierdo, el resto se asignan al lado derecho. Entonces, los socios que han dibujado líneas x = 1 y x = 3 se asignan al lado izquierdo, y los otros tres socios se asignan al lado derecho. Cada una de las partes se divide recursivamente entre los socios asignados a esa parte.

Se puede demostrar por inducción que cualquier socio que juega según las reglas garantiza un valor de al menos 1/ n , independientemente del comportamiento de los otros socios.

Gracias a la estrategia divide y vencerás, el número de iteraciones es solo O(log n ), a diferencia de O( n ) para el último procedimiento reducido. En cada iteración, se requiere un token de cada socio. Por lo tanto, el número de marcadores requeridos es . $O(n\log n)$

Optimalidad

Unos años después de la publicación del algoritmo de Even-Paz, se demostró que cualquier procedimiento de división proporcional determinista o aleatoria que asigna a cada participante una pieza continua debe utilizar acciones [2] . $\Omega (n\log n)$

Además, cualquier procedimiento de división proporcional determinista debe utilizar acciones, incluso si se permite que el procedimiento dé al participante una parte que no sea continua, e incluso si se permite que el procedimiento garantice solo una equidad aproximada [3] [4] . $\Omega (n\log n)$

De estos resultados de dificultad del algoritmo se deduce que el algoritmo Even-Paz es el algoritmo más rápido para lograr una proporcionalidad total con piezas continuas, y este algoritmo es el más rápido para obtener una proporcionalidad incluso parcial e incluso con piezas discontinuas. El único caso en el que se puede mejorar el algoritmo es en algoritmos aleatorios que garanticen proporcionalidad parcial con trozos discontinuos. Ver " Algoritmo de Edmonds-Prus ".

Versión aleatoria

Puede utilizar la aleatorización para reducir el número de marcadores. La siguiente versión aleatoria del procedimiento de bisección recursiva logra la división proporcional usando solo consultas de etiquetado O( n ) en promedio [1] . La idea es que en cada iteración, en lugar de pedir a todos los participantes que marquen en el medio, solo se les pide a unos pocos socios que hagan dichos marcadores, mientras que otros socios solo eligen la mitad que prefieren. Los socios se envían al oeste o al este según su preferencia 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 recursivamente [5] .

En el peor de los casos, todavía necesitamos n -1 marcadores por iteración, por lo que el número de marcadores necesarios es O( n log n ) en el peor de los casos. Sin embargo, en el caso promedio, solo necesita marcadores O(log n ) por iteración. Al resolver la relación de recurrencia , se puede demostrar que el número de marcadores requeridos es O( n ).

Tenga en cuenta que el número total de solicitudes sigue siendo O ( n log n ), ya que cada socio debe elegir la mitad.

Notas

↑ 1 2 Pares, Paz, 1984 , p. 285.
↑ Sgall, Woeginger, 2007 , pág. 213–220.
↑ Edmonds, 2006 , pág. 271–278.
↑ Edmonds, 2011 , pág. 1–12.
↑ Este algoritmo de bisección recursiva aleatoria es similar al conocido algoritmo de clasificación aleatoria : encontrar la clasificación r de elementos en una matriz de números.

Literatura

Even S., Paz A. Una nota sobre el corte de tortas // Matemática Aplicada Discreta. - 1984. - T. 7 , núm. 3 . - doi : 10.1016/0166-218x(84)90005-2 .
Jiri Sgall, Gerhard J. Woeginger. Sobre la complejidad del corte de pasteles // Optimización discreta. - 2007. - T. 4 , núm. 2 . -doi : 10.1016/ j.disopt.2006.07.003 .
Jeff Edmonds. Cortar pasteles realmente no es pan comido. — Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos - SODA '06. - 2006. - ISBN 978-0898716054 . doi : 10.1145 / 1109557.1109588 .
Jeff Edmonds. Cortar pasteles realmente no es pan comido // ACM Transactions on Algorithms. - 2011. - T. 7 , núm. 4 . -doi : 10.1145/ 2000807.2000819 .