Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m usunięcie literówki w jednym odnośniku (literka "w" - niepotrzebnie) |
wersja decyzyjna, ang. sktót |
||
Linia 1:
{{Teoria grafów}}
'''Problem komiwojażera''' (TSP - ang. traveling 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ść pomiędzy każdą parą miast.
Linia 15:
'''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.
== Wersja decyzyjna ==
W wersji decyzyjnej problemu, danymi są graf i pewna liczba ''n'', należy odpowiedzieć czy istnieje trasa komiwojażera krótsza od ''n''.
Tak sformułowany problem jest [[problem NP-zupełny|NP-zupełny]].
{{Matematyka stub}}
| |||