V kanceláři městského radního pro dopravu.
Plánování oprav je fuška. Pokud zůstanou dvě sousedící silnice neopravené, lidi se naštvou. Ale peněz je málo. Jak to udělat, aby se mohlo opravit co nejméně silnic?
Zkusím to nakreslit nějak náhodně.
Teď už nemůžu žádnou opravu vyškrtnout, ale nešlo by to lépe? Tady je cesta složená z opravené, neopravené a opravené silnice. Když to změním na neopravenou, opravenou a neopravenou, mám hned o opravu méně!
Nějaké další podobné střídavé cesty? Tahle vypadá jako kytka - stonek a pak okruh jako květ. Ale do květu může vést jen jedna neopravená silnice, takže ho rovnou můžu rovnou nahradit jednou velkou křižovatkou, ne?
Problému, jak vybrat co nejvíce silnic, které spolu nebudou sousedit, se říká maximální párování (chceme popárovat co nejvíce křižovatek). Řeší se tzv. Blossom algoritmem, který postupně hledá zlepšující cesty a květy neboli kružnice liché délky nahrazuje jedním vrcholem. Podrobnější popis včetně obrázků je třeba tu.
- Pro vkládání komentářů se musíte přihlásit
Květinový algoritmus :) jak
HCHO
Květinový algoritmus :) jak vidno, tak i matematici jsou romantici. Pěkné drabble :)
Díky za hezké drabble. Že se
mila_jj
Díky za hezké drabble. Že se kružnici o lichém počtu uzlů říká květ, to mi zatím bylo utajeno. Ale pokud si ještě něco z teorie grafů pamatuji, býval tam třeba i strom.