BOINC.TSP - Hier gibts Rechenbedarf

[Iver]

Moin Leute,
ich bin seit einiger Zeit bei dem Projekt "TSP (http://bob.myisland.as/tsp/)" (Traveling Salesman Problem) dabei, und wollte hier mal ein bisschen Unterstützung einwerben. Mit meinen knapp 1.500 und ein bisschen Punkten pro Tag (im Augenblick akkumuliert: knapp 16.000) liege ich zwar weltweit unter den ersten 30 (von etwa 850), da geht aber noch was.

Ihr seht, hier gibts mit ein bisschen Wumms noch ordentlich Spitzenplätze einzufahren, speziell auch für unser Team SETI.Germany (http://bob.myisland.as/tsp/team_display.php?teamid=1). Übrigens hat unser Gründer Saenger nicht nur derart schnell reagiert, daß wir die Team-Nummer 1 haben, sondern er selbst hat es tatsächlich geschafft, die User-ID 2 einzuheimsen. Applaus dafür! :x)

Kommt zu uns, dann schubsen wir die anderen Teams (http://bob.myisland.as/tsp/top_teams.php) aus dem Weg!

Axso, worum es überhaupt geht: Wenn ein Handelsreisender verschiedene Orte besuchen will, so muss er eine optimale Route finden. Es gibt bisher keinen perfekten Algorithmus hierfür, der auch tatsächlich mit vielen Zielen auf einmal funktioniert. Also hat der Entwickler sich das Ziel gesetzt, einerseits die optimale minimale Strecke zwischen den 48 aneinandergrenzenden US-Bundesstaatshauptstädten mit brachialer Rechengewalt (eben BOINC..) zu finden, andererseits genetische Algorithmen zu finden, die sich an den Ergebnissen messen lassen können sollen müssen. ;)

[Iver]

Eine letzte Bemerkung noch zum voraussichtlichen Rechenaufwand (ohne Optimierungen): Es werden 48!/2 Wege geprüft, das sind 6,20696*10^60 Möglichkeiten.... Jede WU prüft davon etwa 40.000.000 Möglichkeiten. Ich zitiere mal aus dem Forum aus einem Beitrag des Betreibers:


"The big problem here is that I'm really not a mathematician. There are 48!/2 unique paths. The way I generate paths I'll end up going through each one twice. This is a HUGE waste of time, although it does allow for some redundancy which is not all that bad.

Workunits have a prefix of 37 cites,and a suffix of 11 cites. A workunit tries all 11! paths and returns the shortest one found. Just the other day I realized that I recalculate the distance of the prefix every time, when what I should do is precalculate the prefix, and only add the suffix part.

TSP started as just a proof of concept, I never in a million years thought it would be where it is today. I'll be looking into, and adding optimizations to the original app as time allows, but I'm more focused on different search algorithms. The brute force method is the only one that guarantees you find the optimal path(s), and I'm slowly learning there are mathematical "tricks" to eliminate large portions of the search space which can be proven to be suboptimal. I have not figured out how to implement it."

[marodeur6]

Hi Iver,

seehr interessantes Projekt und da ist ja wirklich Luft nach oben drin.
Ich werde das mal im Auge behalten.

Und herzliches Willkommen bei uns im Forum und Team ;)

Gruß Jörg

[Dominik S.]

Wo du gerade schon so schön Werbung machst für das Projekt.

Hier im Wiki (http://wiki.seti-germany.de/index.php/TSP) könnte das Projekt noch ein bisschen mehr Beschreibung gebrauchen. Also wer immer bei dem Projekt angemeldet ist und sich berufen fühlt uns anderen ein paar mehr Informationen über das Projekt zu geben, immer rein damit!

[aendgraend]

Bin dabei, wenn auch mit wenig Ressourcen ;)
(Ich muss ja die Grössen und Laufzeiten-Seite mal wieder aktualisieren)


EDIT: Ich werde den Thread mal in Projekte-Forum verschieben, nach "sonstige Projekte", aber hier einen Verweis lassen für 3 Tage

[seeferkel]

Könnten wir uns doch nach yoyo vornehmen.

[yoyo[RKN]]

Wie ich Markus verstanden habe ist das Projekt aber noch ganz schön Alpha. Da werden u.a. Abstürze produziert und Applikationen dann wieder zurückgezogen usw.
yoyo

[Iver]

Alpha ist nicht ganz richtig, der Betreiber bastelt aber zugegebenermaßen an einem Genetic Algorithm für den Windowsbetrieb, unter Linux läuft der nämlich schon rund. Nur unter Windows zuckelt da noch irgendwas.

Nun ist es nicht so, daß ich jetzt jede Menge kaputter WUs auf der Platte habe, denn die Windows-Clients kriegen bisher nur die Brute Force-WUs (Laufzeit prognostiziert bei 3,0 GHz Kentfield QX6700: 48 Minuten je CPU, Athlon XP 3200: 56 Minuten, wird aber eher knapp 1:10 hr). In der Zeit zwischen den Tagen gabs ein-zwei GA-WUs, die völlig hinter ihrer Zeit hinterherliefen (also gerne mal 10 Stunden lang als verbleibende Zeit 15 Stunden anzeigte), bis sie auf einmal fertig waren. JA, die waren verbugt. Shit happens. Mit hunderten von BF-WUs hatte ich bisher keine Probleme und IMO auch keine Nicht-Punkte.:thumbup:

[Iver]

@Marauder: Ich bin übrigens schon länger dabei, die "Links, die man mal gesehen haben sollte"-Threads hatte ich damals ins Leben gerufen :)
@Dominik: Ich bin wohl zu blöd zum Wiki-Schreiben.... Wenn Du mir einen Tip geben kannst, wie ich ein Textfeld dort mit Krams füttern kann, dann mach ich das gerne, aber mit HTML o. Wiki-CMS hab ichs nicht so. *sry*

[Dominik S.]

Was meinst du mit Textfeld?

Wenn du die Tabelle meinst, dann sieh auf der Seite der Vorlage (http://wiki.seti-germany.de/index.php/Vorlage:ProjektTabelle) nach, da steht beschrieben wie du die Vorlage abänderst.
Für allgemeine Bearbeitungshilfe: Siehe hier. (http://de.wikipedia.org/wiki/Hilfe:Bearbeitungshilfe)

[Zwitschi]

Iver, ich denke da ist großes Zögern fehl am Platz ;)

Schreib doch einfach mal rein in so ein Textfeld, beobachte den Artikel und du wirst sehen, dass selbst nicht schön formatierte und mit Fehlern gespickte Artikel schon bald von anderen überarbeitet werden. Hauptsache ist, dass interessante Informationen nicht allein in den Köpfen einzelner abgespeichert sind, sondern allen verfügbar werden.

[McCarron]

einfach ausprobieren das mit der Wiki :)



und wenn's gar net will, einfach mal im Chat vorbeischaun, da kann dir garantiet wer helfen :)