Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m r2.7.1) (robot poprawia: hu:Az utazó ügynök problémája |
dodatek |
||
Linia 2:
'''Problem komiwojażera''' (TSP - ang. travelling salesman problem) jest to zagadnienie z [[teoria grafów|teorii grafów]], polegające na znalezieniu minimalnego [[cykl Hamiltona|cyklu Hamiltona]] w [[graf (matematyka)|pełnym grafie ważonym]].
Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast, które komiwojażer ma odwiedzić, oraz odległość/cenę podróży/czas podróży pomiędzy każdą parą miast. Celem jest znalezienie najkrótszej/najtańszej/najszybszej drogi łączącej wszystkie miasta zaczynającej się i kończącej się w określonym punkcie.
'''Symetryczny problem komiwojażera (STSP)''' polega na tym, że odległość pomiędzy miastami A i B jest zawsze taka sama. W '''asymetrycznym problemie komiwojażera (ATSP)''' odległość od miasta A do miasta B może być inna, niż odległość od miasta B do miasta A.
| |||