Problém optimální explorace prostředí

• Data: instance.txt a jeji visualizace

V této úloze je povoleno analyzovat konkrétní data a využívat získané znalosti, např. matici vzdáleností mezi uzly, i jinde než v ohodnocovací funkci, např. v rekombinačních operátorech.

Je dána mapa prostředí, na které je M objektů zájmu, tzv. segmenty. Každý segment můžeme považovat za souvislou křivku.

Dále máme úplný neorientovaný graf o N uzlech, rozdělených do M tříd. Každá třída reprezentuje uzly, které patří jednomu segmentu.

Každý uzel “vidí” jednu nebo více souvislých částí svého segmentu.

Jeden uzel je výchozí, tzv. depot.

Cílem je nalézt cestu, která prochází podmnožinou uzlů tak, že všechny segmenty jsou úplně pokryty a délka cesty je minimální. Segment je pokryt právě tehdy, když je jakýkoliv jeho bod “vidět” alespoň z jednoho uzlu na cestě.

Pozor: Hledáme neuzavřenou cestu.

• Posloupnost K uzlů, kde K ≤ N.

Kvalita řešení je určena jako délka cesty, při splnění podmínky na úplné pokrytí všech segmentů.