Problem komiwojażera: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m Dodaję nagłówek przed Szablon:Uwagi, dodaję nagłówek przed Szablon:Przypisy |
m ort. |
||
Linia 1:
{{Teoria grafów}}
'''Problem komiwojażera''' ({{ang.|travelling salesman problem, TSP}}) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego [[cykl Hamiltona|cyklu Hamiltona]] w [[graf (matematyka)|pełnym grafie ważonym]]{{odn|Sysło|Deo|Kowalik|1995|s=282}}<ref name=":0">{{Cytuj książkę|nazwisko=Białynicki-Birula, Białynicka-Birula|imię=Iwo, Iwona|tytuł=Modelowanie rzeczywistości|rok=2002|wydawca=
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ść / cena 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{{odn|Sysło|Deo|Kowalik|1995|s=282}}<ref name=":0" />.
| |||