Problem komiwojażera

Problem komiwojażera- problem bardzo powszechny polegający na znalezieniu takiej trasy między punktami, by przebiegała on przez wszystkie te punkty (warunek: każdy punkt możesz odwiedzić tylko jeden raz), a potem wrócić do miejscowości z której wyruszyliśmy oraz by trasa była jak najkrótsza i jak najszybsza. Dotyczy to też podróży w naszej rzeczywistości: w rzeczywistości polega to na tym samym (czyli na odwiedzeniu każdej miejscowości, maks. jeden raz, by wrócić pod koniec do miejscowości z której wyruszyliśmy, jednocześnie, by trasa była jak najkrótsza, jak najszybsza, oraz jak najtańsza).
A teraz pytanie:
Skąd pochodzi nazwa tego problemu oraz kim nazywamy komiwojażera?
Zastanówcie się przez chwilę, a jak nic nie wymyślicie to zapraszam do odpowiedzi:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Zacznijmy od wyjaśnienia sobie, kim jest komiwojażer:
komiwojażer to przedstawiciel firmy, który podróżuje, w celu zdobywania klientów oraz przyjmowania od nich zamówień na jakiś konkretny towar, który sprzedaje firma.
Teraz możesz się zastanawiać dlaczego jest to problem komiwojażera?
Otóż komiwojażer ma ograniczony budżet na tą podróż (więc dlatego trasa ma być najtańsza i najkrótsza, gdyż wicie po ile chodzi litr paliwa), oraz prezes firmy pożąda od takiej osoby, by zachęcił jak najwięcej osób w jak najkrótszym czasie (bo jest takie przysłowie: czas to pieniądz), a dlaczego trasa ma być jak najkrótsza- by była ona jak najszybsza (bo przeważnie krótsze trasy są szybsze, ale nie zawsze) oraz wspominałem o tym przy okazji poprzednich wymagań.

Problem komiwojażera jest jednym tych problemów, które bardzo trudno rozwiązać oraz trzeba by było poświęcić na to długo czasu (nawet Albert Einstein nie zrobiłby tego w jeden dzień), gdyż ilość możliwości tras między miastami (zakładając, że koszty przejazdu są różne) to ilość takich tras obliczamy ze wzoru (według Hamiltona):

gdzie:
n- ilość miast, które musimy odwiedzić

Choć w rzeczywistości, istnieję więcej tras, ten wzór określa, ile jest najkrótszych tras między miejscowościami

Teraz widzicie, że problem komiwojażera jest naprawdę trudny do jednoznacznego określenia, najkrótszej, najtańszych oraz jednocześnie najszybszej trasy między różnymi punktami na Ziemi, gdyż tych połączeń jest możliwych (według mnie) aż kwadrylion

Koniec