TSP (Travelling salesman problem)

Zaczęty przez AL, 19 Październik 2007, 02:53

AL

Strona główna: TSP (TSP na naszej Wiki).

CytatAbout TSP
TSP is a research project that uses Internet-connected computers to find a solution to a 48 node traveling salesman problem. You can participate by downloading and running a free program on your computer.

Drużyna

TJM

Z tym, że nie bardzo da się podłączyć:


W razie jakiejś pilniejszej sprawy - jestem często dostępny na kanale IRC B@P, na forum czasami zapominam zajrzeć lub nie mam czasu.

RAD-Poland

zgadza się
przyłącz się przez przygotowany link AL'a (w poscie wyżej)

   
WCG:
PG:         YOYO:

     

TJM

Z jakiegoś powodu team jest oznaczony jako nieaktywny, dlatego nie da się podłączyć przez team search.

W razie jakiejś pilniejszej sprawy - jestem często dostępny na kanale IRC B@P, na forum czasami zapominam zajrzeć lub nie mam czasu.

AL

Może jest dopiero aktywny jak ktoś w nim zdobędzie jakieś punkty (Ja narazie mam całe 0,1  :?  ). Po drugie to nowe rozwiązanie i jak widać wymaga jeszcze pewnego dopracowania.

RAD-Poland

teraz funkcja działa  8)
a może trzeba było odznaczyć opcję "Show only active teams"
sprawdzimy przy kolejnym nowym projekcie
mój wynik to 2,96 ale zbliżam się limitu dziennych wu na wszystkich moich hostach (1+2vm) :wink:

   
WCG:
PG:         YOYO:

     

jaskij

złożoność O(n^2*2^n)... dla n=48... daje nam 648518346341351424 czyli ~6,48*10^17 kroków.... mogę się mylić, ale jak na mój gust nie jest to aż tak dużo pracy... dysponując mocą obliczeniową właściwą dla BOINCa możnaby obliczyć rozwiązanie tego problemu, dla np. 100 tys. miast
Cytat: "Wiki"
In March 2005, the travelling salesman problem of visiting all 33,810 points in a circuit board was solved using CONCORDE: a tour of length 66,048,945 units was found and it was proven that no shorter tour exists. The computation took approximately 15.7 CPU years (Cook et al. 2006). In April 2006 an instance with 85,900 points was solved using CONCORDE, taking over 136 CPU years, see the book by Applegate et al [2006] .
no chyba, że liczą pełnym przeglądem, o O(n!).... to daje nam ~1,24*10^61... i tu mamy "ciut" więcej (jakieś 1,91*10^43) pracy ;P ale jest to algorytm dość nieoptymalny ;P
Jak zaczną liczyć coś konkretniej, to dajcie znać ;P

TJM



co dokładnie ten błąd oznacza ? Pierwszy raz takie coś widzę :O

W razie jakiejś pilniejszej sprawy - jestem często dostępny na kanale IRC B@P, na forum czasami zapominam zajrzeć lub nie mam czasu.

jaskij

:D jak miło :D to co widać :D twórcy TSP sobie powymyślali zbyt skomplikowany graf, tudzież pamięciożerny algorytm :D tudzież cuś w tym stylu :D przynajmniej tak mi się wydaje :D zazwyczaj aplikacja zajmuje stałą ilość pamięci, ale w tym wypadku widać jest alokowana dynamicznie :D i jej zabrakło :D ale to tak tylko strzelam :D a Ty się TJM nie baw w TSP, tylko licz SETI, przynajmniej na Gauntleta :D

TJM

Upgrejdnąłem managera do wersji 5.10.26, bo i tak muszę coś sprawdzić, teraz pokazuje mi Waiting for memory, tak jakby czekał, aż pójdę do sklepu i dokupię.
To zadanie nie różni się niczym od innych :O
Tak w ogóle to do czego pamięci może jeszcze brakować, jak zadanie jest zakończone ?


W razie jakiejś pilniejszej sprawy - jestem często dostępny na kanale IRC B@P, na forum czasami zapominam zajrzeć lub nie mam czasu.

Pigu

nie narzekaj, tylko zwlacz się już do sklepu :mrgreen:

Bober

A sprawdź jakie masz ustawienia użycia pamięci w tym projekcie. Czasami ustawienie np. na 90% when in use, przynajmniej na chwile, pomaga.

TJM

Mam tak cały czas ustawione, inne zadania sie przeliczają, tylko to jedno się zaklinowało.

W razie jakiejś pilniejszej sprawy - jestem często dostępny na kanale IRC B@P, na forum czasami zapominam zajrzeć lub nie mam czasu.

deway

#13
Czy ktoś wie co się dzieje z projektem TSP@home?

Trzeba uaktualnić dwa artykuły na Wiki, bo linki są martwe i ten projekt nie ma statusu czy żyje czy nie:
TSP@home
Lista_projektów
"Szaleństwo: robić wciąż to samo, a oczekiwać różnych rezultatów" Albert Einstein