[PaddyL]

Hi,
Ich wollte euch nur mein neustes Projekt vorstellen: World Travel Simulator. Dieses Programm stellt einen Brute-Force Simulator für das traveling salesman problem dar. Dies bedeutet im Grunde, die erzeugte Lösung ist nicht eine ungefähre Lösung, sondern DIE Lösung für den kürzesten Pfad. Optimierungen sind, soweit mir welche eingefallen sind, vorgenommen (beispielsweise werden Distanzen nur einmalig am Anfang errechnet).
Entstanden ist die Idee bei uns in einer Englisch-Vertretungsstunde, in der es eine Aufgabe gab bei der es darum ging eine Route zu entwerfen die einmalig durch alle 50 Staaten der USA ging. Hierbei war ich natürlich an der kürzesten Interessiert und zusammen mit meinem Nachbarn kam ich dann auch schnell auf die Anzahl der Möglichkeiten, die sich aus der Fakultät herleitet. Jedenfalls haben wir dann den Großteil der Stunde damit verbracht rum zurechnen wie lange ein Computer wohl für die Lösung des Problems brauchen könnte. Also habe ich mich mal rangemacht das Problem anzugehen. Das Ergebnis ist folgendes:
http://img116.imageshack.us/img116/3381/screeneh8.png

Der Code ist sicher noch nicht perfekt. Optimal wäre sicher eine Auslagerung in Threads zur Unterstützung von Dual (oder besser Quad ) Core CPUs, doch da ich momentan noch keine solche CPU besitze und das Programm sich auch so schon 98-100% der CPU schnappt reichte es mir auch so. Mein Athlon 64 (2 GB) schafft 10 Städte in einer akzeptablen Zeit von 4-5 Sekunden bei 50k-70k Lösungen pro Sekunde. Falls jemand Optimierungen hat oder sonstiges zu sagen hat würde ich mich freuen.
Freigegeben ist das Programm lizenslos (Forks oder Weiterentwickelungen steht so jede Lizenz frei - nett wäre die Erwähnung meines Namens, ist aber nicht nötig), da es nur rund 230 Zeilen hat und davon noch ein großer Teil Freizeilen und sonstiges Delphi Zeug sind.

-- Paddy

Lustige Sache

aber ich habe einen Fehler gefunden (siehe Anhang).
Einfach nach geglücktem Lauf 23 Städte hinzugefügt und gestartet ...

MfG,
Bug

Gute Idee und nette Umsetzung (zumindest grafisch).
Sind 150 Städte zuviel?

MfG
freak