Úloha kropicího vozu

Úloha číslo: 3629

Nalezněte algoritmus pro nalezení nejkratšího uzavřeného sledu, jež obsahuje všechny hrany daného grafu (sled je posloupnost navazujících hran, kde se hrany i vrcholy mohou opakovat). Pro jednoduchost předpokládejte, že graf má nejvýše 6 vrcholů lichého stupně.

  • Řešení

    Sestavíme pomocný úplný graf na vrcholech lichého stupně jehož hrany budou ohodnoceny vzáleností těchto vrcholů v původním grafu.

    Párování minimální ceny odpovídá úsekům, které je potřeba projet dvakrát. Zdvojíme-li hrany podél těchto cest, dostaneme eulerovský graf, jehož uzavřený eulerovský tah nalezneme pomocí standardního algoritmu pro tuto úlohu.

    Párování minimální ceny lze nalézt hrubou silou (je-li pomocný graf malý jako v zadání), případně využít některý ze sofistikovaných algoritmů pro tento problém.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze