• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Problem komiwojażera

    Przeczytaj także...
    Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka) . Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi.
    Maciej Marek Sysło (ur. 3 listopada 1945 w Tarnowie) – profesor, Wydział Matematyki i Informatyki Uniwersytetu Wrocławskiego, Wydział Matematyki i Informatyki Uniwersytetu Mikołaja Kopernika w Toruniu, matematyk (specjalność – teoria grafów, matematyka dyskretna, algorytmika, optymalizacja, dydaktyka informatyki), nauczyciel akademicki kierunków związanych z informatyką.

    Problem komiwojażera (ang. travelling salesman problem, TSP) – zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w 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ść / 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.

    W teorii złożoności obliczeniowej problem NP-trudny (NPH) to taki problem obliczeniowy, którego rozwiązanie jest co najmniej tak trudne jak rozwiązanie każdego problemu z klasy NP.Uniwersytet Princeton (ang. Princeton University) – naukowo-badawczy uniwersytet prywatny w Stanach Zjednoczonych, działający w mieście Princeton w stanie New Jersey. Nazwa także odnosi się do college’u, czyli odpowiednika studiów licencjackich (ang. undergraduate studies). To ci studenci głównie tworzą kulturę kampusu i afiszują swoją przynależność do niego, nazywając siebie „Princeton man”, w odróżnieniu od „Yale man” czy „Harvard man”. Studenci z Princeton tradycyjnie rywalizują ze studentami z Yale i Harvardu, także w późniejszym życiu zawodowym.

    Symetryczny problem komiwojażera (STSP) polega na tym, że dla dowolnych miast A i B odległość z A do B jest taka sama jak z B do A. W asymetrycznym problemie komiwojażera (ATSP) odległości te mogą być różne.

    Rozwinięciem problemu komiwojażera jest problem marszrutyzacji.

    Wydawnictwo Naukowe PWN SA – wydawnictwo z siedzibą w Warszawie, założone w 1951, w obecnej formie prawnej działające od 1997. Wydawnictwo Naukowe PWN SA stanowi jednostkę dominującą Grupy kapitałowej PWN, w skład której wchodzi kilkanaście przedsiębiorstw, głównie wydawnictw.Karl Menger (ur. 13 stycznia 1902 r. w Wiedniu, zm. 5 października 1985 r. w Chicago w stanie Illinois w USA), austriacki matematyk, jeden z twórców teorii wymiaru, znany z konstrukcji kostki Mengera.

    Historia[]

    Początek badań nad problemem komiwojażera nie jest jasny. Wspomina o nim podręcznik z 1832, który zawiera przykładową trasę po Niemczech i Szwajcarii, lecz nie zawiera żadnych matematycznych uzasadnień.

    W 1859 irlandzki matematyk William Rowan Hamilton sformułował problem istnienia cyklu o długości n w grafie n-wierzchołkowym.

    Problem marszrutyzacji - problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej liczby środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej, niż jedno kryterium optymalizacji. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).Problem NP-zupełny (NPC) czyli problem zupełny w klasie NP ze względu na redukcje wielomianowe, to problem, który należy do klasy NP oraz dowolny problem należący do NP może być do niego zredukowany w czasie wielomianowym. Czasami zamiast redukcji w czasie wielomianowym używa się redukcji w pamięci logarytmicznej. Pytanie, czy są to definicje równoważne pozostaje pytaniem otwartym. Taka definicja problemów NP-zupełnych implikuje fakt, że jeśli tylko potrafimy rozwiązać jakikolwiek problem NP-zupełny w czasie wielomianowym, to potrafimy rozwiązać w czasie wielomianowym wszystkie problemy NP. Problemy NP-zupełne można więc traktować jako najtrudniejsze problemy klasy NP (z punktu widzenia wielomianowej rozwiązywalności).

    Za faktycznego twórcę problemu komiwojażera uznaje się austriackiego matematyka Karla Mengera, który go zdefiniował w 1930, zwracając szczególną uwagę na stopień jego skomplikowania. Niezależnie od niego ten sam problem poruszył w 1934 Hassler Witney na wykładzie w Princeton University. Natomiast pierwsze praktyczne zastosowanie problemu miało miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych.

    Z uwagi na bardzo prosty opis problemu oraz opinii o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów.

    Przykład[]

    Miasta: Kutno, Warszawa, Poznań, Kraków

    Odległości:

    Należy znaleźć najkrótszą trasę zaczynającą się np. z Kutna, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Kutna.

    Problem ten jest NP-trudny.

    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 NP-zupełny.

    Uwagi

    1. Oryginalny tytuł: Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur

    Przypisy

    1. Sysło, Deo i Kowalik 1995 ↓, s. 282.
    2. Sysło, Deo i Kowalik 1995 ↓, s. 283.
    3. Sysło, Deo i Kowalik 1995 ↓, s. 314.
    4. The traveling salesman and the assignement problem, [w:] AlexanderA. Schrijver AlexanderA., Combinatorial Optimization: Polyhedra and Efficiency, s. 51 (ang.).

    Bibliografia[]

  • Maciej MarekM. M. Sysło Maciej MarekM. M., NarsinghN. Deo NarsinghN., Janusz S.J. S. Kowalik Janusz S.J. S., Algorytmy optymalizacji dyskretnej, wyd. drugie, Warszawa: Wydawnictwo Naukowe PWN, 1995, ISBN 83-01-11818-0.
  • Linki zewnętrzne[]

  • Traveling Salesman Problem [dostęp 2016-05-22] (ang.).



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.015 sek.