Problem komiwojażera

Wyobraźmy sobie, że mamy do odwiedzenia kilka miast rozrzuconych na dużym obszarze. Chcemy zaplanować podróż tak, by koszty były możliwie najmniejsze, zastanawiamy się zatem w jakim porządku należałoby odwiedzać poszczególne miasta (każde z nich chcemy odwiedzić tylko jeden raz). Czy takie zadanie jest łatwo rozwiązać?

Problem jest banalny dla dwóch, trzech, czterech czy pięciu miast do odwiedzenia - wystarczy przedstawić sytuację na grafie z wagami, którego wierzchołki są reprezentacjami poszczególnych miast, a wagi nad krawędziami określają ile kilometrów jest między jednym a drugim miastem. Okazuje się jednak, że ilość możliwych dróg wzrasta zdecydowanie szybciej niż ilość miast, gdy dodajemy do trasy kolejny cel podróży. A zatem metoda polegająca na wypisywaniu tras i liczeniu ich odległości przestaje być skuteczna gdy rozważa się dłuższe wycieczki.

Czy ten problem jest praktyczny? Zdecydowanie. Przed dokładnie tego typu zadaniem stoją w swej działalności firmy kurierskie, linie lotnicze, przedstawiciele władz lokalnych odpowiedzialni za zarządzanie komunikacją miejską, czy wreszcie - jak w początkowym przykładzie - osoba planująca wakacyjną wycieczkę (a być może młoda para wybierająca

Polecamy również:

Komentarze (0)
Wynik działania 2 + 1 =
Ostatnio komentowane
w
ldwjnd • 2021-07-27 09:06:46
żoną Jaroslawa Iwaszkiewicza była pisarka i tłumaczka Anna Iwaszkiewiczowa z domu Lilp...
Iwona • 2021-07-19 18:40:47
"Oda do radości" to utwór Beethovena. Schiller napisał "Do Radości".
Germanista • 2021-07-10 02:59:47
Zgromadzenie Narodowe (Konwent) nie było "rządem rewolucyjnym", a parlamentem.
Andrzej • 2021-07-06 08:15:34
Czy naprawdę nie dało się tego bardziej spłycić? Gdzie jest drugi syn? Ten który p...
Andrzej Koraben • 2021-06-30 11:34:39