Optimalizace tras přívozů

Autoři

  • Pavel Töpfer Matematicko-fyzikální fakulta UK, Praha

Abstrakt

Další článek ze série věnované úlohám matematické olympiády – kategorie P (programování) popisuje jednu soutěžní úlohu ústředního kola z roku 2015 a její modifikace. Naším úkolem je nalézt takové trasy přívozů spojujících všechny stanovené body na obou březích vodního kanálu, aby byl celkový součet jejich délek co nejmenší. Zjednodušená verze úlohy hledá pouze tuto optimální délku, původní obtížnější verze vypisuje i trasy všech přívozů. Řešení úlohy je v obou případech založeno na metodě dynamického programování.

Stahování

Publikováno

2016-01-03

Jak citovat

Töpfer, P. (2016). Optimalizace tras přívozů. Matematika–Fyzika–Informatika, 25(1), 59–67. Získáno z https://www.mfi.upol.cz/index.php/mfi/article/view/249

Číslo

Sekce

Informatika