Daten für einfache TSP

Schrieb ich einen einfachen genetischen Algorithmus, lösen können traveling salesman problem mit 5 Städten. Ich möchte sehen, wie es ist, ein problem mit mehr Städten, so etwas wie 10, 25, 50, 100, aber ich kann nicht finden, eine Probe-Datum für das problem, es zu versuchen. Im Grunde, ich bin auf der Suche nach 2D-Listen oder Matrizen mit Entfernungen zwischen den Städten. Es wäre schön, wenn es eine Lösung gibt. Wo sollte ich suchen?

Danke im Voraus

Wollen Sie Daten mit exakten Lösungen, oder einfach nur Daten? Man kann nur immer bauen Sie Ihren eigenen Daten-sets, wenn Sie möchten. Auch Sie sind auf der Suche für euklidische TSP-Instanzen oder beliebige TSP-Instanzen?
Wenn Lösungen enthalten sind, wäre es schön. Ich weiß nicht, was euklidischen und Beliebige TSP-Instanzen sind. Ich bin nur ab.
Sie können auch sets mit bekannten Lösungen, um begonnen zu erhalten - zum Beispiel, erstellen Sie die n Punkte auf einem Kreis. Die beste Lösung ist, Durchlaufen Sie in der Reihenfolge, und Sie können die ungefähren ideal-Pfad Länge durch die Länge des Kreises.
gute Idee. Danke.

InformationsquelleAutor Akavall | 2012-06-13

  1. 6

    Ich bin mir nicht sicher, aber wie es scheint, die Seite "Lesen oder Schreiben Traveling Salesman Problem (TSP) - Dateien " haben einige input-Daten-Dateien, zum Beispiel, diese eine.

    Auch, "TDL-Test-Daten" ist eine gute Quelle.

    Danke, ja, dein Erster link scheint was ich Suche. Ich sah "TDL-TEST-DATEN" Zeug, aber Sie scheinen enthalten zu viele Städte.

    InformationsquelleAutor gahcep

  2. 8

    Einer bekannten benchmark-Bibliothek für das TSP-Instanzen reichen von weniger als 14 auf fast 100.000 Städten ist die TSPLIB. Die Instanzen wurden gelöst, um Optimalität, für einige Instanzen die optimale Lösung ist ebenfalls verfügbar.

    Viele Instanzen haben einen realen hintergrund, wie z.B. Reise wurden Städte in Deutschland, der Schweiz, den USA oder in der ganzen Welt. Einige der Instanzen darstellen, bohren Probleme für computer-board-layout Es ist auch eine Instanz, die für die Reise des Odysseus.

    InformationsquelleAutor Andreas

  3. 6

    Den Quellen, die ich im Netz gefunden habe sind Recht groß. Könnte ich vielleicht etwas falsch, aber 10 Orte (Städte) nehmen ~0,6 s und 11 Orte in der ~7s. Der kleinste bekannte-Lösung dataset ich finden konnte, war die 15 Plätze (und als "kleine", das "klassische" einer wird 48 Plätze), aber vielleicht sind diejenigen, für optimierte (nicht-brute-force-algorithmen. Am Ende machte ich meine eigenen Tabelle mit der realen Welt der Städte:

               m
           a
           a                           h
           s       h   s               u
           t   a   e   i   g           l
           r   a   e   t   e           s
           i   c   r   t   l   e   b   b   a       e
           c   h   l   a   e   c   o   e   n   o   p
           h   e   e   r   e   h   n   r   n   h   e
           t   n   n   d   n   t   n   g   e   e   n
maastricht 0   29  20  21  16  31  100 12  4   31  18
    aachen 29  0   15  29  28  40  72  21  29  41  12
   heerlen 20  15  0   15  14  25  81  9   23  27  13
   sittard 21  29  15  0   4   12  92  12  25  13  25
    geleen 16  28  14  4   0   16  94  9   20  16  22
      echt 31  40  25  12  16  0   95  24  36  3   37
      bonn 100 72  81  92  94  95  0   90  101 99  84
  hulsberg 12  21  9   12  9   24  90  0   15  25  13
     kanne 4   29  23  25  20  36  101 15  0   35  18
       ohe 31  41  27  13  16  3   99  25  35  0   38
      epen 18  12  13  25  22  37  84  13  18  38  0

Optimal (by program): cities 0-7-4-3-9-5-2-6-1-10-8-0 = 253km
maastricht -> hulsberg -> geleen -> sittard -> ohe -> kanne -> echt
-> heerlen -> bonn -> aachen -> epen -> kanne -> maastricht

    Daten-format lesbar durch das Programm ist eine Teil-Tabelle (weil es symmetrisch):

    29 20 21 16 31 100 12 4 31 18
15 29 28 40 72 21 29 41 12
15 14 25 81 9 23 27 13
4 12 92 12 25 13 25
16 94 9 20 16 22
95 24 36 3 37
90 101 99 84
15 25 13
35 18
38

    Für mich braucht ~6,7 Sekunden verarbeiten 3rd gen i7 (i7-3630QM). Das Programm ist in C++ geschrieben, die single-threaded und einfach brute-Kräfte die Möglichkeiten. Für die Prüfung könnte es praktisch sein, zum entfernen von einem Ort, dann dauert es ~660ms (0,7 s), das ist immer noch genug um zu sehen, ob die code-änderungen machen einen großen Unterschied.

    Ich habe getestet, mein TSP solver und ich bekomme den gleichen Weg 😀 ich bin sehr glücklich darüber 🙂
    Danke 🙂 hat mir Geholfen und ich bekam die gleiche Antwort 🙂

    InformationsquelleAutor Luc

Schreibe einen Kommentar