:]

Ciastka!

Strona korzysta z plików cookies w celu realizacji usług i zgodnie z Polityką Plików Cookies. Możesz określić warunki przechowywania lub dostępu do plików cookies w Twojej przeglądarce.

  •  

    pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @maciekst: To coś kiepsko uczyli chyba :P

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @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

    •  

      pokaż komentarz

      @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

    •  

      pokaż komentarz

      @oner: Dlatego polecam zagraniczne uczelnie. Inne standardy.

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @loczyn: Dziennie, publicznie

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      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

    •  

      pokaż komentarz

      @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

    •  

      pokaż komentarz

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

  •  

    pokaż komentarz

    Podoba mi się dynamika tej prezentacji.

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

    Ciekawe, jak poradziłby sobie tabu search?

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      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?

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

  •  

    pokaż komentarz

    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?

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

    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.

    •  

      pokaż komentarz

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

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

    •  

      pokaż komentarz

      @Dakkar: To algorytm o zlozonosci wykladniczej

    •  

      pokaż komentarz

      @Ragnarokk: Si, szukam geniuszów.

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

  •  

    pokaż komentarz

    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?

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      Komentarz usunięty przez autora

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

  •  

    pokaż komentarz

    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.

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

    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

  •  

    pokaż komentarz

    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.

  •  

    pokaż komentarz

    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.

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

    To było naprawdę ciekawe.

  •  

    pokaż komentarz

    Komentarz usunięty przez autora

  •  

    pokaż komentarz

    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ą !

  •  

    pokaż komentarz

    Matematyka, fuck yeah.

  •  

    pokaż komentarz

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

  •  

    pokaż komentarz

    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?

  •  

    pokaż komentarz

    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ść.

  •  

    pokaż komentarz

    Problem korwijeża?

  •  

    pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

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

    •  

      pokaż komentarz

      @koscik: niczego nie przedstawialismy..

    •  

      pokaż komentarz

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