Meno:Vladimír
Priezvisko:Boža
Názov:Problém dvoch obchodných cestujúcich
Vedúci:RNDr. Michal Forišek, PhD.
Rok:2013
Blok:INF
Kľúčové slová:obchodný cestujúci, PTAS, dynamické programovanie, celočíselné lineárne programovanie
Abstrakt:V práci sa zaoberáme modifikáciou problému obchodného cestujúceho -- problémom dvoch obchodných cestujúcich, t.j. hľadáme dve hranovo disjuktné hamiltonovské kružnice, ktorých súčet dĺžok je čo najmenší. Pre riešenie tohoto problému sme pomocou dynamického programovania zostrojili exaktný algoritmus, ktorého čas behu je výrazne lepší ako čas behu triviálneho algoritmu. Ďalej sme modifikovali PTAS pre problém obchodného cestujúceho v euklidovskej rovine, aby sme pomocou neho zostrojili PTAS pre problém dvoch obchodných cestujúcich. Nazáver ešte porovnávame praktickú výkonnosť heuristík využívajúcich celočíselné lineárne programovanie.

Súbory diplomovej práce:

main.pdf