TSP (Travelling salesman problem)

[AL]

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

About 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ć:

[RAD-Poland]

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

[TJM]

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

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

[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

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

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

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

[deway]

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