Úloha 2.u4: Vyrovnání dluhů (3 b)

Zadáno v čísle 23.2.

Řešeno v čísle 23.4.

Zadání

Pět kamarádů spolu vyrazilo na akční hru Hranostaj. Verča zaplatila startovné, Tadeáš koupil lístek pro čtyři z nich do Ferdinandova, Olda si koupil svoji jízdenku a zaplatil také zákusky v cukrárně, Luboš se postaral o účet v restauraci. No a na Evelínu zbylo vymyslet, jak se co nejjednodušeji vyrovnat.

Obecněji máme $n$ kamarádů a $m$ dluhů, což jsou trojice (kdo, komu, kolik dluží). Nalezněte co nejlepší horní odhad na počet transakcí, který bude pro daná $n$ a $m$ na vyrovnání vždy stačit. Pak vymyslete co nejrychlejší algoritmus, který takové vyrovnání nalezne. Pokud dokážete, že úloha nalezení vyrovnání s minimálním počtem transakcí je NP-úplná1, bonusové body vás neminou!


1) O NP-úplných problémech byla přednáška na soustředění. Jinak si můžete přečíst např. kuchařku KSP: http://ksp.mff.cuni.cz/kucharky/tezke-problemy/

Řešení

Jako první si ujasníme, že se úloha skládá ze tří různých otázek. První otázka se týká horního odhadu na počet transakcí, jenom ze znalosti $n$ a $m$, bez znalosti konkrétní instance problému. Druhá otázka spočívá v nalezení algoritmu, který nalezne vyrovnání (posloupnost transakcí) pro konkrétní instanci problému. Tento algoritmus by měl najít vyrovnání, které není horší než námi nalezený horní odhad na počet transakcí. Dále by tento algoritmus měl být co nejrychlejší. Pokud jde o rychlost algoritmu, tak nás již nezajímá počet transakcí, ale počet kroků výpočtu, které k nalezení řešení vedou. Zatímco při stanovování horního odhadu jsme museli být velmi precizní, tak při určování časové složitosti algoritmu je vhodné použít asymptotickou notaci, která nám umožní zanedbat inkrementální a multiplikativní konstanty. Třetí otázka se týká NP-úplnosti hledání vyrovnání dluhů na co nejnižší počet transakcí. Jedná se o problém, kde je opravdu potřeba najít vyrovnání na co nejnižší počet transakcí pro konkrétní instanci problému – nestačí tu tedy již dodržení limitu pro obecný problém jen ze znalosti $n$ a $m$.

Tvrdíme, že nejlepší horní odhad na vyrovnání $m$ dluhů mezi $n$ lidmi je menší z čísel $n-1$ a $m$. Pokud je dluhů opravdu málo, tak se druhy můžou vyrovnat mezi stejnými dvojicemi lidí, jako vznikly (transakcí bude $m$). Jinak předpokládejme, že dluhů je více než lidí. Pak je výhodné pro každého člověka spočítat, kolik peněz celkem dluží, kolik peněz je mu celkem dluženo a jaká je výsledná bilance. Následně můžeme sestavit řetěz předávání peněz, kde všichni lidé, kteří v souhrnu dluží peníze, budou před lidmi s kladnou pohledávkou. První člověk pošle druhému peníze, které dluží zbytku skupiny v součtu. Druhý člověk k tomu přidá svoji výslednou dluženou částku a součet pošle dál. Když se peníze dostanou k věřitelům, začnou si z těchto peněz postupně brát tolik, kolik mají v součtu dostat, a zbytek peněz, které jim dorazily, posílat zbytku věřitelů. Až nakonec k poslednímu věřiteli dorazí přesně tolik peněz, kolik měl v součtu dostat. Počet transakcí v tomto řetězu je $n-1$.

Tento horní odhad je nejlepší možný. Pokud jednomu člověku všichni kamarádi dluží 1 Kč, pak aby proběhlo vyrovnání, musí mít každý dlužník odchozí transakci. Těchto transakcí bude $n-1 = m$.

Algoritmus pro nalezení vyrovnání plyne z našeho zdůvodnění horního odhadu. Nejprve pro každého člověka sečteme všechny jeho dluhy a pohledávky, což nám zabere $O(n+m)$ kroků. Pak roztřídíme lidi podle znaménka součtu do dvou seznamů, což nám zabere $O(n)$ kroků. Nyní začneme vypisovat lidi ze seznamu dlužníků a jejich dluhy postupně přičítáme k částce, kterou si musí mezi sebou předávat. Nakonec budeme vypisovat lidi z druhého seznamu, přičemž od částky, kterou si musí předávat, budeme odčítat jejich pohledávky. To se opět vejde do $O(n)$ kroků. Časová složitost našeho algoritmu tudíž je $O(n+m)$.

Nyní k bonusové otázce. Na podrobné představení NP-úplnosti zde nemáme prostor, lepší vhled do problematiky můžete získat např. v již zmiňované kuchařce KSP. Připomeňme jen, že NP-úplné problémy jsou právě ty, které jsou ve třídě NP (to znamená, že se dají vyřešit na Nedeterministickém Turingově stroji v Polynomiálním čase) a zároveň jsou NP-těžké (to znamená, že se na ně každý problém v NP dá převést – vyřešit pomocí nich s tím, že se jeho vstup při převodu může zvětšit jen polynomiálně).

Hodí se umět o problému dokázat, že je NP-úplný, protože když se nám to podaří, můžeme se přestat snažit nalézt efektivní (tj. polynomiální) algoritmus, který jej řeší. Ne že by někdo s jistotou věděl, že to nejde. Slavná otázka jestli $\mathrm{P} = \mathrm{NP}$ (P je třída problémů řešitelných v polynomiálním čase na obyčejném Turingově stroji) stále není vyřešená. Ale snažilo se o to už hodně lidí a všeobecně se má za to, že $\mathrm{P} \neq \mathrm{NP}$.

Jak dokážeme o problému nalezení minimálního počtu transakcí, že je NP-úplný? Uvažme jinou verzi problému: pro daných $n$ lidí a $m$ dluhů nalézt vyrovnání na právě $t$ transakcí, pokud existuje. Označme si tento problém Tr. Původní problém pomocí Tr dokážeme vyřešit jednoduše tak, že budeme zkoušet počet transakcí $t = 1, 2, \ldots $ a skončíme, jakmile nalezneme první vyrovnání. A naopak – jestli lze najít vyrovnání na právě $t$ transakcí zjistíme z jednoho zavolání minimalizace. Pokud je minimální počet transakcí větší než $t$, vyrovnání na $t$ transakcí nalézt nelze. Naopak pokud je minimum menší než $t$, vždy můžeme přidat další transakce předávající 0 peněz.

Jelikož umíme problém převést tam i zpět, je minimalizace počtu transakcí NP-úplná právě tehdy, když je NP-úplný Tr.

Nyní dokážeme, že Tr je NP-úplný. Zaprvé je v NP – pokud nám někdo ukáže, jak by prováděl $t$ transakcí (dá nám tzv. „certifikát“), dokážeme snadno v polynomiálním čase ověřit, jestli tyto transakce zajistí vyrovnání (pro každého člověka spočítáme, jestli změna stavu jeho účtu odpovídá vyžadované). Zadruhé potřebujeme dokázat, že je NP-těžký. To uděláme tak, že na něj převedeme známý NP-úplný problém zvaný problém dvou loupežníků: Dva loupežníci si „vypůjčili“ $k$ předmětů, které mají obecně různé hodnoty. Existuje rozdělení předmětů na dvě hromádky tak, aby součty hodnot předmětů v nich byly stejné?

Převod dvou loupežníků na Tr: Za každý předmět a každou hromádku si vytvoříme jednoho člověka. Dlužit budou lidé odpovídající předmětům polovinu své hodnoty každé ze dvou hromádek. Takto každý předmět celkem zaplatí svou hodnotu a každá hromádka celkem dostane polovinu hodnoty všech předmětů. Abychom našli rozdělení předmětů mezi hromádky, spustíme Tr$t = k$. Máme k dispozici jen jednu transakci na předmět a všechny peníze z předmětů musí dotéct do hromádek (ale nemusí přitéct přímo, mohou to vzít přes jiné předměty a utvořit tak jakési stromy transakcí). Pokud tedy Tr nalezne vyrovnání, získáme správné rozdělení předmětů na hromádky a vyřešíme problém dvou loupežníků. Pokud Tr vyrovnání nenalezne, neexistuje ani správné rozdělení předmětů na hromádky.

Převedli jsme problém dvou loupežníků na Tr, tím jsme dokončili důkaz jeho NP-úplnosti, a díky tomu víme, že i minimalizace počtu transakcí je NP-úplná.

Martin a Matěj