EVO: cvičení 1 - Úloha N dam, TSP


  1. Stáhněte si archív s úlohami:
  2. nastavte spustitelnost (chmod +x Nqueens.py)
  3. nastavte spustitelnost (chmod +x tsp.py)


Řešená úloha - Problém N dam

Jak lze rozmístit n dam na šachovnici o rozměrech n×n tak, aby se vzájemně neohrožovaly?


  1. Doplňte fitness funkci:
  2. Program na stderr vypisuje průběžné údaje (číslo iterace, fitness).
    Po doběhnutí vykreslí na stdout šachovnici s nalezeným řešením.
  3. Až budete mít fungující program, ukládejte si výpisy do souboru a zobrazte průběh několika běhů.
  4. Experimentujte s nastavením parametru, hledejte co nejlepší.


Řešená úloha - Problém obchodního cestujícího (TSP)

V daném ohodnoceném úplném grafu najděte nejkratší hamiltonovskou kružnici.
Př.: vrtání desek plošných spojů -- co nejkratší dráha vrtáku:

(obvod http://pandatron.cz/?199&ne555_-_priklady_pouziti_-_1)

  1. Program na stderr vypisuje průběžné údaje (číslo iterace, vzdálenost, nejlepší vzdálenost).
    Po doběhnutí graficky znázorní nejlepší nalezené dráhy vrtáku pomocí gnuplot. Př.:
    ./tsp.py | gnuplot - --persist
  2. Ověřte, že algoritmus nachází „dobré“ řešení.
  3. Jaký typ algoritmu je použit?
  4. Ukládejte si výpisy do souboru a zobrazte průběh několika běhů.
  5. Vysvětlete rozdíl mezi jednotlivými variantami algoritmu.