Warning
This page is located in archive. Go to the latest version of this course pages.

Zobecněný TSP

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 analyzovat konkrétní data a využívat získané znalosti i jinde, např. v rekombinačních operátorech.

Popis problému

Na vstupu je úplný neorientovaný graf o N uzlech, rozdělených do M tříd.

Cílem je nalézt uzavřenou cestu, která obsahuje právě jeden uzel z každé třídy a jejíž délka je nejkratší.

Poznámka: Každá skupina je v řešení zastoupena právě jedním uzlem; do každého uzlu vedou právě dvě hrany.

Možné reprezentace

  • permutace M měst

Jednotná ohodnocovací funkce

Kvalita řešení je určena jako délka cesty, kterou minimalizujeme.

courses/a0m33eoa/semestralni_ulohy/zobecneny_tsp/start.txt · Last modified: 2019/11/18 15:31 by kubalik