Problem komiwojażera

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

[DoTheMonkey]

Podoba mi się dynamika tej prezentacji.

[Zircon]

@DoTheMonkey: Pewnie została zrobiona przez młody, dynamiczny zespół.

[b4kus]

Ciekawy jest algorytm mrówkowy stworzony na podstawie obserwacji zachowań tych zwierząt:

W najprostszej wersji schemat algorytmu mrówkowego wygląda następująco:

Połączenia między miastami inicjowane są z pewną (niewielką) ilością feromonu. Pewna liczba mrówek umieszczona jest na losowo wybranych miastach.

Mrówki

[minuano68]

@b4kus: Miałem na studiach projektowanie efektywnych algorytmów. Tam właśnie była o tym mowa. Chyba najciekawszy przedmiot. Prowadzący opowiadał, że w ramach doktoratu szeregował statki w Hongkongu :-)

[0utsider]

Na magisterkę rozwiązywałem algorytmem mrówkowym problem komiwojażera z zyskami, ale trzeba przyznać, że kolega algorytmem genetycznym komórkowym dostawał szybciej i lepsze wyniki.

[m.....t]

3 lata studiów logistycznych, a tu taka ciekawostka...

[Smiechol]

@maciekst:

To co się na tych studiach robi? Myślałem, że to jedno z podstawowych zagadnień logistyki.

[Sylar]

@maciekst: 5 lat studiów logistycznych na PRz i co roku ten problem był poruszany, omawiany i robione były różne obliczenia, a to na kompach w programach, nawet excelu, na kartkach, wzorach i kalkulatorach. Jeśli przez 3 lata nie miałeś poruszonego problemu komiwojażera to może zmień studia, no chyba że nie robisz inżyniera tylko licencjat, to winszuje.

[koscik]

Całkiem ciekawie przedstawili działanie aplikacji, ale już działanie algorytmu tak sobie, muszę pooglądać jeszcze raz.

[shusty]

@koscik: Problem komiwojażera jest tak stary i przez tysiące ludzi rozwikływany, że tutaj już za dużo nie ma co dodawać. Jest masa sposobów, by znaleźć rozwiązanie. Złożoność może być ogromna, więc przeważnie przegląd zupełny odpada.

Ja sam gdybym miał rozwiązać taki problem użyłbym algorytmu genetycznego. Dosyć prosta implementacja i całkiem niezłe wyniki. Dodatkowo łatwo można wpleść w to wszystko dodatkowe kryteria np. priorytety, jaka przesyłka w jakim czasie powinna dotrzeć

[koscik]

@Gronie: Mam przeczucie, że coś takiego może istnieć. Google wystawia bogate API dla swoich map i pewnie ktoś już się pokusił o komiwojażera ;)

edit: Wpisz komiwojażer google w googlach, jeden z ciekawszych na oko linków to http://www.gebweb.net/optimap/

Nie chce mi się drążyć, dalej to Twoja sprawa :)

[calkiem]

@rzezbi tak, znalazlem skrota, ale teraz nie widze 8)

[Finsnsowy]

pisałem z tego pracę dyplomową na studiach. teraz pracuję na infolinii :P

[a.....s]

@Finsnsowy: Jak będziesz głodny to wpadnij do mnie na McD, też pisałem pracę :)

[S.....h]

Swoją drogą jak ktoś wymyśli algorytm wielomianowy tutaj z ludzi zgromadzonych, który poda najkrótszą drogę zawsze , to mam dla niego pół miliona dolarów.

[givdaf]

@Sarseth: cwaniak wie, że amerykańska fundacja płaci za to milion dolarów ;)

[Ragnarokk]

@Dakkar: To algorytm o zlozonosci wykladniczej

[WesolyMorswin]

A prędkość na drogach też tu jest brana pod uwagę? Bo jak nie to jest to trasa najkrótsza, a nie najszybsza, a więc... czy to takie świetne rozwiązanie?

[staszko90]

@WesolyMorswin: Droga może być rozumiana również jako czas przejazdu. Można powiedzieć że dokonujesz transformacji z dziedziny odległości na dziedzinę czasu przejazdu. Wbrew pozorom to wcale nie jest takie trudne. Co więcej, idąc krok dalej można zrobić funkcję kosztów uwzględniają czas jazdy (koszty pracownika) i zużyte w tym czasie paliwo. Jak może zauważysz, sprowadza się to do tego samego co poprzednio, czyli wyznaczenia takich takich funkcji kosztów dla każdego połączenia i

[Dakkar]

@WesolyMorswin: Koszt połączenia między wierzchołkami możesz kształtować dowolnie. To może być koszt przejazdu, odległość między miastami, zużycie paliwa, przepustowość dróg, ogólnie cokolwiek (możesz nawet uwzględnić kilka parametrów dla jednego połączenia, nadać im wagi i wyliczyć średnią kosztów). Aby było ciekawiej i trudniej, możesz także zabronić poruszania się niektórymi trasami albo zaznaczyć, ze daną trasą można poruszać się tylko w jednym kierunku.

[rea9]

Rozwiązywałem podobne problemy na Programowaniu Liniowym na uczelni, z tym że tam była do dyspozycji jedynie kartka papieru i długopis - bezmiar dłubania. Swoją drogą, ciekawa prezentacja.

[dziczku]

@rea9: U nas nazywało się to Badania Operacyjne:)

[kote]

Z tego co wiem, to podczas prezentacji któregoś z pseudokwantowych komputerów od D-Wave Systems, pokazano rozwiązanie tego problemu.

[kote]

@Dakkar: Nie pamiętam, wydaje mi się, że podczas prezentacji pierwszego D-Wave'a. Ja dobrze wiem o co chodzi, chodzi o szybkość obliczeń :) Podczas prezentacji pokazano, jak D-Wave zaprogramowany do obliczania tego typu algorytmów szybko sobie z nimi radzi. (W sensie, PC robi to tydzień a D-Wave tylko 30 sekund, kupujcie nasz kwantowy komputer za 10 mln $)

[kote]

@givdaf:

@Dakkar:

Po pierwsze, skłamałam :P Nie był to D-Wave One tylko Orion, 16-qubitowy prototyp D-Wave One. Po drugie, wiem, na czym polega problem xd Wiem, że nie jest to problem nierozwiązany, tylko po prostu trudny i czasochłonny. Po trzecie, skłamałam również mówiąc, że rozwiązanie problemu zostało zaprezentowane xd Podczas prezentacji zostało wspomniane, że tego typu problemy będą mogły być w przyszłości szybko rozwiązywane przez komputery kwantowe. Nie