Nejprve si posypu hlavu popelem, asi jsem první díl vůbec neměl publikovat, ale já už nevěděl kudy kam. Až když jsem to viděl napsané, tak mi došlo, kolik odboček a možností jsem cestou přehlédl. Když se ozval i syn Vojta, že by zkusil „prohledávání sítě“, odpověděl jsem mu, že už jsem to zkusil, a že to nikam nevede. Potom mi ale došlo, že vše záleží na volbě kritéria (neboli „užitkové funkce“).
Takže nejprve uvedu jedno omezení losování, na které jsem přišel záhy, ale nevěděl si s ním rady.
Pokud létá 16 pilotů na 4 startovištích ve 4 skupinách („čtvercová matice“), mohou letět 5 kol, přičemž se všichni potkají právě jednou. Pokud použiji užitkovou funkci, která přiřazuje váhy v podobě 3. mocniny opakování, potom je skóre 120 (120 letů každý s každým). Když by se skupiny vůbec neměnily, potom by všichni proti sobě letěli 5x a takových letů by bylo 24, takže skóre by mělo být 125*25 = 3000. Losování vrací „kopeček“ přibližně mezi 300 a 750. Jak to, že se těmto krajům losování ani nepřiblíží?
Podle mě je to tím, že hodnoty mezi 120 a 300 a 750 a 3000 jsou hodně řídké, takže je málo pravděpodobné, že se na ně při omezeném počtu losování dostane. Ale trápilo mě to. Modelový případ, kdy je známo řešení, se dá použít k testování algoritmu. Losování „hanebně selhalo“.
Dobrá zpráva je, že dále popsaný prohledávací algoritmus si s tímto případem hravě poradil, ale až po úpravě kritéria.
Tedy, mám piloty, startoviště, skupiny a užitkovou funkci, kterou v našem případě chci minimalizovat. Přiřazuji piloty v rámci kola do skupin a startovišť, přičemž předpokládám, že vše, co je hotové, je již optimální. Vezmu pilota X a vyzkouším, co to udělá s hodnotou užitkové funkce (skóre), když ho dám do jednotlivých skupin.
Dám pilota X na první volné místo v první skupině a zapíšu si skóre. Potom přemístím pilota X na první volné místo ve druhé skupině a opět si zapíšu skóre. Pokračuji dalšími skupinami. Když vyzkouším všechny možnosti, vložím pilota natrvalo tam, kde minimalizuje skóre. Pokud je více možností se stejným skóre, dám ho do dřívější skupiny.
Nejlépe to lze ukázat na příkladu. Mám 18 pilotů, 6 startovišť, 3 skupiny:
Zde zařazuji pilota G do třetího kola. Když je v první skupině, je skóre 734. Vpravo jsou ukázány i váhy a počty vzájemných soubojů.
Když je ve druhé skupině, je skóre 741.
Když je ve třetí skupině, je skóre také 741.
Nejmenšího skóre se tedy dosáhne, když bude pilot G v první skupině.
Prohledáváním se to nazývá proto, že si lze celou matici představit jako síť. Z každé křižovatky sítě vedou 3 cesty (v případě 3 skupin), které prozkoumám a vyberu tu nejvýhodnější. Dále postupuji na další křižovatku, kde zase vyberu nejvýhodnější cestu dále.
Dále se postupuje dalším pilotem v pořadí, tj. H, a postup se opakuje, až mají všichni piloti v kole své místo. Do dalšího kola se opět začne A. Algoritmus je poměrně jednoduchý, dalo by se to zvládnout i bez počítače, jen na papíře.
Tento algoritmus najde nejlepší řešení i pro výše popsaný případ 16 pilotů ve čtyřech skupinách a 5 letech, ale kritérium musí mít u nuly nenulovou váhu. Popravdě, dlouho mě to mátlo, než jsem přišel na to, že u nuly nesmí být nula.
V případě 18 pilotů ve třech skupinách a pro šest letů je výsledek následující:
Při náhodném losování vyjde tato distribuce skóre pro danou užitkovou funkci. Je zajímavé, že výsledek nalezený opakovaným losováním se téměř blíží výsledku prohledávání sítě. Zde tedy opakované losování „skoro“ funguje. Ale prohledávání se zdá být mnohem efektivnější (zde jen upozorňuji, že v první části jsem měl u nuly nulu, tudíž nejsou výsledky mezi oběma články srovnatelné).
Vede však tento algoritmus opravdu k nejlepšímu výběru? Možná, to nelze určit. Pro jednoduché případy a pro „čtvercové“ matice nejlepší řešení, která jsou známá, najde. Snažil jsem se ukázat, že hodně závisí na kritériu. Součástí algoritmu je i pravidlo, že pokud je více možností, kudy pokračovat, vyberu si tu první. Jiná kritéria a jiná pravidla povedou k jiným výsledkům.
Piloty ve skupině i skupiny v kole je možné, či dokonce nutné, mezi sebou promíchat, to ale skóre nezmění.
Kdybych měl v úmyslu vytvořit si vlastní program pro organizace soutěže, použil bych toto prohledávání a výše uvedené kritérium 3. mocniny opakování, pro nulu s vahou 8. Ale možná to chce ještě hledat a zkoušet, mě už to ale nebaví 🙂 . A vlastní program také vyvíjet nebudu 😉 .
Honza
15.10.2019