...
  •  

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

    •  

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

    •  

      @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.

    •  

      @Smiechol: Jeśli to jest logistyka na Uniwersytecie Ekonomicznym to głównie bezsensowne p!%@$?!enie i nauka o niczym.

    •  

      @Smiechol: pewnie omawiają problemy gender oraz zdobywają doświadczenie w wykorzystywaniu funduszy unijnych ;)

    •  

      @Sylar: to i tak dobrze macie na tej logistyce, na informatyce od zera musieliśmy implementować i optymalizować algorytm wraz z wizualizacją itd :)

    •  

      @Eoghan: poziom nie jest jakichś najwyższych lotów bo chyba najłatwiejsze studia inż na PRz ale powiem tak, jak ktoś chciał się czegoś nauczyć to się nauczył :)

    •  

      @Smiechol:
      Też tak myślałem :) Z tego co warte było zapamiętania, to systemy zarządzania zapasami, organizacja magazynów, infrastruktura logistyczna... Aha no i PRÓBA nauki systemu informatycznego dla logistyki - SAP przez 15h zajęć... (ciężko mi ogarnąć wyobraźnią ogrom możliwości aplikacji). Poza tym przedmioty typowe dla kierunków takich jak zarządzanie i ekonomia...

    •  

      @maciekst: To coś kiepsko uczyli chyba :P

    •  

      @loczyn: Kurde, po tym co pisaliście głupio mi się przyznać, no ale zrobię to - jestem na trzecim roku logistyki, właśnie kończę 5 semestr i też nie miałem tego problemu. Tzn. pewnie miałem w pewnym sensie w innej formie, ale nikt tego tak dosłownie, konkretnie nie poruszył. Ale szczerze mówiąc, chyba nie miałem wielu istotnych problemów poruszanych, trzeba sobie samemu ogarnąć niektóre kwestie na pewno, z resztą chyba na tym polega studiowanie jako takie :) Wydaje mi się, że logistyka w Polsce jest cały czas źle traktowana przez wykładowców - tzn. liczy się nadal wiedza książkowa, jakieś pierdoły sprzed powstania ludzkości, bo ktoś "mądry" napisał i to książka a nie internety co toto ludzie tylko głupoty wypisują, niż takie proste praktyczne problemy. Zakładam, że głównie wykładowcy starej daty są przyczyną.
      Albo inaczej - nie potrafią zrozumieć, że wszystko teraz tak pędzi, że jakaś gówno warta książka o logistyce sprzed 10 lat (czy podobnie o informatyce) jest już nieaktualna.

    •  

      @oner: Sęk w tym, że często wykładowcy NIGDY nie pracowali zawodowo. Prawdą jest jednak to, że bez solidnych case-study gówno się nauczysz.
      Na zachodzie dawno to zrozumieli więc szkoły przygotowują do zawodu, u nas studia w stylu radzieckim. Wykuj książki, zrób doktora, umrzyj jako siwy dziadek w leśnej chatce żyjąc cały czas ze stypendiów i innych socjalnych pomocy :P

    •  

      @loczyn: No właśnie miałem też o tym napisać - nawet bardzo często wykładowcy znają jedynie teorię, rzadziej są takimi prawdziwymi praktykami (a nawet jeżeli nimi byli, to dawno temu i dawno gówno prawda). Dlatego zawsze cieszę się, jak dowolnego przedmiotu uczy mnie ktoś, kto widzę że odnosi się do własnych doświadczeń, jest nadal na bieżąco z tematem lub chociaż go tak porządnie śledzi. Niestety - rzadkość :O

    •  

      @oner: Dlatego polecam zagraniczne uczelnie. Inne standardy.

    •  

      @loczyn: Heh, no pewnie :) Z resztą patrząc na zagadnienia z logistyki i polską literaturę, już wiem, że będę musiał dość mocno podłubać jeżeli chodzi o materiały do pracy, po polsku średnio tutaj zdziałam.
      W sumie to właśnie sobie coś uświadomiłem - nie spodziewałem się, że na tej uczelni będzie taka, w zasadzie, lipa, bo nie jest to raczej Wyższa Szkoła Logistyki i Wszystkiego Co Sobie Wymarzysz.

    •  

      @oner: A co to jest? Bo chyba nie pisałeś gdzie studiujesz :)

    •  

      @loczyn: A no nie napisałem :) Nie chcę, ale jest to uczelnia wyjątkowa w pewnym sensie - mało która w ogóle w Europie czy na świecie ma odpowiednie środki, aby uczyć studentów zwłaszcza jednego kierunku. Tzn na świecie pewnie trochę tego się znajdzie, ale raczej ciężko tutaj nawet z miliardami dotacji itd. I tak celowo zostawiam zagadkę, chociaż chyba łatwo wpaść na trop a później od razu wiadomo o co chodzi :)

    •  

      @oner: http://www.wscil.edu.pl/ ?:D
      Daj plusa jak trafiłem.

      A tak serio to odpuściłem sobie już studiowanie w Polsce. Szkoda czasu, nerwów i pieniędzy.

    •  

      @loczyn: No ja sobie teraz nie daruję, z resztą tragedii jakiejś nie ma, może zostałem źle zrozumiany. Po prostu myślałem, że będzie to raczej na bardzo wysokim poziomie (patrząc na wymagania stawiane pewnej grupie studentów). Nie wiem czy tu szukasz :) Tak bardzo podpowiem, bo aż jestem ciekawy czy wpadniesz o ile w ogóle ci się chce - uczą tam pewnych rzeczy tak specyficznych, że po prostu mało kto jest w stanie dostarczyć odpowiednich środków do nauki, zwłaszcza z praktycznej strony.

    •  

      @oner: Oj dziś to średnio mi się chce szukać.
      Swoją drogą jak patrze te galerie wykładowców na tych uczelniach to mnie smutek bierze :(

    •  

      @loczyn: A jak się jeszcze musisz z nimi użerać, to dopiero smutek bierze :)

      Ok, chodziło o pilotów, wszystko jasne :P

    •  

      @oner: Dziennie czy zaocznie? Płacisz czy publicznie?

    •  

      @loczyn: Dziennie, publicznie

    •  

      @oner: O tyle dobrze, że aż tak bardzo nie szkoda bo opłacają Ci inni, haha.
      Czasu tylko szkoda ;)

    •  

      @loczyn: Nie no może nie przesadzajmy, jak pisałem to nie jest żadna tragedia, po prostu spodziewałem się czegoś na wysokim poziomie. A tak to tak czy inaczej poznałem wykładowców i zdaje się, że tytuł inz. pomaga w rekrutacji (dodatkowe punkty), gdybym chciał po tym przenieść się do "drugiej kategorii studentów" tam :) Poza tym naprawdę jest co najmniej dobrze i w ogóle pewne specyficzne myślenie mi zostanie, już pomijając konkretne zagadnienia. No nieważne bo ciągniemy tu offtop chyba, chociaż to ważne co się dzieje na polskich uczelniach :P

    •  

      @maciekst: Pewnie jakieś WSL czy inne gówno..

    •  

      @lisekchz: Matematyka stosowana na drugim roku, na teorii grafów.

    •  

      @azn3: Ja to miałem na inżynierii systemów, kierunek logistyka, rok II

    •  

      @lisekchz:
      Politechnika Białostocka. Może to nie Harvard, ale spodziewałbym się więcej.
      pozdrawiam

    •  

      @Sylar: to i tak dobrze macie na tej logistyce, na informatyce od zera musieliśmy implementować i optymalizować algorytm wraz z wizualizacją itd :)

      @Eoghan: to źle? a co chciałeś robić na informatyce - w tomb raidera grać? nie każdy musi być programistą ale ten algorytm nie jest szczególnie skomplikowany.

    •  

      @power_user: bardziej chodzi o to, że na informatyce więcej z takiego podstawowego logistycznego problemu wynieśliśmy niż studenci logistyki :) Akurat sztuczna inteligencja była spoko, jeden z ciekawszych kursów, dosyć ciężki.

    •  

      @power_user: bardziej chodzi o to, że na informatyce więcej z takiego podstawowego logistycznego problemu wynieśliśmy niż studenci logistyki :)

      @Eoghan: bo to nie logistyka tylko parodia logistyki. Na logistyce ten problem byłby omawiany.

    •  

      @maciekst: No to ładnie. Jestem w technikum na profilu logistycznym i miałem już poruszany ten problem. Chyba nie mam po co iść na studia :D

    •  

      @maciekst:
      Jakim cudem nie miałeś jak ja to miałem na robotyce

    •  

      Jeśli to jest logistyka na Uniwersytecie Ekonomicznym to głównie bezsensowne p?$@!??enie i nauka o niczym.

      @Pivoo: niestety muszę się pod tym podpisać. j@%@ny festiwal zarządzania a nie logistyka

    •  

      @Smiechol: inzynieria systemow informatycznych - rok I lub II nie pamietam, pol semestru z b.fajna pania prowadzaca (logika) :P
      ps w mechanice kwantowej dystans wynosi do tego przykladu 0 :P

    •  

      teraz nie daruję, z resztą tragedii jakiejś nie ma, może zostałem źle zrozumiany. Po prostu myślałem, że będzie to raczej na bardzo wysokim poziomie (patrząc na wymagania stawiane pewnej grupie studentów). N

      @maciekst:
      Przecież na dyskretnej masz teorie grafów...

    •  

      @Eoghan: czesc, masz gdzies algorytm i wizualizacje? Mozesz sie podzielic?

    •  

      @doskasowania: możliwe, że gdzieś na dysku z backupem będzie, poszukam

    •  

      @Eoghan: super byloby! Bede mega wdzieczny i sie odwdziecze :)

  •  

    Podoba mi się dynamika tej prezentacji.

  •  

    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 większą ilością feromonu.
    Gdy wszystkie mrówki zakończą obchód wszystkich miast to feromon na wszystkich ścieżkach zmniejsza się o pewną wartość (parowanie). Ponadto feromon na ścieżkach, którymi przeszły mrówki zwiększa się o ilość odwrotnie proporcjonalną do całkowitej długości trasy danej mrówki (im krótsza trasa tym większy przyrost).

  •  

    Ciekawe, jak poradziłby sobie tabu search?

    •  

      @minuano68: UPS dla przykładu używa programu ORION. Tutaj można więcej o nim przeczytać http://www.forbes.com/sites/alexkonrad/2013/11/01/meet-orion-software-that-will-save-ups-millions-by-improving-drivers-routes/. Można też łatwo zauważyć korzyści wynikające ze stosowania takich algorytmów. Załóżmy, że optymalizacja jest w stanie zaoszczędzić kierowcy 30 minut mnożąc to przez liczbę kierowców i liczbę dni w roku przynosi to ogromną oszczędność czasu, a co za tym idzie, pieniędzy.

    •  

      @Pismak: Ciekawe, ile płacą za ten soft, skoro mogą aż tyle zaoszczędzić?

    •  

      @minuano68: dawno temu na studiach to badałem i tabu search radził sobie gorzej niż symulowane wyżarzanie. Za tym drugim przemawia też prostota implementacji. Testowałem jeszcze algorytm ewolucyjny i on też wypadł lepiej niż tabu search. Od razu zaznaczam, że to nie były poważne badania, więc nie należy tego co tutaj wypisuję brać za pewnik ;).

    •  

      @ghostface: Pewnie zależy od problemu. Tabu search był niezły w szeregowaniu zadań na procesorach. Tabu search moim zdaniem jest prosty. Szukasz lokalnie najlepszego rozwiązania, po czym dodajesz je na listę tabu, żeby móc przejść do zupełnie innych rozwiązań. I sprawdzasz, jak to działa dla różnej długości list tabu. Z głowy bym nie powiedział, jak działa symulowane wyżarzanie. Ten algorytm wydawał mi się trudniejszy.

    •  

      @ghostface:
      @minuano68: To chyba studiuję to samo, bo robię ten sam projekt. Porównanie czasu algorytmów tabu search, symulowanego wyżarzania i algorytmu genetycznego. Radzą sobie różnie, w zależności od wielkości instancji i dobranych parametrów/założeń przy implementacji każdego z nich. Symulowane wyżarzanie jest proste w implementacji i ma najlepsze wyniki dla małych instancji problemu (kilkadziesiąt wierzchołków), tabu search radzi sobie czasem lepiej, czasem gorzej, najlepiej w średnich instancjach, natomiast algorytm genetyczny radzi sobie najlepiej (zwłaszcza dla dużych instancji (kilkaset wierzchołków)), ale dla mniejszych wykonuje się zdecydowanie dłużej. Także jeśli iść na kompromis pomiędzy jakością i czasem wykonania, to wygra chyba tabu search na równi z symulowanym wyżarzaniem, ale plusem tego drugiego jest prostota wdrożenia i obsługi.

    •  

      @Mave: W-4 PWr, tak? Kto teraz to prowadzi, skoro zamknęli cały zakład?

    •  

      @ghostface: dawniej był to dla nas ZSZ - Zakład Szeregowania Zadań :-P

    •  

      @minuano68: Nie tak dawno na studiach jako część pracy licencjackiej bawiliśmy się między innymi metrycznym TSP. Tabu searcha nie sprawdzaliśmy. Dla małych instancji najlepiej wypadał Christofides wspierany Blossomem V. Wyżarzanie wypadało de facto gorzej niż zwykły hill climb. Monte Carlo Tree Search wypadał bardzo słabo. W obecnej chwili najlepszy algorytm to LKH to jest k-opt który się adaptuje do sytuacji.. magic.

    •  

      @ghostface: Tak ;) Wykład prowadzi dr Makuchowski i to nawet w ciekawy sposób, wydaje się być bardzo w porządku, zobaczymy jak z zaliczeniem. Projekt przejęła doktorantka, laboratorium ona + ktoś tam jeszcze, generalnie przedmiotem zajmują się teraz niezbyt znani ludzie co mnie cieszy, bo zaraz po wyjściu afery na światło dzienne krążyły plotki, że przedmiot przejmuje profesor "Ostateczny sumator" B.

    •  

      @WhosYourDaddy: Widzę, że mam pewne zaległości. Po studiach chyba nie tak łatwo znaleźć robotę, w której można by rozwiązywać takie problemy. Komuś się poszczęściło?

    •  

      minuano68
      @minuano68:
      @ghostface:
      @Mave:
      Takie pytanie panowie, a czy w takich problemach mają szanse implementacji algorytmy gradientowe? W obszarze w którym prowadzę badania: optymalizacji dowolnych funkcji bardzo wydajny jest algorytm Levenberga-Marquardta, spotkaliście się może z nim na waszych studiach?

    •  

      @staszko90: nie spotkałem się z tym algorytmem w kontekście tego problemu.

    •  

      @ghostface: Tak tylko z ciekawości pytam, bo w przypadku optymalizacji funkcji, algorytmy gradientowe są w większości przypadków o wiele, wiele szybsze i bardziej zbieżne niż algorytmy symulowanego wyżarzania i genetyczne. Ale warto wiedzieć gdzie można je zastosować. Dzięki wielki!

    •  

      @staszko90: Jak zadasz różniczkowalną funkcję ciągłą na przestrzeni problemu to masz szansę. Ja tutaj takiej funkcji nie widzę chyba, że powiemy że każdy wierzchołek ma mieć w sumie stopień wejścia 1 i wyjścia też 1 i dopuścimy krawędzie z wagą [0,1], no ale potem jakoś trzeba będzie zdyskretyzować (pewnie takie slowo nie istnieje, czyli przejsc do dziedziny liczb calkowitych) co nie wydaje sie oczywiste.

      @minuano68: Niet, co prawda jeden pisze teraz magisterke z jakiegos uogolnionego problemu plecakowego i po studiach jest szansa ze zostanie na uczelni, a reszta z nas jakies bardziej praktyczne rzeczy na magisterke robi, a potem do USA po $ :)

    •  

      @WhosYourDaddy: Dzięki, btw słowo którego szukałeś to skwantować:) (czyli zdyskretyzować w przestrzeni wartości funkcji)

  •  

    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 algorytmu optymalizującego.

    •  

      @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.

    •  

      @WesolyMorswin: w praktyce jest też branych wiele innych rzeczy pod uwagę jak np. to do której pracuje dana firma gdzie ma dojść przesyłka albo jakiś okreslony czas dostarczenia. Kwestia co bierzesz pod uwagę

  •  

    Lol, możliwych tras jest duuuużo więcej od liczby cząsteczek we wrzechświecie.

  •  

    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.

    •  

      @Sarseth: Sprawdzamy wszystkie połączenia. Dziękuje, dobranoc.

      pokaż spoiler "Gdzie jest k@?$a moje trzysta baniek, słyszysz?"

    •  

      @Dakkar: To algorytm o zlozonosci wykladniczej

    •  

      @Ragnarokk: Si, szukam geniuszów.

    •  

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

    •  

      @Sarseth:
      Z tego co kojarzę, to raczej podejrzewa się, że równości nie ma. Ale niech próbują :)

    •  

      @Ragnarokk:
      Wynika to z tego, że problemy klasy P zawierają się w problemach klasy NP, ale nie wszystkie problemy z klasy NP da się rozwiązać w klasie P w czasie wielomianowym.

    •  

      @Incognix:

      nie wszystkie problemy z klasy NP da się rozwiązać w klasie P w czasie wielomianowym.

      Hm - wiesz o tym, że to co piszesz właśnie oznacza dokładnie to, że P != NP? A udowodnienie tego jest warte milion dolarów + wielka sława w świecie matematyki i informatyki. Więc jak wiesz taką rzecz, to musisz być bardzo bogatym człowiekiem.

    •  

      @Ragnarokk: Podejrzewam, że być może źle zrozumiałem pojęcia zawierania się tych klas oraz ich problemów, co powoduje, że muszę zweryfikować moją wiedzę. Gdybyś teraz nie zwrócił mi uwagi na to co napisałem, to bym pieprznął gafę na egzaminie i być możę bym trwał nadal w błędnym przekonaniu :P
      Chyba, że te założenie co napisałem to jest tylko jedno z założeń które mogły pomóc w rozwiązaniu tego problemu. Bo pewne problemy P są rozwiązywalne przez NP, ale nie każdy problem NP da się rozwiązać w klasie P, gdyż obecnie występują ograniczenia w postaci mocy obliczeniowej komputera, który w definicji może spełniać założenia deterministycznej MT.

    •  

      @Incognix:
      To jest tak. Wszystko, co jest w P jest też w NP - tu dowód jest prosty, ten sam algorytm co rozwiązuje problem w czasie wielomianowym także weryfikuje problem w czasie wielomianowym. Rozchodzi się o należenie w drugą stronę. Jest całe morze problemów, co do których nie znaleźliśmy algorytmów wielomianowych, ale też nie udowodniliśmy, że takie algorytmy na pewno nie istnieją. I tutaj nie chodzi o moc obliczeniową, to jest matematyka i w uzywanym standardowo modelu te problemy nie są obliczalne w czasie wielomianowym. Być może istnieją, ale póki co ludzkości te algorytmy znane nie są. Jeśli by udowodniono, że P=NP, to wynikałoby, że takie algorytmy istnieją. (i na odwrót - pokazanie algorytmu wielomianowego dla problemu NP-zupełnego rozwiązuje problem P=NP?) Jeśli P !=NP to znaczy, że nie istnieją.
      Nie tak dawno znaleziono algorytm wielomianowy na rozkład liczby na czynniki pierwsze. Ale ten problem należy do co-NP, nie do NP.

  •  

    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 życie na matematyce, pokazuje jak bardzo wykres funkcji zmienia się w danym punkcie (w uproszczeniu). To znaczy, że jak mamy np. funkcję y=2x - jej pochodna wynosi 2 w każdym punkcie. Znaczy to, że w każdym punkcie 'wzrost' tej funkcji będzie wynosił 2. Łatwo to sobie zobrazować - dla x = 1 y = 2, dla x = 2 y = 4. Sam przez całe liceum i studia byłem nieświadomy zajebistości pochodnej, więc podejrzewam że jest wielu takich jak ja :P.

    Warto również wspomnieć, że nie tylko firmy kurierskie korzystają z tego typu algorytmów do wyszukiwania trasy - większość z nas korzysta z tego od czasu do czasu używając GPSa na komórce. W końcu trasa w jakiś sposób na naszym smartfonie musi się wyszukać, prawda?

    •  

      @Pivoo: Co do pochodnej zgadzam się, niedawno też odkryłem do czego ona może służyć i faktycznie jest to bardzo ciekawy rachunek :)

    •  

      @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.

    •  

      Komentarz usunięty przez autora

    •  

      @Pivoo: Użycie pochodnej nie nadaje się do rozwiązywania problemu komiwojażera (dla bardzo dużej liczby rozwiązań), gdyż algorytmy oparte na pochodnej są algorytmami szybko zbieżnymi i nie są odporne na minima (maksima) lokalne. Do rozwiązywania tego typu problemów używa się głównie algorytmów z rodzaju 'obliczeń inteligentnych', czyli symulowanego wyżarzania, algorytmów mrówkowych, algorytmów ewolucyjnych, logiki rozmytej, czy sztucznych sieci neuronowych. Ten problem w rzeczywistości jest o wiele bardziej skomplikowany, gdyż w życiu jest to problem wielokryterialny (istnieje wiele czynników mających wpływ na optymalne rozwiązanie, np. nie tylko długość trasy, ale także koszt paliwa, czas przejazdu, komfort kierowcy, itd.) zaś środowisko jest niestacjonarne (zmienne warunki pogodowe, remonty, wypadki, itd). Algorytmy korzystające z obliczeń inteligentnych pracują ostro w wielu dziedzinach życia i ludzie (szarzy) nawet nie zdają sobie sprawy, że rządzą one na rynkach finansowych, giełdach, itd.

    •  

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

    •  

      @DanioPL: Jak udowodni, że P=NP to takim milionem będzie mógł ścierać swój szafirowy blat kuchenny.

    •  

      http://pl.wikipedia.org/wiki/Algorytm_Dijkstry
      To jest zapewne najprostszy algorytm jaki do tej pory wymyślono do problemu komiwojażera.


      @Pivoo: Ja jebie. Nawet nie wiem jak to skomentować.

  •  

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

  •  

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

    •  

      @kote: Którego? :-) Tutaj chodzi o to, że przy rosnącej liczbie wierzchołków (miast), liczba możliwych połączeń między nimi rośnie wykładniczo więc, żeby sprawdzić która droga jest optymalna, trzeba by sprawdzić wszystkie możliwe połączenia. Jak widziałaś przy 304 miastach możliwych połączeń jest 2,3*10^624 czyli hmm.. sporo.

    •  

      @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: Koledze zapewno chodzi o to, że w pewnym momencie komputer sobie nie poradzi. Rozwiązanie problemu znane jest od dawna. Tzn. analizuje się wszystkie możliwe drogi i szuka najkrótszej. Problem jednak w tym, że przy pewnej ilości miast komputer nie daje już rady. Pewnie komputer o którym wspominasz, wykonuje dla liczby powiedzmy 300 miast to kilkudziesięciokrotnie szybciej niż tradycyjne, ale gdy zaaplikujesz mu powiedzmy 700 to zajmie mu to kilka lat. (Liczby oczywiście biorę z kosmosu)

    •  

      @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 zaprezentowano jednak tego w praktyce, Orion wykonywał jakieś mniejsze zadania (jakieś sudoku i rozsadzenie gości na weselu). Jako ciekawostkę mogę przytoczyć fakt, iż "– na obliczenie trasy komiwojażera dla liczącej 24.978 miejscowości Szwecji dobry współczesny PC potrzebowałby około 85 lat" - tyle podano w prezentacji :P

      Przepraszam, kajam się :3

    •  

      @givdaf: Stosuje się algorytmy. Nie sprawdza się wszystkich możliwości.

    •  

      @Dakkar: Tak, ale jeszcze nikt nie wymyślił bezbłędnego algorytmu. Zdaję się, że już potrafią liczyć z prawdopodobieństwoem około 99% optymalności, ale dalej nie jest to 100% optymalne. A tak można sprawdzić tylko poprzez analizę wszystkich możliwości. Dlatego cały czas amerykaństa fundacja płaci milion dolarów osobie, która wymyśli algorytm, który będzie bezbłędnie wyliczał optymalną trasę, bez konieczności badania wszystkich możliwych dróg.

  •  

    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.

  •  

    Do dupy ten algorytm, poprawne rozwiązanie :
    http://pokazywarka.pl/lrx232/

  •  

    Ktoś ma informacje jakich algorytmów wyznaczania tras (w kolejności) używa Google Maps?

  •  

    Problem znany z dziedziny inżynierii systemów logitycznych.

  •  

    Miałem to na badaniach operacyjnych na UE w Poznaniu. Pozdrawiam wszystkich, którzy musieli przez to przejść ;)

  •  

    Nic nie wspomnieli o metodach znajdywania rozwiązań optymalnych problemu komiwojażera (opartych np. na programowaniu ograniczeniowym ).
    Swego czasu napisałem bibliotekę do jednego z open-source-owych systemów do optymalizacji kombinatorycznej, która służy do znajdywania "Cyklu Hamiltona", o najniższym koszcie, w grafie (bo do tego sprowadza się problem komiwojażera). Załączam link do biblioteki i przykładu z Polskimi miastami :)
    http://eclipseclp.org/doc/bips/lib_public/cycle/index.html

  •  

    Nie wiedziałam, że w USA rozwożą pocztę helikopterem. A nie taniej by było kupić sobie drugi?

  •  

    Wszystko ładnie i pięknie dopóki nie okaże się że mamy nie tylko wiele miejsc do odwiedzenia ale też wielu kurierów. A jak się na dodatek okaże że mamy ograniczoną pojemność i różne ilości przesyłek do odebrania w poszczególnych miejscach to robi się zabawa na całego.

  •  

    a pro po tematu: w ubiegłym tygodniu miałem taką sytuację, że zadzwonił do mnie kurier, że ma dla mnie przesyłkę, i czy mógłbym dojechać 2 km do większej miejscowości. Odpowiedziałem mu, że nie, na co on od razu zaproponował inny dzień. Gdy zapytałem go dlaczego, to stwierdził, że droga do mojej miejscowości jest oblodzona, i że nie może przyjechać.
    Dodam tylko, że nie jest to żadna droga szutrowa, tylko normalna asfalt po którym co chwilę jedzie jakiś samochód. Fakt, jest ślisko, ale jak to powiedziała nasza Pani minister infrastruktury: Sory - taki mamy klimat.

    Czy w ogóle kurier ma prawo odmówić przyjazdu ze względu na śliską drogę? Dzwoniłem do DPD (bo to ich kurier) i Pani nie była w stanie odpowiedzieć mi na to pytanie. A ponieważ zależało mi niesamowicie na tej przesyłce to następnego dnia musiałem sam podjechać po tą paczkę te 2 km.

  •  

    Nikt nie zakopie ? ; ) Rekord chyba. Prawie tysiąc bez zakopania.

  •  

    OOOO proszę. W końcu coś co mieli Wykopki na studiach i są w stanie coś napisać.
    Bo o prawdziwym życiu, nie z książki, nic nie wiedzą !

  •  

    Komentarz usunięty przez autora

  •  

    To było naprawdę ciekawe.

  •  

    Ciekawe podejście, jednak tylko w teorii. Co w przypadku gdy klient jest nieobecny i nie odbierze przesyłki?

  •  

    To nic niezwykłego sam kiedyś milem napisać na zaliczenie program rozwiązujący ten problem jest wiele algorytmów ja stosowałem genetyczny ale mrówkowy o którym wspominano też jest dość ciekawy :)

  •  

    Matematyka, fuck yeah.

  •  

    Zasadniczo to wychodzi, że trzeba w kółko jechać po miastach :)

  •  

    O co tu chodzi? Ktoś to wyjaśni? Dlaczego nie można po prostu ustalić normalnej trasy od miasta do najbliższego miasta, tylko trzeba jakichś programów używać? Nie wystarcza po prostu kartka i długopis i się łączy punkciki tak jak w pierwszym przykładzie na tej prezentacji?

  •  

    Czyli wszystko dąży do kształtu koła... pewnie ma to związek z tym, że kształt koła ma najkorzystniejszy stosunek pole-objętość.

  •  

    Problem korwijeża?

  •  

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

    •  

      @koscik: Przyznaj po prostu, że fajnie się to ogląda a nie wymyślaj "usprawiedliwień" dla powtórnego oglądnięcia.

    •  

      @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ć - jak nie dotrze na czas, to przecież i tak mamy funkcję kary i algorytm ładnie sobie znajdzie niezłe rozwiązanie. W funkcji fitness można zawrzeć masę danych. Proste w implementacji, wcale nie takie wolne i można łatwo dowolnie problem rozszerzać o masę kryteriów. Co więcej taki program może napisać każdy śmiertelnik, który choć trochę programowanie ogarnia.

    •  

      @koscik: Właśnie coś takiego bardzo by mi się przydało, gdyby było gdzieś w opcjach google earth. Mam sobie pooznaczanych klientów w GE i chciałbym żeby mi pokazał optymalną trasę zahaczając o wybranych klientów. Może coś takiego już gdzieś istnieje, a ja o tym nie wiem? Jeśli ktoś wie gdzie to znajdę to będę ogromnie wdzięczny.

    •  

      @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 :)

    •  

      @koscik: niczego nie przedstawialismy..

    •  

      @koscik: No właśnie o to mi chodziło :) Dzięki ogromne za ten link.

Dodany przez:

avatar P...k dołączył
1240 wykopali 1 zakopali 36.7 tys. wyświetleń