czwartek, 23 czerwca 2011

Problem komiwojażera w logistyce

Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie.
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.
Należy znaleźć najkrótszą trasę zaczynającą się np. z Warszawy, przechodzącą jednokrotnie przez wszystkie pozostałe miasta i wracającą do Warszawy.

Brak komentarzy:

Prześlij komentarz