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 poruszają się z miasta do miasta. Nie mogą wracać do miasta, w którym już były. Miasto do którego przemieści się mrówka wybierane jest losowo jednakże preferowane są miasta bliżej położone i te z
@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 :-)
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.
@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: 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ć -
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.
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?
@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 wykonania
@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.
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.
@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 $)
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 zaprezentowano jednak
Komentarze (157)
najlepsze
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 poruszają się z miasta do miasta. Nie mogą wracać do miasta, w którym już były. Miasto do którego przemieści się mrówka wybierane jest losowo jednakże preferowane są miasta bliżej położone i te z
To co się na tych studiach robi? Myślałem, że to jedno z podstawowych zagadnień logistyki.
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ć -
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 :)
http://pokazywarka.pl/lrx232/
Komentarz usunięty przez moderatora
@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 zaprezentowano jednak