-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmain.go
125 lines (111 loc) · 6.64 KB
/
main.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package main
import (
"fmt"
"time"
"github.com/Spi1y/tsp-solver/solver"
"github.com/Spi1y/tsp-solver/solver/matrix"
"github.com/Spi1y/tsp-solver/solver/tasks"
)
func main() {
case7 := matrix.ConvertToMatrix([][]int{
{-1, 5866, 13206, 12730, 4940, 10000, 15147, 5941},
{4780, -1, 8881, 7975, 7415, 5754, 17622, 1616},
{17410, 9343, -1, 5532, 15866, 5964, 26073, 8484},
{11103, 7404, 5499, -1, 12388, 3274, 22595, 6545},
{7277, 5321, 15015, 12346, -1, 11026, 11761, 5987},
{10801, 6413, 6486, 4504, 11398, -1, 21605, 5554},
{17465, 15509, 25203, 22534, 11735, 21214, -1, 16175},
{5550, 2203, 8658, 9262, 8185, 6532, 18392, -1},
})
path7 := []int{0, 6, 4, 1, 2, 3, 5, 7}
distance7 := 60994
case8 := matrix.ConvertToMatrix([][]int{
{-1, 10000, 4940, 13206, 5941, 5866, 15147, 12730, 13714},
{10801, -1, 11398, 6486, 5554, 6413, 21605, 4504, 3796},
{7277, 11026, -1, 15015, 5987, 5321, 11761, 12346, 17326},
{17410, 5964, 15866, -1, 8484, 9343, 26073, 5532, 8971},
{5550, 6532, 8185, 8658, -1, 2203, 18392, 9262, 10864},
{4780, 5754, 7415, 8881, 1616, -1, 17622, 7975, 10086},
{17465, 21214, 11735, 25203, 16175, 15509, -1, 22534, 27514},
{11103, 3274, 12388, 5499, 6545, 7404, 22595, -1, 4304},
{13688, 4936, 17473, 8938, 9338, 10197, 27680, 4628, -1},
})
path8 := []int{0, 6, 2, 5, 1, 8, 7, 3, 4}
distance8 := 65914
case10 := matrix.ConvertToMatrix([][]int{
{-1, 10000, 4940, 13206, 5941, 5866, 15147, 12730, 13714, 10632, 19693},
{10801, -1, 11398, 6486, 5554, 6413, 21605, 4504, 3796, 3412, 14454},
{7277, 11026, -1, 15015, 5987, 5321, 11761, 12346, 17326, 14244, 18287},
{17410, 5964, 15866, -1, 8484, 9343, 26073, 5532, 8971, 9271, 8644},
{5550, 6532, 8185, 8658, -1, 2203, 18392, 9262, 10864, 10109, 16873},
{4780, 5754, 7415, 8881, 1616, -1, 17622, 7975, 10086, 12531, 17117},
{17465, 21214, 11735, 25203, 16175, 15509, -1, 22534, 27514, 24432, 28475},
{11103, 3274, 12388, 5499, 6545, 7404, 22595, -1, 4304, 7178, 13467},
{13688, 4936, 17473, 8938, 9338, 10197, 27680, 4628, -1, 3709, 16906},
{10606, 3863, 14391, 9197, 8266, 9125, 24598, 6593, 3709, -1, 17165},
{20295, 14035, 18751, 8316, 16298, 16135, 28958, 13603, 17042, 17342, -1},
})
path10 := []int{0, 6, 2, 10, 3, 7, 8, 9, 1, 4, 5}
distance10 := 83430
case12 := matrix.ConvertToMatrix([][]int{
{-1, 10000, 4940, 13206, 5941, 5866, 15147, 12730, 13714, 10632, 19693, 134984, 21742},
{10801, -1, 11398, 6486, 5554, 6413, 21605, 4504, 3796, 3412, 14454, 129139, 17131},
{7277, 11026, -1, 15015, 5987, 5321, 11761, 12346, 17326, 14244, 18287, 131597, 20336},
{17410, 5964, 15866, -1, 8484, 9343, 26073, 5532, 8971, 9271, 8644, 133609, 11943},
{5550, 6532, 8185, 8658, -1, 2203, 18392, 9262, 10864, 10109, 16873, 130330, 19817},
{4780, 5754, 7415, 8881, 1616, -1, 17622, 7975, 10086, 12531, 17117, 137459, 20061},
{17465, 21214, 11735, 25203, 16175, 15509, -1, 22534, 27514, 24432, 28475, 130047, 30524},
{11103, 3274, 12388, 5499, 6545, 7404, 22595, -1, 4304, 7178, 13467, 131433, 16255},
{13688, 4936, 17473, 8938, 9338, 10197, 27680, 4628, -1, 3709, 16906, 129524, 19693},
{10606, 3863, 14391, 9197, 8266, 9125, 24598, 6593, 3709, -1, 17165, 126442, 19842},
{20295, 14035, 18751, 8316, 16298, 16135, 28958, 13603, 17042, 17342, -1, 148795, 4189},
{128052, 128430, 132527, 133642, 130747, 136302, 129548, 131160, 129352, 126270, 140852, -1, 147051},
{23594, 21180, 22050, 11615, 20041, 20900, 43627, 16165, 19604, 24462, 4189, 163225, -1},
})
path12 := []int{0, 2, 6, 11, 9, 8, 7, 12, 10, 3, 1, 4, 5}
distance12 := 328616
// case17 := matrix.ConvertToMatrix([][]int{
// {-1, 10000, 4940, 13206, 5941, 5866, 15147, 12730, 13714, 10632, 19693, 134984, 21742, 9385, 7930, 10139, 5281, 10263},
// {10801, -1, 11398, 6486, 5554, 6413, 21605, 4504, 3796, 3412, 14454, 129139, 17131, 4354, 5709, 3073, 6419, 295},
// {7277, 11026, -1, 15015, 5987, 5321, 11761, 12346, 17326, 14244, 18287, 131597, 20336, 9431, 7976, 10185, 4928, 11289},
// {17410, 5964, 15866, -1, 8484, 9343, 26073, 5532, 8971, 9271, 8644, 133609, 11943, 4539, 7172, 4268, 9349, 6252},
// {5550, 6532, 8185, 8658, -1, 2203, 18392, 9262, 10864, 10109, 16873, 130330, 19817, 4837, 3382, 5591, 2209, 6795},
// {4780, 5754, 7415, 8881, 1616, -1, 17622, 7975, 10086, 12531, 17117, 137459, 20061, 5060, 3605, 5814, 1863, 6017},
// {17465, 21214, 11735, 25203, 16175, 15509, -1, 22534, 27514, 24432, 28475, 130047, 30524, 19619, 18164, 20373, 15116, 21477},
// {11103, 3274, 12388, 5499, 6545, 7404, 22595, -1, 4304, 7178, 13467, 131433, 16255, 3350, 5233, 2205, 7410, 4061},
// {13688, 4936, 17473, 8938, 9338, 10197, 27680, 4628, -1, 3709, 16906, 129524, 19693, 6789, 9493, 5644, 10203, 3722},
// {10606, 3863, 14391, 9197, 8266, 9125, 24598, 6593, 3709, -1, 17165, 126442, 19842, 7065, 8421, 5784, 9131, 3931},
// {20295, 14035, 18751, 8316, 16298, 16135, 28958, 13603, 17042, 17342, -1, 148795, 4189, 11949, 14388, 10869, 17163, 14323},
// {128052, 128430, 132527, 133642, 130747, 136302, 129548, 131160, 129352, 126270, 140852, -1, 147051, 129887, 129837, 130124, 135909, 128693},
// {23594, 21180, 22050, 11615, 20041, 20900, 43627, 16165, 19604, 24462, 4189, 163225, -1, 15192, 18131, 14111, 20906, 21443},
// {9417, 3384, 9850, 4141, 4007, 4866, 20057, 3104, 6544, 6666, 11351, 130445, 13876, -1, 2695, 912, 4872, 3647},
// {6794, 3627, 8222, 7121, 2379, 3238, 18429, 4928, 7959, 6909, 15689, 130005, 18633, 2700, -1, 2937, 3244, 3890},
// {9123, 2472, 10408, 4166, 4565, 5424, 20615, 2192, 5632, 5754, 11544, 129531, 14069, 912, 3253, -1, 5430, 2735},
// {5363, 6516, 4691, 8742, 1477, 812, 14898, 7836, 10848, 9798, 16978, 134735, 19922, 4921, 3466, 5675, -1, 6779},
// {10506, 857, 11103, 6191, 5259, 6118, 21310, 3587, 4069, 3020, 14159, 128844, 16836, 4059, 5414, 2778, 6124, -1},
// })
// path17 := []int{}
// distance17 := 0
fmt.Println("TSP solver demo")
fmt.Printf("========================\n")
showCase("7 points", case7, path7, distance7, 0)
showCase("8 points", case8, path8, distance8, 1)
showCase("10 points", case10, path10, distance10, 6)
showCase("12 points", case12, path12, distance12, 111)
// Can`t handle that much yet
// showCase("17 points", case17, path17, distance17, 0)
}
func showCase(name string, distanceMatrix matrix.Matrix, path1C []int, distance1C int, time1C int) {
fmt.Printf("%s\n", name)
fmt.Printf("1C: %v, %v, %vs \n", path1C, distance1C, time1C)
s := &solver.Solver{}
s.DistanceMatrix = distanceMatrix
start := time.Now()
path, distance, err := s.Solve(tasks.QueueLinkedList)
elapsed := time.Since(start)
if err != nil {
fmt.Printf("Go error: %v\n", err)
}
fmt.Printf("Go: %v, %v, %s\n", path, distance, elapsed)
fmt.Printf("========================\n")
}