Problem komiwojażera

Czyli ciekawy problem matematyczny, z którym na co dzień borykają się np. największe firmy kurierskie.

[Pivoo]

http://pl.wikipedia.org/wiki/Algorytm_Dijkstry

To jest zapewne najprostszy algorytm jaki do tej pory wymyślono do problemu komiwojażera.

Poza nim dosyć proste są algorytmy genetyczne, które w skrócie polegają na tym, że losowanych jest x ścieżek i później te ścieżki mieszają się ze sobą aż do momentu kiedy coraz trudniej jest znaleźć lepsze rozwiązanie.

http://pl.wikipedia.org/wiki/Algorytm_genetyczny

[ghostface]

@Pivoo:

To jest zapewne najprostszy algorytm jaki do tej pory wymyślono do problemu komiwojażera.

Algorytm Dijkstry nie rozwiązuje problemu komiwojażera. Służy on do wyliczenia najkrótszej drogi do danego wierzchołka, ale nie do wyznaczenia najkrótszej ścieżki w grafie, która przechodzi przez wszystkie wierzchołki.

[DanioPL]

@Pivoo: Jeśli udowodnisz, że potrafisz rozwiązać problem komiwojażera za pomocą algorytmu Djikstry, to możesz dostać 1mln dolarów :)

[nom_om]

Problem korwijeża?