Strona 2 z 2 PierwszyPierwszy 12
Pokaż wyniki od 11 do 12 z 12
Like Tree2Likes

Wątek: Optytmalne dzielenie odcinków

  1. #11
    Programista Awatar Aravorn
    Dołączył
    Apr 2011
    Posty
    343

    Domyślnie

    No to wychyl głowę poza Wikipedię odnośnie problemu plecakowego i jego rozwinięć Bo do tego problemu się nadaje dobrze.
    Problem wydawania reszty też dostosować do tego można, żeby dobrze działał, jeżeli się nad tym pomyśli.

    Ogólnie klasyczne podejścia odpadają w większości, bo to przede wszystkim optymalizacje bąbelkowania, ze złożoności 30! (silnia) robi się mniejsza, ale to i tak wiele, czas liczony w tryliardach lat jak nie lepiej.
    Z technik heurystycznych polecam Simulated Annealing, algorytm mrówkowy itd. - pisałem na matematykę dyskretną na zaliczenie program do problemu komiwojażera i dla przykładu dla 100 punktów wyznaczał prawie optymalną trasę w czasie < 1 sekunda.
    Heurystyki mają właśnie to do siebie, że są to rozwiązania przybliżone, ale dobrze przybliżone. W celu poprawienia wyniku / zmniejszenia prawdopodobieństwa błędu wykonuje się ponownie algorytm dla wprowadzonych danych itd. ile tam się ustali, do czasu uzyskania zadowalającego efektu. Symulowane wyżarzanie - uproszczony opis, pisany do algorytmu do TSP (komiwojażera, ale nie tylko w sumie):
    Losujemy / ustalamy dowolną ścieżkę, np. zgodnie z indeksami elementów: 0 -> 1 -> 2 -> .. -> n
    Generujemy dla danej temperatury inne rozwiązanie. Jeśli prawdopodobieństwo wylosowania lepszego będzie mniejsze od pewnej wartości, wykonujemy następny krok. Jeżeli przez k cykli dane rozwiązanie będzie najlepsze, kończymy program
    Zmniejszamy temperaturę i powtarzamy poprzedni krok
    Gdy temperatura spadnie poniżej minimum lub k razy otrzymamy to samo rozwiązanie, jest ono PRAWDOPODOBNIE najlepszym

    Ogólnie Twój problem należy do klasy problemów NP-trudnych, musisz skorzystać z bardziej zaawansowanych technik.
    Dobra optymalizacja dla klasycznego podejścia do branch and bound: jak robiliśmy testy dla grafu pełnego (a w rzeczywistości to jest powiązane z Twoim problemem) dla 12 wierzchołków bąbelkowa metoda wykonywała obliczenia w ciągu 6 minut, branch and bound kilka sekund bodajże (kolega to pisał, nie pamiętam), moja implementacja w czasie prawie natychmiastowym (ciężko to określić, gdy się pozna ten algorytm, gdyż bazuje na losowości i aproksymacjach).


    Skąd moje nawiązanie do grafów i to wszystko co pisałem? A no bo Twój problem też można przestawić jako pewną funkcję, krzywa linia długa bardzo i program ma znaleźć globalne minimum, potrafiąc przy tym wychodzić z minimów lokalnych - simulated annealing jest proste i pozwala właśnie na to.

    Wniosek:
    Nie ma algorytmu optymalnego pod każdym względem. Masz algorytmy optymalne pod względem poprawności rozwiązania, ale o bardzo długim czasie działania, jak te wspomniane tryliardy lat. Dynamicznie masz optymalizację czasu do ułamków sekundy itd. ale rozwiązanie niekoniecznie będzie 100% najlepsze, to tylko aproksymacja. Wielokrotne uruchomienie drugiego typu algorytmów i wybieranie co raz lepszej aproksymacji pozwala uzyskać aproksymację, która to z co raz większym prawdopodobieństwem będzie najlepsza.

    Uzupełnienie 2:
    Tak, uprzedzając z góry technika opisana wyżej może dobrze posłużyć do rozwiązania problemu plecakowego.
    Problem wydawania reszty zmodyfikowany może posłużyć w ujęciu Twojego problemu, a wspomniałem o tym ponieważ są opisane w publikacjach naukowych dostępnych w sieci bardzo dokładne i szybkie algorytmy, przy podejściu jeszcze innym niż wspomniałem i da się to do Twojego problemu dostosować i wykorzystać

    Tą samą odpowiedź wklejam na php.pl
    Ostatnio edytowane przez Aravorn ; 30-07-2013 o 13:27
    proklin likes this.

  2. #12
    Programista
    Dołączył
    Sep 2007
    Posty
    622

    Domyślnie

    Faktycznie bruta nie przejdzie. Tak teraz się zastanawiam jakim cudem wmówiłem sobie że jest inaczej
    http://orodlin.pl/ - Orodlin.pl Team Member
    http://blog.albitos.eu - Albi's Jogger - Z pamiętnika młodego programisty
    http://wsosnowski.pl - wizytówka

    Mam do wynajęcia miejsce na serwerze dedykowanym. Ktoś zainteresowany?

Strona 2 z 2 PierwszyPierwszy 12

Informacje o wątku

Użytkownicy przeglądający ten wątek

Aktualnie 1 użytkownik(ów) przegląda ten wątek. (0 zarejestrowany(ch) oraz 1 gości)

Podobne wątki

  1. Problem z chatem do gry(dzielenie chatu na iframe i emotikony)
    Przez GibonZiom w dziale Problemy przy tworzeniu własnej gry
    Odpowiedzi: 0
    Ostatni post / autor: 06-10-2010, 19:20
  2. [php]dzielenie i wynik z przecinkiem.
    Przez haxigi w dziale PHP / MySql
    Odpowiedzi: 11
    Ostatni post / autor: 08-05-2010, 23:02
  3. Dzielenie rekordów na strony
    Przez Veter w dziale Budowa gry via www
    Odpowiedzi: 5
    Ostatni post / autor: 28-04-2010, 19:06
  4. Dzielenie bez reszty
    Przez mordeto w dziale PHP / MySql
    Odpowiedzi: 5
    Ostatni post / autor: 04-11-2007, 22:46

Zakładki

Uprawnienia umieszczania postów

  • Nie możesz zakładać nowych tematów
  • Nie możesz pisać wiadomości
  • Nie możesz dodawać załączników
  • Nie możesz edytować swoich postów
  •