Zobecněný TSP

• Data: zobecnenytsp_instance.zip

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.

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.

• permutace M měst

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