V dubnu 2025 jsme odstartovali programovací soutěž. Soutěžícím jsme dali šest týdnů na nalezení nejlepšího řešení. Celé týdny se v žebříčku objevovalo jen pár jmen, v posledních dnech ale přibývala dvě i tři denně. Největší drama přišlo na konci. Někteří soutěžící si své nejlepší řešení schovávali až těsně před deadline a jména prvních tří se mezi sebou neustále střídala.
Vítězem se nakonec stal Mgr. Pavel Dvořák, Ph.D., který aktuálně působí na MFF UK. Na třetím místě se překvapivě umístil student, kterého studium na vysoké škole teprve čeká – devatenáctiletý Tomáš Pražák. Vymyslet programovací úlohu tak, aby potrápila i ty nejchytřejší hlavy a umožňovala nalézat pořád lepší a lepší řešení – to není jen tak. Stojí za ním CTO Qminers Filip Matzner. Jak na to šel?
„Když se řekne „minimální kostra“, většina lidí si vzpomene na algoritmus z učebnice a čtyři obrázky, co to celé elegantně vysvětlí. Proč tedy soutěžit v něčem, co se probírá v prvním semestru druhého ročníku?“ popisuje Filip svoje úvahy. „Jenže stačí jen drobná úprava a z polynomiální pohodičky je rázem NP-úplná džungle. A přesně tam jsem chtěl všechny poslat.“
| Historické okénko – Borůvkův algoritmus
Roku 1926 hledal mladý český matematik Otakar Borůvka nejlevnější způsob, jak zavést elektřinu do obcí jihozápadní Moravy. Vynalezl při tom první známý algoritmus pro minimální kostru grafu: v každé fázi spojil každou komponentu s jejím nejbližším sousedem, čímž postupně „srůstaly“ do jediného stromu. Problém hledání minimální kostry se stal milníkem moderní kombinatorické optimalizace a Borůvkův algoritmus byl několikrát „znovuobjeven“ (Choquet, Sollin). Pokud dovolíme přidávat do grafu nové vrcholy, najednou máme problém, ke kterému efektivní algoritmus neznáme - hledání minimálního Steinerova stromu. Tomu se shodou okolností poprvé věnoval jiný známý český matematik Vojtěch Jarník, a to již v roce 1934.
| Od učebnice k noční můře
Hledání minimální kostry je populární problém s efektivním polynomiálním řešením. Hledání Steinerova stromu je však úloha z kategorie NP-těžkých problémů. Proto se objevilo mnoho různých heuristik, optimalizačních přístupů a softwarových pomocníků. Ačkoliv neznáme efektivní algoritmus pro velké grafy, existují heuristiky, které se k optimu přibližují třeba až pro 10 000 vrcholů.
„My jsme ale nechtěli, aby se řešení úkolu dalo založit jen na solveru, to by bylo příliš snadné. Úlohu jsme tedy dále upravili,“ vypráví Filip Matzner. „Solver typicky předpokládá, že nové vrcholy nic nestojí. Takové řešení pak navrhne hromadu bodů „zadarmo“ a deklaruje vítězství – jenže účet za materiál by nás zruinoval. Proto jsme přidali cenu 5 000 jednotek za každý nový uzel. Solver už rázem nestačí, protože slepě sype vrcholy, které drtivou většinu sítě spíš prodraží.“
| Jak na to šli účastníci?
Řešitelé museli některé body buď úplně vypustit, nebo je umístit jinam. Někteří zkusili udělat jen „pruning“, tedy drahé body prostě vyhodit. Jiní na to šli chytřeji – hledali pro ty drahé body nové, efektivnější pozice.
Jeden účastník večer spustil evoluční algoritmus, který přes noc generoval malé náhodné změny a vyvíjel je evolučně. Snažil se najít lepší řešení a šel na to velmi chytře a po zásluze skončil mezi vítězi. Jiný účastník používal solver iterativně na dílčí podgrafy, které následně lepil do výsledného stromu. A právě ten měl nakonec nejlepší výsledek v repozitáři.
„Měli jsme ale i lidi, kteří solver úplně vynechali, napsali vlastní evoluční algoritmus od nuly a dosáhli velmi dobrých výsledků. Ale nebyli mezi prvními třemi. Kdyby někdo použil solver a ještě ho dále vylepšil, měl by velký potenciál,” doplňuje Filip Matzner.
| Vizualizace ukázala překvapení
V úloze byl skrytý malý easter egg. Viktor Němeček, Python developer a Filipův kolega v Qminers, navrhl zadat úlohu tak, aby řešení při vizualizaci složilo logo Qminers.
„U vítězného řešení mezi zadaných 10 000 bodů přibylo 3795 dalších bodů a mezi nimi necelých 14 tisíc propojení. Každý vrchol má stupeň nejvýše 3 a přidané vrcholy mají stupně právě 3 a úhly mezi hranami 120 stupňů,“ popisuje Viki. „Žádný ze tří nejlepších účastníků nezkoumal možnost tvořit vrcholy stupně 4 nebo více, přestože v úloze tak, jak jsme ji zadali, může být takové řešení optimální. Dalším výzkumem tímto směrem by tedy vítězné řešení mohlo jít ještě zlepšit.“
| Takže… troufneš si?
Úloha už má za sebou jednu soutěžní sezónu a výhry byly rozdány. Jistotu, že jsme viděli to nejlepší možné řešení, ale nemáme. Jestli tě láká hacknout naši výzvu, zkus to – a napiš nám, jak se ti dařilo!
Zdroje:
Nešetřil, Jaroslav & Nešetřilová, Helena. (2012). The origins of minimal spanning tree algorithms – Borůvka and Jarník. Documenta Mathematica.