| 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.
|
|---|