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

Dosyć dobrym sposobem na stopowanie takiego algorytmu jest używanie pochodnej:

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

Pochodna - zapewne znana wielu osobom jako nieprzydatna rzecz uprzykrzająca

[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?