Even-Paz-protokollet
Even -Paz- algoritmen är en beräkningseffektiv algoritm för rättvis kakskärning . Det handlar om en viss heterogen och delbar resurs, såsom en födelsedagstårta, och n partners med olika preferenser över olika delar av tårtan. Det tillåter de n personerna att uppnå en proportionell uppdelning .
Historia
Den första publicerade algoritmen för proportionell uppdelning av en kaka var den sista förminskningsalgoritmen , publicerad 1948. Dess körtidskomplexitet var O( n ^2). 1984 Shimon Even och Azaria Paz sin förbättrade algoritm, vars körtidskomplexitet endast är O( n log n ).
Beskrivning
Algoritmen använder en dela-och-härska-strategi, det är möjligt att uppnå en proportionell uppdelning i tiden O( n log n ).
- Varje partner uppmanas att dra en linje som delar kakan i en höger och vänster del så att han tror att förhållandet är ⌊ n /2⌋:⌈ n /2⌉. Skärningarna måste vara icke-korsande; ett enkelt sätt att garantera detta är att endast tillåta horisontella linjer eller endast vertikala linjer.
- Algoritmen sorterar de n raderna i ökande ordning och skär kakan i medianen av linjerna, dvs vid den ⌊ n /2⌋:e linjen. T.ex. om det finns 5 partners som ritar linjer vid x =1, x =3, x =5, x =8 och x =9, så skär algoritmen kakan vertikalt vid x =5.
- Algoritmen tilldelar var och en av de två delarna de partner vars linje ligger inuti den delen, dvs de partner som ritade de första ⌊n / 2⌋ -linjerna tilldelas den vänstra delen, de andra till den högra delen. Till exempel, partnerna som ritade linjer vid x =1, x =3 och x =5 tilldelas den vänstra delen och de andra partnerna tilldelas den högra delen. Varje del är uppdelad rekursivt mellan de partners som tilldelats den.
Det är möjligt att bevisa genom induktion att varje partner som spelar enligt reglerna är garanterad en pjäs med ett värde på minst 1/ n , oavsett vad de andra partnerna gör.
Tack vare dela-och-härska-strategin är antalet iterationer endast O(log n ), i motsats till O( n ) i Last Diminisher-proceduren. I varje iteration måste varje partner göra ett enda märke. Följaktligen är det totala antalet poäng som krävs O( n log n ).
Optimalitet
Flera år efter publiceringen av Even–Paz-algoritmen bevisades det att varje deterministisk eller randomiserad proportionell divisionsprocedur som tilldelar varje person en sammanhängande del måste använda Ω(n log n ) -åtgärder .
Dessutom måste varje deterministisk proportionell divisionsprocedur använda Ω( n log n ) åtgärder, även om proceduren är tillåten att tilldela varje partner en icke-sammanhängande del, och även om proceduren tillåts endast garantera ungefärlig rättvisa .
Dessa hårdhetsresultat antyder att Even-Paz-algoritmen är den snabbaste möjliga algoritmen för att uppnå full proportionalitet med sammanhängande bitar, och det är den snabbaste möjliga deterministiska algoritmen för att uppnå även partiell proportionalitet och även med frånkopplade bitar. Det enda fallet där det kan förbättras är med randomiserade algoritmer som garanterar partiell proportionalitet med frånkopplade delar; se Edmonds–Pruhs algoritm .
Randomiserad version
Det är möjligt att använda randomisering för att minska antalet poäng. Följande randomiserade version av den rekursiva halveringsproceduren uppnår en proportionell division med endast O( n )-markeringsfrågor i genomsnitt. Tanken är att, i varje iteration, istället för att be alla partner att göra ett halvvärde, bara några partners uppmanas att göra sådana märken, medan de andra partnerna bara väljer vilken halva de föredrar. Partnerna skickas antingen västerut eller österut enligt deras preferenser, tills antalet partners på varje sida är n /2. Sedan görs ett snitt och varje grupp av n /2 partners delar sin halva rekursivt.
I värsta fall behöver vi fortfarande n -1 poäng per iteration så det värsta antalet poäng som krävs är O( n log n ). I genomsnitt krävs dock endast O(log n )-märken per iteration; genom att lösa en återkommande formel är det möjligt att visa att det genomsnittliga antalet poäng som krävs är O( n ).
Observera att det totala antalet frågor fortfarande är O( n log n ), eftersom varje partner måste välja en halv.
- ^ a b Even, S.; Paz, A. (1984). "En anteckning om tårtskärning" . Diskret tillämpad matematik . 7 (3): 285. doi : 10.1016/0166-218x(84)90005-2 .
- ^ Sgall, Jiří; Woeinger, Gerhard J. (2007). "Om komplexiteten i tårtskärning" . Diskret optimering . 4 (2): 213–220. doi : 10.1016/j.disopt.2006.07.003 .
- ^ Edmonds, Jeff (2006). Tårtskärning är verkligen inte en piece of cake . Handlingar från det sjuttonde årliga ACM-SIAM-symposiet om diskret algoritm - SODA '06 . s. 271–278. doi : 10.1145/1109557.1109588 . ISBN 978-0898716054 . , Edmonds, Jeff (2011). "Tårtskärning är verkligen inte en piece of cake". ACM-transaktioner på algoritmer . 7 (4): 1–12. CiteSeerX 10.1.1.146.1536 . doi : 10.1145/2000807.2000819 .
- ^ Den här randomiserade rekursiva halveringsalgoritmen liknar en välkänd randomiserad algoritm för rangordning - hitta det r -rankade elementet i en array av tal