Dane dla prostego TSP

Question

Napisałem prosty algorytm genetyczny, który może rozwiązać problem komiwojażera z 5 miastami. Chcę zobaczyć, jak to działa w przypadku problemu z większą liczbą miast, na przykład 10, 25, 50, 100, ale nie mogę znaleźć przykładowej daty problemu, aby ją wypróbować. Zasadniczo szukam list 2D lub macierzy z odległościami między miastami. Byłoby miło, gdyby istniało rozwiązanie. Gdzie powinienem wyglądać?

góry dziękuję

Answer 1

Nie jestem pewien, ale, jak się wydaje, na stronie „Read or Write Traveling Salesman Problem (TSP) Files” pewne pliki danych wejściowych, na przykład, this one.

Również "TSP Test Data" jest dobrym źródłem.

Answer 2

Dobrze znaną biblioteką benchmarków dla TSP z instancjami od zaledwie 14 do blisko 100 000 miast jest TSPLIB. Instancje zostały rozwiązane w sposób optymalny, w niektórych przypadkach dostępne jest również optymalne rozwiązanie.

Wiele przykładów ma rzeczywiste tło, np. Podróże były miastami w Niemczech, Szwajcarii, USA lub na całym świecie. Niektóre instancje reprezentują problemy z wierceniem układu płyty komputera Istnieje również instancja reprezentująca podróż Ulissesa.

Answer 3

Źródła, które znalazłem w Internecie, są dość duże. Mogę robić coś nie tak, ale 10 miejsc (miast) zajmuje ~ 0.6s, a 11 miejsc zajmuje ~ 7s. Najmniejszy znany zbiór danych, jaki udało mi się znaleźć, to 15 miejsc (i uważany za "mały", "klasyczny" to 48 miejsc), ale być może są to algorytmy zoptymalizowane (nie-brutalne). W końcu zrobiłem własną tabelę z rzeczywistych miast:

  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 

Format danych odczytywane przez program jest częściowy stół (bo jest symetryczna):

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 

Dla mnie to trwa ~ 6,7 sekund do przetworzenia na trzecim gen i7 (i7-3630QM). Program napisany jest w C++, jednowątkowy i po prostu brutalnie wymusza możliwości. W przypadku testowania może być bardziej praktyczne usunięcie jednego miejsca, to zajmie około 660ms (0,7 s), co jest wystarczające, aby sprawdzić, czy zmiany w kodzie odgrywają istotną rolę.