|
|
Testování heuristik pro úlohy obchodního cestujícího
Dítětová, Tereza ; Jablonský, Josef (vedoucí práce) ; Fábry, Jan (oponent)
Úloha obchodního cestujícího je nejznámějším typem okružních dopravních problémů. Tato práce přináší empirické srovnání dvou vybraných heuristik, které dávají v úloze obchodního cestujícího přibližná řešení, s optimálním řešením. Právě jednoduchá formulace úlohy a rychle rostoucí složitost řešení činí TSP hodně atraktivním. V první kapitole se zaměřuji na teoretické vymezení včetně historického vývoje, druhá kapitola popisuje vybrané heuristické metody pro řešení TSP. Ve třetí kapitole jsou zaznamenány výsledky výpočetních experimentů, které jsem provedla s pomocí mnou naprogramované aplikace. Z výsledků, ke kterým jsem došla, mohu soudit, že metoda nejbližšího souseda je výhodnější než metoda výhodnostních čísel, a to jak rychlostí výpočtu, tak i přiblížení se k optimu.
|
host ::
RSS.