Přináším vám třetí pokračování (snad ne) nekonečného seriálu „Spravedlivé nalosování soutěže“ (1. díl, 2. díl), obrňte se trpělivostí 🙂 . Jako v každém správném seriálu, nejprve shrnu minulý děj: kvůli ohromnému počtu možností nalosování soutěže nelze použít ani hrubou výpočetní sílu k prohledání a vyhodnocení všech variant. Soutěž je ale možné nalosovat náhodně a případně losování mnohokrát opakovat, dokud není splněna nějaká podmínka (= dokud se nám nalosování nelíbí). Celkem slibným způsobem se mi jevila metoda „prohledávání sítě“. O ní bude tento článek.
Metodu prohledávání sítě lze vysvětlit následovně. Představte si, že máte projít lesem protkaným sítí stezek. Není to bludiště, všechny stezky vycházejí ze „Startu“ a ústí v „Cíli“. Na každé křižovatce se stezka rozděluje. Na každé cestě jsou položené peníze, úkolem je cestou do cíle nasbírat co nejvíce.
Jedna z možných strategií je ta, že projdete všechny cesty vedoucí z daného uzlu do příštího uzlu, podíváte se, jaká částka kde leží, a potom se dáte tou cestou, kde je zisk nejvyšší. Z uzlu A1 tedy dojdete do B1 a zjistíte, že za tuto cestu je jen jedna koruna. Vrátíte se do A1 a vydáte se do B2. Tato cesta je za 10, takže první úsek je A1-B2 a ziskem je 10. V bodě B2 jsou zase dvě možnosti. Nejprve vyzkoušíte B2-C3 a zjistíte, že je za 10. Vrátíte se do B2 a vydáte se do C4. Zklamání, jen za korunu, takže se musíte vrátit do B2 a poté postoupit do C3. Zatím jste ušli A1-B2-C3 se ziskem 20 korun. Z C3 lze jít do D5 a do D6. Prozkoumáte obě možnosti a zjistíte, že jsou obě za 10. Zde musí nastoupit další pravidlo, jinak dopadnete jak Buridanův osel. Pravidlo pro tuto situaci je například „dát se vpravo“, takže do D6 a do cíle. Celá trasa tedy byla A1-B2-C3-D6. Jednoduché, ne?
Popsané prohledávání je jen do bezprostředně následujícího uzlu, tj. do hloubky 1. Pokud máme dost času, můžeme hledat i hlouběji, ale nemusí to být praktické, neboť složitost narůstá. Při hledání do hloubky 1 musíme urazit vždy 5 jednotek vzdálenosti (z A1 do B1 a zpět, z A1 do B2 a zpět, a poté z A1 do vybrané z B1, B2). Při postupu do úrovně C je to tedy 10 jednotek vzdálenosti. Při prohledávání do úrovně dvě jsem napočítal 14. Zde je nutné poměřovat možný zisk s vynaloženým úsilím. Spojnice C2-D3 je ohodnocena 100 korunami, ale dostat se k ní dá jen po A1-B1 za korunu a B1-C2 také za korunu. Tuto „odměnu“ tak lze objevit jen při hledání do hloubky 3.
Popsaný způsob lze použít i při generování matice letů. Prvního pilota dám na první startoviště v první skupině (A1). Druhého pilota mohu přidat k prvnímu do první skupiny (B1) nebo ho mohu dát do druhé skupiny (B2). Musím jen vědět, co je výhodnější. Řekněme, že (B2) je lepší. Třetího pilota mohu dát opět do první (C3) nebo čtvrté skupiny (C4). Lepší se jeví (C3). Opakuji pro čtvrtého pilota, opět mám dvě možnosti (D5) a (D6), tentokrát jsou rovnocenné, musí nastoupit dodatečné pravidlo.
Důležité je, že jakmile se rozhodnu pro jednu možnost, ty ostatní jakoby přestaly existovat, nikdy už se nedovím, co by bylo, kdybych se rozhodl jinak. Tato metoda tak nenajde nejlepší cestu (viz C2-D3 za 100), nýbrž vždy „jen“ tu nejlepší v daný okamžik. Ostatně v životě se také musíme rozhodovat tady a teď 😉 .
V uvedeném příkladu nám někdo na cestičky položil peníze, takže jsme věděli, kterou cestou se dát. Při vytváření startovací matice je to složitější, protože o tom, kterou cestou se dát, rozhoduje, kudy jsme šli dříve. Kritériem pro umístění pilota je to, kolikrát letí „každý s každým“ v (dílčí) matici sestavené už v předchozích krocích. Je to hodně počítání, pro větší počty skupin a zejména pilotů to pro netrpělivé typy, jako jsem já, „k nevydržení“.
Níže je ke stažení excelový soubor, který nyní popíši.
Soubor má dvě makra, Ctrl-Shift-U vymaže všechna vypočtená data, Ctrl-Shift-G vygeneruje startovací matici. Program potřebuje znát počet startovišť, počet skupin v kole a počet kol. Počet pilotů se uvažuje plný, tj. všechna startoviště ve všech skupinách jsou zaplněná. Dalším vstupním údajem jsou váhy pro jednotlivá opakování. Jak je ukázáno, skončil jsem nakonec dokonce u 4. mocniny, přičemž 0 má stejnou váhu jako 3. S váhami si lze hrát dlouho 😉 , domnívám se, že pro každou kombinaci počtu startovišť, skupin a kol mohou být optimální váhy jiné. Program uvažuje pouze tolik vah, kolik je kol.
Po proběhnutí výpočtu se ukáže takováto obrazovka. Vedle vah jsou počty opakování. Dále je startovací matice (K1-S1 znamená 1. kolo a 1. skupina, L1 je první startoviště) a úplně vpravo potom tabulka kdo kolikrát s kým. Piloti jsou P1 až P6. Pro sledování běhu programu jsou důležitá i čísla nahoře – čas, po který program běží (po skončení běhu čas, po který běžel) a ukazatel, které kolo a kterého pilota právě algoritmus řeší. V uvedeném příkladu byl program hotov asi za 0.1 sekundy, ale třeba úlohu s 12 startovišti a 6 skupinami (tj. 72 pilotů) pro dvě kola řešil přes 20 minut! Ale mám hloupý počítač 🙁 .
Pravidlo pro nakládání se dvěma rovnocennými možnosti, jak umístit pilota, je následující: vybere se ta s menším startovištěm (například pokud se může pilot X dát do 2. skupiny na 3. startoviště nebo do 3. skupiny na 2. startoviště, vybere se druhá možnost). Pro následující kombinace je tak k dispozici více místa.
Pro můj oblíbený případ 18 pilotů ve třech skupinách spočítal program pro šest letů tyto výsledky. Povšimněte si, že 4x proti sobě neletí nikdo. Pro náhodné losování je v průměru 8 dvojic, které proti sobě letí 4x, vyloučené nejsou ani pětinásobné souboje. Pro opakované losování (výběr nejlepší varianty z 1000 losování) byly „čtyřnásobné“ dvojice čtyři.
K dokonalosti má ale i tato metoda daleko, i když se mi zdá lepší, v některých případech, než losování. Nápadů, co by se ještě dalo vyzkoušet, mám ovšem hodně. Třeba prohledávání do větší hloubky, změna kritéria „uprostřed“ výpočtu nebo hybridní přístup kombinující náhodné losování a prohledávání. Uvidíme za dlouhých zimních večerů, je to nádherný problém, i když zrovna teď už mě vůbec nebaví 🙂 . Zazipovaný soubor v Excelu lze stáhnout zde, pozor, obsahuje makra.
Honza
26.10.2019