Warning
This page is located in archive.

Differences

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

Link to this comparison view

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.
  
courses/a0m33eoa/semestralni_ulohy/mtsp/start.txt · Last modified: 2018/06/25 12:56 (external edit)