Differences

This shows you the differences between two versions of the page.

--- courses:a0m33eoa:semestralni_ulohy:mtsp:start [2018/06/25 12:56]
+++ courses:a0m33eoa:semestralni_ulohy:mtsp:start [2018/06/25 12:56] (current)
@@ Line 1: / Line 1: @@
+====== TSP s několika cestujícími ======
+Data: {{:courses:a0m33eoa:semestralni_ulohy:mtsp:mtsp_data.zip|}} pro 3, 4 a 5 cestujících
+Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste pozice měst nebo matici vzdáleností využívat nikde jinde než v ohodnocovací funkci. V této úloze ale **je povoleno využívat či analyzovat konkrétní úlohu MTSP** i jinde, např. v rekombinačních operátorech.
+===== Popis problému =====
+Na vstupu je úplný neorientovaný graf o N uzlech. Cílem je nalézt takovou množinu cest pro M cestujících, které všechny vychází z počátečního uzlu (depotu) a zase v něm končí, všechny uzly (kromě depotu) jsou navštíveny právě jednou a délka nejdelší cesty je minimální. Žádná z cest nesmí mít nulovou délku.
+{{:courses:a0m33eoa:semestralni_ulohy:mtsp:mtsp.png|}}
+===== Možné reprezentace =====
+  * [permutace měst][break-pointy],  příklad: [2-4-3|5-8-6-7|10-9][3,7]
+  * ...
+===== Jednotná ohodnocovací funkce =====
+Kvalita řešení je určena jako délka nejdelší cesty z M cest.