Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Problem komiwojażera. Szukam prostego algorytmu.

vacpan 12 Cze 2007 16:58 12042 5
  • #1 12 Cze 2007 16:58
    vacpan
    Poziom 19  

    Szukam prostego algorytmu rozwiązującego problem komiwojażera. Algorytm sprawdzający wszystkie możliwości już mam, ale potrzebuje czegoś trochę szybszego a jednocześnie nie za bardzo skomplikowanego. Najbardziej bym się ucieszył z przykładu w C ale za pseudokod też będe wdzięczny.

    0 5
  • #2 12 Cze 2007 18:01
    Sam Sung
    Poziom 30  

    Nie wiem, czy przeglądałeś już linki z angielskiej wikipedii - http://en.wikipedia.org/wiki/Travelling_salesman_problem - są tam jakieś przykładowe rozwiązania, np. http://members.pcug.org.au/~dakin/tsp.htm .
    A tu jest aplet z rozwiązaniem przy pomocy algorytmu genetycznego: http://cs.felk.cvut.cz/~xobitko/ga/tspexample.html (chyba bez źródeł).

    0
  • #3 12 Cze 2007 18:07
    Oberon
    Poziom 15  

    Robiłem kiedys komiwojadzera 2 sposobami:

    Genetycznie (na podstawie http://www.k0pper.republika.pl/geny.htm)
    Oraz klasycznie

    C++ z wizualizacja w OpenGLu

    moge podesłac jak bys chciał ale cos wizualizacje mam niedopracowana (czasem sie faka :cry: )

    czolem
    Oberon

    0
  • #4 13 Cze 2007 00:14
    vacpan
    Poziom 19  

    W C++ raczej odpada, bo najpierw bym musiał nauczyc sie C++ . Ale dzieki za zainteresowanie. Znalazlem coś co sie nazywa algorytm z wykorzystaniem programowania dynamicznego ale nie bardzo to rozumiem.

    0
  • #5 19 Cze 2007 12:14
    yakuzam
    Poziom 1  

    Najlepiej problem komiwojadzera obliczją algorytmy genetyczne. mam taki program , gdzie wczytujesz do niego wczesniej zdefiniowane ( wsp pkt , miejscowosci) a on szuka najkrutszej drogi i czasu program nazywa sie komigen.exe bardzo prosty

    0
  • #6 19 Cze 2007 12:40
    wmaster
    Poziom 2  

    Nie są znane wielomianowe algorytmy rozwiązujące ten problem. Używając programowania dynamicznego jest algorytm O(2^n * n^2).

    Zasada działania dynamika
    Jak sama nazwa wskazuje bedzięmy tą drogę konstruować z czasem działania algorytmu. Musimy mieć jakąś strukturkę, która będzie przechowywała informacje gdzie jesteśmy, długość trasy oraz co już odwiedziliśmy (najlepiej jakaś maska bitowa, lub zwykła tablica dla małych danych).

    Wrzucamy do kolejki wszystkie miasta po kolei.
    W kolejce odczytujemy tą strukturkę, czyli gdzie jesteśmy, etc. Bierzemy wszystkich sąsiadów (nieodwiedzonych) tego miasta i wrzucamy znowu do kolejki modyfikując oczywiście odwiedzonych, dł trasy, oraz ostatnie miasto.

    Pozdrawiam

    2