-
Notifications
You must be signed in to change notification settings - Fork 1
/
out.txt
172 lines (172 loc) · 14.4 KB
/
out.txt
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
*** Step 1: ***
*** Step 2: ***
triangulating ...
build graph
#edges: 64 #nodes: 25
computing MST
took 0.000999927520752
computing delaunay of odd_deg_nodes
#edges: 33 #nodes: 14 14
computing minimum matching
took 0.0119998455048
#edges: 7 #nodes: 14
find euler tour
took 0.00100016593933
euler path: [(0, 7), (7, 16), (16, 4), (4, 9), (9, 6), (6, 21), (21, 3), (3, 18), (18, 12), (12, 24), (24, 20), (20, 17), (17, 14), (14, 20), (20, 13), (13, 23), (23, 5), (5, 1), (1, 19), (19, 11), (11, 22), (22, 12), (12, 10), (10, 8), (8, 2), (2, 15), (15, 0)]
#edges: 27 #nodes: 25
start shortcutting
-- start shortcutting visit 1
20 visited! 14
its a crossing
connected_visited_neighbors: None None
#its a real crossing!
12 visited! 22
its a crossing
connected_visited_neighbors: None None
#its a real crossing!
[(14, 20), (22, 12)]
#edges: 27 #crossings: 2
unfuddle (14, 20)
20 14 17 [24, 1, 5, 14, 17] [24]
unfuddle (22, 12)
12 22 11 [24, 8, 10, 18, 22] [24, 18]
EE - no cross resolving
-- start shortcutting visit 2
[]
#edges: 25 #crossings: 0
-- start shortcutting visit 3
[]
#edges: 25 #crossings: 0
-- start shortcutting visit 4
[]
#edges: 25 #crossings: 0
-- start shortcutting visit 5
[]
#edges: 25 #crossings: 0
took 0.000999927520752
#edges: 25 path len: 78884.86197
*** Step 3: ***
Best Solution:
Distance: 197597.846693
('Tour: ', [(14, 8), (8, 19), (19, 2), (2, 16), (16, 11), (11, 7), (7, 0), (0, 17), (17, 18), (18, 10), (10, 5), (5, 1), (1, 23), (23, 6), (6, 4), (4, 12), (12, 15), (15, 13), (13, 9), (9, 21), (21, 22), (22, 20), (20, 3), (3, 24), (24, 14)])
('Route: ', [(0, 7), (7, 16), (16, 4), (4, 9), (9, 6), (6, 21), (21, 3), (3, 18), (18, 22), (22, 11), (11, 19), (19, 1), (1, 5), (5, 23), (23, 13), (13, 20), (20, 17), (17, 14), (14, 24), (24, 12), (12, 10), (10, 8), (8, 2), (2, 15), (15, 0)])
*** Step 4: ***
# Duplicates: #
duplicate (0) (0, 7) and (6) (7, 0)
duplicate (12) (1, 5) and (11) (5, 1)
duplicate (18) (14, 24) and (24) (24, 14)
dupicates: 3
Path0: 78884.86197
Path1: 197597.846693
*** Step 4.1: ***
solving duplicate (0) (0, 7) and (6) (7, 0)
manipulate route0 on 0
solving duplicate (11) (1, 5) and (11) (5, 1)
manipulate route0 on 11
solving duplicate (16) (14, 24) and (24) (24, 14)
manipulate route0 on 16
solving duplicate (22) (0, 7) and (6) (7, 0)
manipulate route0 on 22
Path0: 119080.752784
Path0: [(7, 16), (16, 4), (4, 9), (9, 6), (6, 21), (21, 3), (3, 18), (18, 22), (22, 11), (11, 19), (19, 5), (5, 23), (23, 13), (13, 20), (20, 17), (17, 24), (24, 12), (12, 10), (10, 8), (8, 2), (2, 15), (15, 7), (7, 1), (1, 7), (7, 3)]
Path1: 197597.846693
Path1: [(14, 8), (8, 19), (19, 2), (2, 16), (16, 11), (11, 7), (7, 0), (0, 17), (17, 18), (18, 10), (10, 5), (5, 1), (1, 23), (23, 6), (6, 4), (4, 12), (12, 15), (15, 13), (13, 9), (9, 21), (21, 22), (22, 20), (20, 3), (3, 24), (24, 14)]
*** Step 5: ***
Results:
Path0: 119080.752784 / 78884.86197
Path1: 197597.846693 / 197597.846693
------------------------
0
[0.0, 10950.041095813294, 2874.325312138485, 9716.70612913656, 14833.601214809572, 8555.265337790523, 13667.174287320697, 5625.344878316351, 4852.651749301613, 15230.659375089444, 5582.49988804299, 12189.080030912915, 8560.209168005184, 10226.090406406545, 6677.8177573216235, 2065.012590760647, 6918.3469846488615, 5991.375217760944, 8658.0276044836, 13756.462117855739, 6960.749169450081, 11150.823646708794, 11110.88349322411, 9272.928393986444, 6949.969927992494]
2065.01259076
***
1
[10950.041095813294, 0.0, 8364.40517909074, 11244.065545877967, 14234.513865952711, 3557.204660966248, 15657.336203837483, 15769.354235351555, 6738.1766821596475, 15122.416109868158, 5909.843060521996, 6479.753081715383, 6010.114225204044, 4399.320970331672, 4320.680733403014, 9203.888797676773, 13406.537845394687, 5903.803265692379, 6189.066003849046, 5819.402890331619, 4042.9762551862705, 12949.697293759418, 4756.891842369343, 4401.657528704386, 4000.2432426041296]
3557.20466097
***
2
[2874.325312138485, 8364.40517909074, 0.0, 10036.119170276925, 14980.274396685796, 5711.062335502914, 14470.876442012765, 8429.532905208924, 3480.2846147980486, 15534.837398569707, 3880.235173285248, 10769.98839367991, 7324.972969233402, 7352.750029750773, 4044.6596890220567, 2271.5107307692824, 8610.040476095335, 3117.201469266945, 7478.045199114538, 11955.38188432306, 4321.437839423355, 11713.738002875085, 9401.221729115849, 6399.126893569153, 4422.535019646538]
2271.51073077
***
3
[9716.70612913656, 11244.065545877967, 10036.119170276925, 0.0, 5118.49518901796, 11926.542709435958, 4683.0738836793935, 10020.304436492936, 6992.760899673319, 5544.122743951472, 7221.852186246961, 6767.892581889875, 5235.4049509087645, 14016.100777320346, 9719.773659916162, 8146.032469859177, 4960.12348636604, 11274.007140320606, 5055.083777742956, 9156.465912130072, 9819.097158089435, 1815.0068870392752, 7362.364429991224, 13302.61677265041, 9351.860135823246]
1815.00688704
***
4
[14833.601214809572, 14234.513865952711, 14980.274396685796, 5118.49518901796, 0.0, 15869.309373756629, 3460.696172737503, 14637.301663899669, 11709.462156734613, 959.8020629275601, 11739.583041999405, 8091.253116792232, 8815.57179087097, 17818.626209671722, 13952.200722466689, 13212.665211833682, 9451.13379441853, 15784.22224881543, 8604.00703161033, 10068.06461044028, 13982.517441433785, 3980.845764407358, 9558.36999702355, 17257.948197859445, 13489.92353573585]
959.802062928
***
5
[8555.265337790523, 3557.204660966248, 5711.062335502914, 11926.542709435958, 15869.309373756629, 0.0, 16591.98463114042, 13923.403750520201, 5620.297856875559, 16663.65074045901, 4999.864998177451, 9003.55091061299, 7058.523499996299, 2124.4528707410764, 2395.3398506266285, 7239.967541363704, 12721.398429418048, 2716.8282978502707, 7269.8927777512645, 9002.780959236985, 2203.36696898179, 13737.361500666713, 7218.187376343177, 1392.3462213113519, 2614.030030431938]
1392.34622131
***
6
[13667.174287320697, 15657.336203837483, 14470.876442012765, 4683.0738836793935, 3460.696172737503, 16591.98463114042, 0.0, 12279.576621366065, 11623.424366338862, 2920.6043895057064, 11895.79169286349, 10230.817806998617, 9733.171528335459, 18668.574503694705, 14402.449409735831, 12407.067018437516, 7296.377457341417, 15931.034178608745, 9535.212897465897, 12484.635877749899, 14499.240807711278, 2869.355502547567, 11335.833140973804, 17973.012268398415, 14029.38576702487]
2869.35550255
***
7
[5625.344878316351, 15769.354235351555, 8429.532905208924, 10020.304436492936, 14637.301663899669, 13923.403750520201, 12279.576621366065, 0.0, 9052.499765258213, 14681.518313852965, 9888.372666925534, 15076.429451299136, 11669.754153365871, 15738.55114043221, 11780.716659015274, 6701.074093009269, 5189.0471186914465, 11515.444238065676, 11670.886041770778, 17137.364587357064, 12053.358453144916, 10663.03151078529, 14564.555091042088, 14783.758656038728, 11907.788753584773]
5189.04711869
***
8
[4852.651749301613, 6738.1766821596475, 3480.2846147980486, 6992.760899673319, 11709.462156734613, 5620.297856875559, 11623.424366338862, 9052.499765258213, 0.0, 12335.522202160717, 836.0633947255435, 7440.8752845347435, 3887.3736635420064, 7721.365682312941, 3225.3001410721454, 2811.1068994259185, 7105.320963897409, 4323.466202018931, 4026.465571689394, 8905.69194391991, 3436.1981898604163, 8772.046796500803, 6264.58338598825, 6856.177944015164, 3119.339192841971]
836.063394726
***
9
[15230.659375089444, 15122.416109868158, 15534.837398569707, 5544.122743951472, 959.8020629275601, 16663.65074045901, 2920.6043895057064, 14681.518313852965, 12335.522202160717, 0.0, 12414.49966772725, 9032.221266111676, 9605.325293814885, 18637.58020774156, 14693.832209468026, 13689.4915172186, 9526.485710900952, 16477.461090835564, 9394.070949274335, 11026.230770304057, 14735.931663793775, 4152.702373154137, 10471.767806822303, 18054.809553135696, 14245.166373194805]
959.802062928
***
10
[5582.49988804299, 5909.843060521996, 3880.235173285248, 7221.852186246961, 11739.583041999405, 4999.864998177451, 11895.79169286349, 9888.372666925534, 836.0633947255435, 12414.49966772725, 0.0, 6895.681329643939, 3475.294519893242, 7120.820879645829, 2624.3058129722613, 3577.7853485082082, 7795.822984137082, 4072.725131898788, 3642.807296577737, 8221.496518274516, 2796.5099677991493, 9028.137626332466, 5604.289517860404, 6293.616607325235, 2419.7869740950337]
836.063394726
***
11
[12189.080030912915, 6479.753081715383, 10769.98839367991, 6767.892581889875, 8091.253116792232, 9003.55091061299, 10230.817806998617, 15076.429451299136, 7440.8752845347435, 9032.221266111676, 6895.681329643939, 0.0, 3634.534495640398, 10600.509846229095, 7869.8001245266705, 10126.829365601061, 10897.574454895916, 10010.851562179912, 3556.87418950966, 2388.6150799155566, 7759.357254309148, 7999.726245316148, 1794.1293152947476, 10282.344333856943, 7314.7627439309335]
1794.12931529
***
12
[8560.209168005184, 6010.114225204044, 7324.972969233402, 5235.4049509087645, 8815.57179087097, 7058.523499996299, 9733.171528335459, 11669.754153365871, 3887.3736635420064, 9605.325293814885, 3475.294519893242, 3634.534495640398, 0.0, 9048.407263159634, 5202.759364029822, 6501.299870025993, 8031.841631904852, 7188.83481518389, 211.56795598577776, 5475.209676350304, 5202.163011671203, 6964.282087911144, 2907.205015130512, 8449.491937388899, 4708.64789509685]
211.567955986
***
13
[10226.090406406545, 4399.320970331672, 7352.750029750773, 14016.100777320346, 17818.626209671722, 2124.4528707410764, 18668.574503694705, 15738.55114043221, 7721.365682312941, 18637.58020774156, 7120.820879645829, 10600.509846229095, 9048.407263159634, 0.0, 4505.125192489106, 9130.803360055455, 14808.341500654285, 4236.297439982231, 9258.034402614845, 10209.413548289636, 4325.097224340743, 15822.65657214363, 8809.64863090464, 955.1586255695962, 4737.3846160091325]
955.15862557
***
14
[6677.8177573216235, 4320.680733403014, 4044.6596890220567, 9719.773659916162, 13952.200722466689, 2395.3398506266285, 14402.449409735831, 11780.716659015274, 3225.3001410721454, 14693.832209468026, 2624.3058129722613, 7869.8001245266705, 5202.759364029822, 4505.125192489106, 0.0, 5087.266947979042, 10328.631322687435, 2145.3141961027527, 5410.0025877997505, 8489.048238760339, 282.936388610585, 11534.638702620901, 6207.159898053215, 3669.419163845962, 556.2517415703073]
282.936388611
***
15
[2065.012590760647, 9203.888797676773, 2271.5107307692824, 8146.032469859177, 13212.665211833682, 7239.967541363704, 12407.067018437516, 6701.074093009269, 2811.1068994259185, 13689.4915172186, 3577.7853485082082, 10126.829365601061, 6501.299870025993, 9130.803360055455, 5087.266947979042, 0.0, 6338.569239189551, 4995.040940773159, 6603.68904476884, 11701.75700482624, 5362.987227282944, 9728.259094000323, 9053.220034882615, 8183.291880410963, 5252.002380045157]
2065.01259076
***
16
[6918.3469846488615, 13406.537845394687, 8610.040476095335, 4960.12348636604, 9451.13379441853, 12721.398429418048, 7296.377457341417, 5189.0471186914465, 7105.320963897409, 9526.485710900952, 7795.822984137082, 10897.574454895916, 8031.841631904852, 14808.341500654285, 10328.631322687435, 6338.569239189551, 0.0, 11038.219874599346, 7954.153191886613, 13181.216370274786, 10541.282085211456, 5474.346079670156, 10854.824227043016, 13919.488568191002, 10206.348073625551]
4960.12348637
***
17
[5991.375217760944, 5903.803265692379, 3117.201469266945, 11274.007140320606, 15784.22224881543, 2716.8282978502707, 15931.034178608745, 11515.444238065676, 4323.466202018931, 16477.461090835564, 4072.725131898788, 10010.851562179912, 7188.83481518389, 4236.297439982231, 2145.3141961027527, 4995.040940773159, 11038.219874599346, 0.0, 7388.6754563994755, 10595.928321765867, 2291.81194691013, 13070.258490175318, 8351.960787743199, 3282.1578267962677, 2701.553812160698]
2145.3141961
***
18
[8658.0276044836, 6189.066003849046, 7478.045199114538, 5055.083777742956, 8604.00703161033, 7269.8927777512645, 9535.212897465897, 11670.886041770778, 4026.465571689394, 9394.070949274335, 3642.807296577737, 3556.87418950966, 211.56795598577776, 9258.034402614845, 5410.0025877997505, 6603.68904476884, 7954.153191886613, 7388.6754563994755, 0.0, 5466.572234956747, 5411.380322985994, 6774.233683598463, 2937.3379104216115, 8660.78085394152, 4917.788934063763]
211.567955986
***
19
[13756.462117855739, 5819.402890331619, 11955.38188432306, 9156.465912130072, 10068.06461044028, 9002.780959236985, 12484.635877749899, 17137.364587357064, 8905.69194391991, 11026.230770304057, 8221.496518274516, 2388.6150799155566, 5475.209676350304, 10209.413548289636, 8489.048238760339, 11701.75700482624, 13181.216370274786, 10595.928321765867, 5466.572234956747, 0.0, 8309.415683428047, 10360.359935832344, 2652.968526010062, 10105.719222301796, 7947.0631053238785]
2388.61507992
***
20
[6960.749169450081, 4042.9762551862705, 4321.437839423355, 9819.097158089435, 13982.517441433785, 2203.36696898179, 14499.240807711278, 12053.358453144916, 3436.1981898604163, 14735.931663793775, 2796.5099677991493, 7759.357254309148, 5202.163011671203, 4325.097224340743, 282.936388610585, 5362.987227282944, 10541.282085211456, 2291.81194691013, 5411.380322985994, 8309.415683428047, 0.0, 11633.964457569913, 6073.02107686117, 3517.3413254900356, 493.7053777304841]
282.936388611
***
21
[11150.823646708794, 12949.697293759418, 11713.738002875085, 1815.0068870392752, 3980.845764407358, 13737.361500666713, 2869.355502547567, 10663.03151078529, 8772.046796500803, 4152.702373154137, 9028.137626332466, 7999.726245316148, 6964.282087911144, 15822.65657214363, 11534.638702620901, 9728.259094000323, 5474.346079670156, 13070.258490175318, 6774.233683598463, 10360.359935832344, 11633.964457569913, 0.0, 8848.602149492313, 15115.112735272602, 11166.176516605852]
1815.00688704
***
22
[11110.88349322411, 4756.891842369343, 9401.221729115849, 7362.364429991224, 9558.36999702355, 7218.187376343177, 11335.833140973804, 14564.555091042088, 6264.58338598825, 10471.767806822303, 5604.289517860404, 1794.1293152947476, 2907.205015130512, 8809.64863090464, 6207.159898053215, 9053.220034882615, 10854.824227043016, 8351.960787743199, 2937.3379104216115, 2652.968526010062, 6073.02107686117, 8848.602149492313, 0.0, 8489.277059915055, 5651.236501863995]
1794.12931529
***
23
[9272.928393986444, 4401.657528704386, 6399.126893569153, 13302.61677265041, 17257.948197859445, 1392.3462213113519, 17973.012268398415, 14783.758656038728, 6856.177944015164, 18054.809553135696, 6293.616607325235, 10282.344333856943, 8449.491937388899, 955.1586255695962, 3669.419163845962, 8183.291880410963, 13919.488568191002, 3282.1578267962677, 8660.78085394152, 10105.719222301796, 3517.3413254900356, 15115.112735272602, 8489.277059915055, 0.0, 3961.3332351621216]