const
# descendants of TO_12345678
TO_123456789A = 59
TO_12345678A9 = 60
TO_1234569A78 = 61
TO_123456A978 = 62
TO_12349A5678 = 63
TO_1234A95678 = 64
TO_129A345678 = 65
TO_12A9345678 = 66
# descendants of TO_12345687
TO_123456879A = 67
TO_12345687A9 = 68
TO_1234569A87 = 69
TO_123456A987 = 70
TO_12349A5687 = 71
TO_1234A95687 = 72
TO_129A345687 = 73
TO_12A9345687 = 74
# descendants of TO_12347856
TO_123478569A = 75
TO_12347856A9 = 76
TO_1234789A56 = 77
TO_123478A956 = 78
TO_12349A7856 = 79
TO_1234A97856 = 80
TO_129A347856 = 81 # 5-opt
TO_12A9347856 = 82 # 5-opt
# descendants of TO_12348756
TO_123487569A = 83
TO_12348756A9 = 84
TO_1234879A56 = 85
TO_123487A956 = 86
TO_12349A8756 = 87
TO_1234A98756 = 88
TO_129A348756 = 89 # 5-opt
TO_12A9348756 = 90 # 5-opt
# descendants of TO_12783456
TO_127834569A = 91
TO_12783456A9 = 92
TO_1278349A56 = 93 # 5-opt
TO_127834A956 = 94 # 5-opt
TO_12789A3456 = 95
TO_1278A93456 = 96
TO_129A783456 = 97
TO_12A9783456 = 98
# descendants of TO_12873456
TO_128734569A = 99
TO_12873456A9 = 100
TO_1287349A56 = 101 # 5-opt
TO_128734A956 = 102 # 5-opt
TO_12879A3456 = 103
TO_1287A93456 = 104
TO_129A873456 = 105
TO_12A9873456 = 106
# descendants of TO_12346578
TO_123465789A = 107
TO_12346578A9 = 108
TO_1234659A78 = 109
TO_123465A978 = 110
TO_12349A6578 = 111
TO_1234A96578 = 112
TO_129A346578 = 113
TO_12A9346578 = 114
# descendants of TO_12346587
TO_123465879A = 115
TO_12346587A9 = 116
TO_1234659A87 = 117
TO_123465A987 = 118
TO_12349A6587 = 119
TO_1234A96587 = 120
TO_129A346587 = 121 # 5-opt
TO_12A9346587 = 122 # 5-opt
# descendants of TO_12347865
TO_123478659A = 123
TO_12347865A9 = 124
TO_1234789A65 = 125
TO_123478A965 = 126
TO_12349A7865 = 127
TO_1234A97865 = 128
TO_129A347865 = 129 # 5-opt
TO_12A9347865 = 130 # 5-opt
# descendants of TO_12348765
TO_123487659A = 131
TO_12348765A9 = 132
TO_1234879A65 = 133
TO_123487A965 = 134
TO_12349A8765 = 135
TO_1234A98765 = 136
TO_129A348765 = 137
TO_12A9348765 = 138
# descendants of TO_12783465
TO_127834659A = 139
TO_12783465A9 = 140 # 5-opt
TO_1278349A65 = 141 # 5-opt
TO_127834A965 = 142
TO_12789A3465 = 143
TO_1278A93465 = 144 # 5-opt
TO_129A783465 = 145
TO_12A9783465 = 146 # 5-opt
# descendants of TO_12873465
TO_128734659A = 147
TO_12873465A9 = 148 # 5-opt
TO_1287349A65 = 149 # 5-opt
TO_128734A965 = 150
TO_12879A3465 = 151 # 5-opt
TO_1287A93465 = 152
TO_129A873465 = 153 # 5-opt
TO_12A9873465 = 154
# descendants of TO_12563478
TO_125634789A = 155
TO_12563478A9 = 156
TO_1256349A78 = 157 # 5-opt
TO_125634A978 = 158 # 5-opt
TO_12569A3478 = 159 # 5-opt
TO_1256A93478 = 160 # 5-opt
TO_129A563478 = 161 # 5-opt
TO_12A9563478 = 162 # 5-opt
# descendants of TO_12563487
TO_125634879A = 163
TO_12563487A9 = 164 # 5-opt
TO_1256349A87 = 165 # 5-opt
TO_125634A987 = 166
TO_12569A3487 = 167 # 5-opt
TO_1256A93487 = 168
TO_129A563487 = 169 # 5-opt
TO_12A9563487 = 170
# descendants of TO_12785634
TO_127856349A = 171
TO_12785634A9 = 172
TO_1278569A34 = 173 # 5-opt
TO_127856A934 = 174 # 5-opt
TO_12789A5634 = 175
TO_1278A95634 = 176
TO_129A785634 = 177 # 5-opt
TO_12A9785634 = 178 # 5-opt
# descendants of TO_12875634
TO_128756349A = 179
TO_12875634A9 = 180 # 5-opt
TO_1287569A34 = 181 # 5-opt
TO_128756A934 = 182
TO_12879A5634 = 183
TO_1287A95634 = 184 # 5-opt
TO_129A875634 = 185 # 5-opt
TO_12A9875634 = 186
# descendants of TO_12567834
TO_125678349A = 187
TO_12567834A9 = 188
TO_1256789A34 = 189
TO_125678A934 = 190
TO_12569A7834 = 191 # 5-opt
TO_1256A97834 = 192 # 5-opt
TO_129A567834 = 193
TO_12A9567834 = 194
# descendants of TO_12568734
TO_125687349A = 195
TO_12568734A9 = 196 # 5-opt
TO_1256879A34 = 197
TO_125687A934 = 198 # 5-opt
TO_12569A8734 = 199 # 5-opt
TO_1256A98734 = 200
TO_129A568734 = 201
TO_12A9568734 = 202 # 5-opt
# descendants of TO_12653478
TO_126534789A = 203
TO_12653478A9 = 204
TO_1265349A78 = 205 # 5-opt
TO_126534A978 = 206 # 5-opt
TO_12659A3478 = 207 # 5-opt
TO_1265A93478 = 208 # 5-opt
TO_129A653478 = 209 # 5-opt
TO_12A9653478 = 210 # 5-opt
# descendants of TO_12653487
TO_126534879A = 211
TO_12653487A9 = 212 # 5-opt
TO_1265349A87 = 213 # 5-opt
TO_126534A987 = 214
TO_12659A3487 = 215
TO_1265A93487 = 216 # 5-opt
TO_129A653487 = 217
TO_12A9653487 = 218 # 5-opt
# descendants of TO_12657834
TO_126578349A = 219
TO_12657834A9 = 220 # 5-opt
TO_1265789A34 = 221
TO_126578A934 = 222 # 5-opt
TO_12659A7834 = 223 # 5-opt
TO_1265A97834 = 224
TO_129A657834 = 225
TO_12A9657834 = 226 # 5-opt
# descendants of TO_12658734
TO_126587349A = 227
TO_12658734A9 = 228
TO_1265879A34 = 229 # 5-opt
TO_126587A934 = 230 # 5-opt
TO_12659A8734 = 231
TO_1265A98734 = 232
TO_129A658734 = 233 # 5-opt
TO_12A9658734 = 234 # 5-opt
# descendants of TO_12786534
TO_127865349A = 235
TO_12786534A9 = 236 # 5-opt
TO_1278659A34 = 237 # 5-opt
TO_127865A934 = 238
TO_12789A6534 = 239
TO_1278A96534 = 240 # 5-opt
TO_129A786534 = 241 # 5-opt
TO_12A9786534 = 242
# descendants of TO_12876534
TO_128765349A = 243
TO_12876534A9 = 244
TO_1287659A34 = 245
TO_128765A934 = 246
TO_12879A6534 = 247 # 5-opt
TO_1287A96534 = 248 # 5-opt
TO_129A876534 = 249
TO_12A9876534 = 250
# descendants of TO_12435678
TO_124356789A = 251
TO_12435678A9 = 252
TO_1243569A78 = 253
TO_124356A978 = 254
TO_12439A5678 = 255
TO_1243A95678 = 256
TO_129A435678 = 257
TO_12A9435678 = 258
# descendants of TO_12435687
TO_124356879A = 259
TO_12435687A9 = 260
TO_1243569A87 = 261
TO_124356A987 = 262
TO_12439A5687 = 263 # 5-opt
TO_1243A95687 = 264 # 5-opt
TO_129A435687 = 265 # 5-opt
TO_12A9435687 = 266 # 5-opt
# descendants of TO_12437856
TO_124378569A = 267
TO_12437856A9 = 268 # 5-opt
TO_1243789A56 = 269
TO_124378A956 = 270 # 5-opt
TO_12439A7856 = 271
TO_1243A97856 = 272 # 5-opt
TO_129A437856 = 273 # 5-opt
TO_12A9437856 = 274
# descendants of TO_12438756
TO_124387569A = 275
TO_12438756A9 = 276 # 5-opt
TO_1243879A56 = 277 # 5-opt
TO_124387A956 = 278
TO_12439A8756 = 279 # 5-opt
TO_1243A98756 = 280
TO_129A438756 = 281
TO_12A9438756 = 282 # 5-opt
# descendants of TO_12784356
TO_127843569A = 283
TO_12784356A9 = 284 # 5-opt
TO_1278439A56 = 285 # 5-opt
TO_127843A956 = 286
TO_12789A4356 = 287
TO_1278A94356 = 288 # 5-opt
TO_129A784356 = 289
TO_12A9784356 = 290 # 5-opt
# descendants of TO_12874356
TO_128743569A = 291
TO_12874356A9 = 292 # 5-opt
TO_1287439A56 = 293
TO_128743A956 = 294 # 5-opt
TO_12879A4356 = 295 # 5-opt
TO_1287A94356 = 296
TO_129A874356 = 297 # 5-opt
TO_12A9874356 = 298
# descendants of TO_12436578
TO_124365789A = 299
TO_12436578A9 = 300
TO_1243659A78 = 301 # 5-opt
TO_124365A978 = 302 # 5-opt
TO_12439A6578 = 303 # 5-opt
TO_1243A96578 = 304 # 5-opt
TO_129A436578 = 305 # 5-opt
TO_12A9436578 = 306 # 5-opt
# descendants of TO_12436587
TO_124365879A = 307
TO_12436587A9 = 308 # 5-opt
TO_1243659A87 = 309 # 5-opt
TO_124365A987 = 310
TO_12439A6587 = 311
TO_1243A96587 = 312 # 5-opt
TO_129A436587 = 313 # 5-opt
TO_12A9436587 = 314
# descendants of TO_12437865
TO_124378659A = 315
TO_12437865A9 = 316 # 5-opt
TO_1243789A65 = 317
TO_124378A965 = 318 # 5-opt
TO_12439A7865 = 319 # 5-opt
TO_1243A97865 = 320
TO_129A437865 = 321
TO_12A9437865 = 322 # 5-opt
# descendants of TO_12438765
TO_124387659A = 323
TO_12438765A9 = 324
TO_1243879A65 = 325 # 5-opt
TO_124387A965 = 326 # 5-opt
TO_12439A8765 = 327
TO_1243A98765 = 328
TO_129A438765 = 329
TO_12A9438765 = 330
# descendants of TO_12784365
TO_127843659A = 331
TO_12784365A9 = 332
TO_1278439A65 = 333 # 5-opt
TO_127843A965 = 334 # 5-opt
TO_12789A4365 = 335
TO_1278A94365 = 336
TO_129A784365 = 337 # 5-opt
TO_12A9784365 = 338 # 5-opt
# descendants of TO_12874365
TO_128743659A = 339
TO_12874365A9 = 340 # 5-opt
TO_1287439A65 = 341
TO_128743A965 = 342 # 5-opt
TO_12879A4365 = 343
TO_1287A94365 = 344 # 5-opt
TO_129A874365 = 345 # 5-opt
TO_12A9874365 = 346
# descendants of TO_12564378
TO_125643789A = 347
TO_12564378A9 = 348
TO_1256439A78 = 349 # 5-opt
TO_125643A978 = 350 # 5-opt
TO_12569A4378 = 351 # 5-opt
TO_1256A94378 = 352 # 5-opt
TO_129A564378 = 353 # 5-opt
TO_12A9564378 = 354 # 5-opt
# descendants of TO_12564387
TO_125643879A = 355
TO_12564387A9 = 356 # 5-opt
TO_1256439A87 = 357 # 5-opt
TO_125643A987 = 358
TO_12569A4387 = 359 # 5-opt
TO_1256A94387 = 360
TO_129A564387 = 361
TO_12A9564387 = 362 # 5-opt
# descendants of TO_12567843
TO_125678439A = 363
TO_12567843A9 = 364
TO_1256789A43 = 365
TO_125678A943 = 366
TO_12569A7843 = 367 # 5-opt
TO_1256A97843 = 368 # 5-opt
TO_129A567843 = 369
TO_12A9567843 = 370
# descendants of TO_12568743
TO_125687439A = 371
TO_12568743A9 = 372 # 5-opt
TO_1256879A43 = 373
TO_125687A943 = 374 # 5-opt
TO_12569A8743 = 375 # 5-opt
TO_1256A98743 = 376
TO_129A568743 = 377 # 5-opt
TO_12A9568743 = 378
# descendants of TO_12785643
TO_127856439A = 379
TO_12785643A9 = 380 # 5-opt
TO_1278569A43 = 381 # 5-opt
TO_127856A943 = 382
TO_12789A5643 = 383
TO_1278A95643 = 384 # 5-opt
TO_129A785643 = 385 # 5-opt
TO_12A9785643 = 386
# descendants of TO_12875643
TO_128756439A = 387
TO_12875643A9 = 388
TO_1287569A43 = 389 # 5-opt
TO_128756A943 = 390 # 5-opt
TO_12879A5643 = 391 # 5-opt
TO_1287A95643 = 392 # 5-opt
TO_129A875643 = 393
TO_12A9875643 = 394
# descendants of TO_12654378
TO_126543789A = 395
TO_12654378A9 = 396
TO_1265439A78 = 397
TO_126543A978 = 398
TO_12659A4378 = 399
TO_1265A94378 = 400
TO_129A654378 = 401
TO_12A9654378 = 402
# descendants of TO_12654387
TO_126543879A = 403
TO_12654387A9 = 404
TO_1265439A87 = 405
TO_126543A987 = 406
TO_12659A4387 = 407 # 5-opt
TO_1265A94387 = 408 # 5-opt
TO_129A654387 = 409
TO_12A9654387 = 410
# descendants of TO_12657843
TO_126578439A = 411
TO_12657843A9 = 412 # 5-opt
TO_1265789A43 = 413
TO_126578A943 = 414 # 5-opt
TO_12659A7843 = 415
TO_1265A97843 = 416 # 5-opt
TO_129A657843 = 417 # 5-opt
TO_12A9657843 = 418
# descendants of TO_12658743
TO_126587439A = 419
TO_12658743A9 = 420 # 5-opt
TO_1265879A43 = 421 # 5-opt
TO_126587A943 = 422
TO_12659A8743 = 423 # 5-opt
TO_1265A98743 = 424
TO_129A658743 = 425 # 5-opt
TO_12A9658743 = 426
# descendants of TO_12786543
TO_127865439A = 427
TO_12786543A9 = 428
TO_1278659A43 = 429 # 5-opt
TO_127865A943 = 430 # 5-opt
TO_12789A6543 = 431
TO_1278A96543 = 432
TO_129A786543 = 433
TO_12A9786543 = 434
# descendants of TO_12876543
TO_128765439A = 435
TO_12876543A9 = 436
TO_1287659A43 = 437
TO_128765A943 = 438
TO_12879A6543 = 439
TO_1287A96543 = 440
TO_129A876543 = 441
TO_12A9876543 = 442
Friday, July 21, 2017
Extending LK: 5-opt move, part 3/3
Extending LK: 5-opt move, part 2/3
proc Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10: City_Number;
tourOrder: int) =
case tourOrder # all 148 cases of sequential 5-opt move
of TO_129A347856, TO_12569A3478, TO_129A785634, TO_12569A7834:
ExchangeLinks(c1, c2, c9, c10)
ExchangeLinks(c1, c9, c7, c8)
ExchangeLinks(c1, c7, c5, c6)
ExchangeLinks(c1, c5, c3, c4)
ExchangeLinks(c1, c3, c10, c2)
of TO_12A9347856, TO_129A563487, TO_12A9784356, TO_129A874356:
ExchangeLinks(c8, c7, c9, c10)
ExchangeLinks(c1, c2, c10, c7)
ExchangeLinks(c2, c7, c5, c6)
ExchangeLinks(c2, c5, c3, c4)
of TO_129A348756, TO_129A346587, TO_129A873465, TO_129A875634,
TO_1243A97856, TO_12439A8756, TO_1256439A87:
ExchangeLinks(c8, c7, c9, c10)
ExchangeLinks(c1, c2, c10, c7)
ExchangeLinks(c2, c7, c3, c4)
ExchangeLinks(c4, c7, c5, c6)
of TO_12A9348756, TO_12A9346587, TO_1278A93465, TO_12A9783465,
TO_12A9657834, TO_1243A96578:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c4, c9, c7, c8)
ExchangeLinks(c4, c7, c5, c6)
of TO_1278349A56:
ExchangeLinks(c1, c2, c9, c10)
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c1, c9, c7, c8)
ExchangeLinks(c1, c7, c3, c6)
ExchangeLinks(c1, c3, c10, c2)
of TO_127834A956, TO_12A9784365:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c4, c9, c5, c8)
of TO_1287349A56:
ExchangeLinks(c7, c8, c10, c9)
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c1, c2, c10, c7)
ExchangeLinks(c2, c7, c3, c6)
of TO_128734A956, TO_12657834A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c2, c7, c3, c6)
of TO_129A347865:
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c8, c7, c9, c10)
ExchangeLinks(c1, c2, c10, c7)
ExchangeLinks(c2, c7, c3, c6)
of TO_12A9347865, TO_12A9785634, TO_125643A978, TO_12568743A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c4, c9, c5, c6)
ExchangeLinks(c6, c9, c7, c8)
of TO_12783465A9, TO_12438756A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c2, c9, c5, c8)
ExchangeLinks(c2, c5, c3, c4)
of TO_1278349A65:
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c8, c5)
ExchangeLinks(c1, c8, c10, c9)
of TO_12873465A9, TO_127856A934, TO_12437856A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c3, c6, c8, c7)
ExchangeLinks(c2, c9, c3, c8)
of TO_1287349A65:
ExchangeLinks(c7, c8, c10, c9)
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c6, c5)
ExchangeLinks(c1, c6, c10, c7)
of TO_12879A3465, TO_12879A6534:
ExchangeLinks(c7, c8, c10, c9)
ExchangeLinks(c6, c5, c7, c10)
ExchangeLinks(c1, c2, c10, c5)
ExchangeLinks(c2, c5, c3, c4)
of TO_1256349A78:
ExchangeLinks(c1, c2, c9, c10)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c9, c5, c8)
ExchangeLinks(c1, c5, c3, c4)
ExchangeLinks(c1, c3, c10, c2)
of TO_125634A978, TO_1256A93478, TO_12875634A9, TO_12874356A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c3, c4, c8, c5)
ExchangeLinks(c2, c9, c3, c8)
of TO_129A563478:
ExchangeLinks(c1, c2, c9, c10)
ExchangeLinks(c2, c10, c3, c4)
ExchangeLinks(c1, c9, c7, c8)
ExchangeLinks(c1, c7, c5, c6)
ExchangeLinks(c1, c5, c10, c4)
of TO_12A9563478, TO_12A9653487, TO_12784356A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c4, c9, c5, c8)
of TO_12563487A9, TO_12569A3487, TO_12659A3478, TO_12659A7834,
TO_1243A95687, TO_1243659A78, TO_12657843A9:
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c4, c9, c5, c8)
of TO_1256349A87, TO_125687A943, TO_126578A943:
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c8, c5)
ExchangeLinks(c1, c8, c10, c9)
of TO_1278569A34:
ExchangeLinks(c1, c2, c9, c10)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c1, c9, c7, c8)
ExchangeLinks(c1, c7, c3, c6)
ExchangeLinks(c1, c3, c10, c2)
of TO_1287569A34:
ExchangeLinks(c7, c8, c10, c9)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c1, c2, c10, c7)
ExchangeLinks(c2, c7, c3, c6)
of TO_1287A95634, TO_12A9568734, TO_128743A956, TO_127843A965:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c4, c9, c5, c8)
of TO_1256A97834, TO_127865A943:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c2, c9, c3, c6)
ExchangeLinks(c6, c9, c7, c8)
of TO_12568734A9, TO_12658743A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c2, c7, c3, c6)
of TO_125687A934, TO_126578A934:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c4, c3, c5, c8)
ExchangeLinks(c2, c9, c3, c8)
of TO_12569A8734:
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c4, c3, c5, c8)
ExchangeLinks(c2, c9, c3, c8)
of TO_1265349A78, TO_12A9435687, TO_12A9436578:
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c5, c8)
ExchangeLinks(c2, c5, c3, c4)
of TO_126534A978, TO_1265879A34, TO_12786534A9, TO_1278659A34,
TO_12785643A9:
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c3, c6)
ExchangeLinks(c6, c9, c7, c8)
of TO_1265A93478, TO_1256A94378:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c2, c7, c3, c6)
of TO_129A653478:
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c4, c9, c5, c8)
of TO_12A9653478, TO_12653487A9, TO_126587A934, TO_12436587A9:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c2, c7, c5, c6)
ExchangeLinks(c2, c5, c3, c4)
of TO_1265349A87, TO_1278A96534, TO_1278569A43, TO_1278A95643:
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c1, c2, c6, c3)
ExchangeLinks(c1, c6, c8, c7)
ExchangeLinks(c1, c8, c10, c9)
of TO_1265A93487, TO_128756A943:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c4, c3, c5, c8)
ExchangeLinks(c2, c9, c3, c8)
of TO_129A658734:
ExchangeLinks(c8, c7, c9, c10)
ExchangeLinks(c1, c2, c10, c7)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c2, c7, c3, c6)
of TO_12A9658734, TO_12A9564378:
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c2, c7, c3, c6)
of TO_129A786534:
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c8, c5, c9, c10)
ExchangeLinks(c1, c2, c10, c5)
ExchangeLinks(c2, c5, c3, c4)
of TO_1287A96534, TO_124378A956, TO_1278A94356, TO_124387A965:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c2, c9, c5, c8)
ExchangeLinks(c2, c5, c3, c4)
of TO_12439A5687:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c8, c7, c9, c10)
ExchangeLinks(c1, c4, c10, c7)
ExchangeLinks(c4, c7, c5, c6)
of TO_129A435687, TO_129A437856, TO_12879A4356, TO_124365A978,
TO_12437865A9, TO_12874365A9, TO_129A564378, TO_129A568743,
TO_12879A5643, TO_12659A4387, TO_1265879A43, TO_1278659A43:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c4, c9, c5, c6)
ExchangeLinks(c6, c9, c7, c8)
of TO_1243879A56, TO_1278439A56:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c4, c9, c5, c8)
of TO_12A9438756:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c2, c9, c3, c6)
ExchangeLinks(c6, c9, c7, c8)
of TO_12439A6578, TO_12439A7865, TO_1243879A65, TO_1278439A65:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c6, c5)
ExchangeLinks(c1, c6, c10, c9)
ExchangeLinks(c6, c9, c7, c8)
of TO_129A436578, TO_12569A4378, TO_129A785643, TO_1287569A43:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c4, c9, c7, c8)
ExchangeLinks(c4, c7, c5, c6)
of TO_1243659A87, TO_129A436587, TO_124378A965, TO_129A874365,
TO_12569A4387, TO_12569A8743:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c6, c5)
ExchangeLinks(c1, c6, c8, c7)
ExchangeLinks(c1, c8, c10, c9)
of TO_1243A96587, TO_128743A965:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c3, c4, c6, c5)
ExchangeLinks(c3, c6, c8, c7)
ExchangeLinks(c2, c9, c3, c8)
of TO_12A9437865, TO_12564387A9, TO_1287A95643:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c2, c7, c3, c4)
ExchangeLinks(c4, c7, c5, c6)
of TO_129A784365, TO_12569A7843, TO_12659A8743:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c4, c9, c5, c8)
of TO_1287A94365:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c6, c5, c7, c8)
ExchangeLinks(c3, c4, c8, c5)
ExchangeLinks(c2, c9, c3, c8)
of TO_1256439A78:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c4, c9, c5, c8)
of TO_12A9564387:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c2, c9, c3, c4)
ExchangeLinks(c4, c9, c5, c8)
of TO_1256A97843, TO_129A658743:
ExchangeLinks(c8, c7, c9, c10)
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c6, c5)
ExchangeLinks(c1, c6, c10, c7)
of TO_1265A94387, TO_1265A97843:
ExchangeLinks(c1, c2, c10, c9)
ExchangeLinks(c4, c3, c5, c6)
ExchangeLinks(c2, c9, c7, c8)
ExchangeLinks(c2, c7, c3, c6)
of TO_129A657843:
ExchangeLinks(c1, c2, c4, c3)
ExchangeLinks(c1, c4, c10, c9)
ExchangeLinks(c5, c6, c8, c7)
ExchangeLinks(c4, c9, c5, c8)
else:
echo "Unknown 5-opt move: ", tourOrder
quit 1
Some simple statistics
| Problem # | Method | Time | Best | Avg | Worst |
|---|---|---|---|---|---|
| 1 | NN | 100 | 100.00 | 104.58 | 111.49 |
| 3opt-ND(24) | 4981 | 82.10 | 84.07 | 87.66 | |
| LK 5+2 | 4687 | 81.89 | 82.51 | 84.62 | |
| 2 | NN | 100 | 100.00 | 105.94 | 113.41 |
| 3opt-ND(24) | 5862 | 88.05 | 89.30 | 91.10 | |
| LK 5+2 | 5268 | 87.87 | 88.32 | 89.12 | |
| 3 | NN | 100 | 100.00 | 110.21 | 118.39 |
| 3opt-ND(24) | 5862 | 88.69 | 89.22 | 92.23 | |
| LK 5+2 | 3025 | 88.69 | 88.74 | 90.17 | |
| 4 | NN | 100 | 100.00 | 110.71 | 121.43 |
| 3opt-ND(24) | 4981 | 88.49 | 90.36 | 94.79 | |
| LK 5+2 | 5174 | 88.22 | 88.94 | 91.08 | |
| 5 | NN | 100 | 100.00 | 106.48 | 112.81 |
| 3opt-ND(24) | 6249 | 83.91 | 86.88 | 91.43 | |
| LK 5+2 | 11518 | 83.36 | 83.96 | 85.16 | |
| 6 | NN | 100 | 100.00 | 107.73 | 119.37 |
| 3opt-ND(24) | 6637 | 89.29 | 90.93 | 94.26 | |
| LK 5+2 | 3906 | 89.29 | 89.66 | 91.21 | |
| 7 | NN | 100 | 100.00 | 111.26 | 124.70 |
| 3opt-ND(24) | 5275 | 94.92 | 97.82 | 103.58 | |
| LK 5+2 | 3025 | 94.92 | 95.47 | 98.97 | |
| 9 | NN | 100 | 100.00 | 106.52 | 117.51 |
| 3opt-ND(24) | 5662 | 87.42 | 89.30 | 91.69 | |
| LK 5+2 | 6837 | 87.33 | 88.43 | 90.56 | |
| 9 | NN | 100 | 100.00 | 105.63 | 112.79 |
| 3opt-ND(24) | 5368 | 85.57 | 87.72 | 90.64 | |
| LK 5+2 | 5374 | 85.57 | 86.04 | 87.80 | |
| 10 | NN | 100 | 100.00 | 107.49 | 119.01 |
| 3opt-ND(24) | 4687 | 91.04 | 92.89 | 94.33 | |
| LK 5+2 | 4006 | 90.79 | 91.50 | 93.80 |
Thursday, July 20, 2017
Extending LK: 5-opt move, part 1/3
There are 148 pure 5-opt move types.
Note that the code below is for sequential pure 5-opt moves and it is supposed to be used with the code for pure 4-opt, 3-opt and 2-opt moves.
proc LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
G4a: Length_Gain;
tourOrderPrev: int): bool =
const
level = 4
var
improved: bool
searching: bool
c9, c10: City_Number
c8_pred, c8_succ: City_Number
c9_pred, c9_succ: City_Number
fwd: bool
G4, G5a, gainFromCloseUp: Length_Gain
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
tried_c9: int = 0
breadth: int
tourOrder: int
moveType: int
c2subseq, cLast: City_Number
Ga: Length_Gain
SubseqLvl: int
improved = false
fwd = (c2 == t_succ(c1))
c8_succ = t_succ(c8)
c8_pred = t_pred(c8)
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
for c9 in neighbors(c8):
if tried_c9 >= 2*Max_Breadth_4:
break find_promising_moves
# tests:
# when c9 is one of tour neighbors of c8,
# then the link (c6,c7) already exists in tour
# and we cannot add it to the tour
if (c9 == c8_succ) or (c9 == c8_pred):
continue
# link (c8,c9) should not be the same as (c2,c3)
if (c8 == c2) and (c9 == c3) or
(c8 == c3) and (c9 == c2):
continue
# link (c8,c9) should not be the same as (c4,c5)
if (c8 == c4) and (c9 == c5) or
(c8 == c5) and (c9 == c4):
continue
# if c9 is c1, then link (c10,c1) needed to close the tour
# would be the same as (c10,c9) already in in tour
if (c9 == c1):
continue
G4 = G4a - distance(c8, c9)
if G4 < 0: # c9 is too far from c8
break # all subsequent candidates for c9 are even worse
# if G4 > 0:
c9_succ = t_succ(c9)
c9_pred = t_pred(c9)
for c10 in [c9_succ, c9_pred]:
# tests:
# c10 should not be c1, when we close a tour.
# We check condition here, because we are not going to
# go deeper and pass possibly disconnecting move
# to *general* 6-opt proc
# (compare place of similar test in 4opt proc)
if (c10 == c1):
continue
# link (c9,c10) should not be the same as (c3,c4)
if (c9 == c3) and (c10 == c4) or
(c9 == c4) and (c10 == c3):
continue
# link (c9,c10) should not be the same as (c5,c6)
if (c9 == c5) and (c10 == c6) or
(c9 == c6) and (c10 == c5):
continue
tourOrder = TO_00 # do not remove this line!
case tourOrderPrev
of TO_12347856:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A347856
else:
tourOrder = TO_12A9347856
of TO_12348756:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A348756
else:
tourOrder = TO_12A9348756
of TO_12783456:
if inOrder(c4, c9, c5, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1278349A56
else:
tourOrder = TO_127834A956
of TO_12873456:
if inOrder(c4, c9, c5, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1287349A56
else:
tourOrder = TO_128734A956
of TO_12346587:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A346587
else:
tourOrder = TO_12A9346587
of TO_12347865:
if inOrder(c2, c9, c3, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A347865
else:
tourOrder = TO_12A9347865
of TO_12783465:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12783465A9
elif inOrder(c4, c9, c6, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1278349A65
elif inOrder(c8, c9, c3, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A93465
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9783465
of TO_12873465:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12873465A9
elif inOrder(c4, c9, c6, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1287349A65
elif inOrder(c7, c9, c3, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A3465
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A873465
of TO_12563478:
if inOrder(c4, c9, c7, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1256349A78
else:
tourOrder = TO_125634A978
elif inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A3478
else:
tourOrder = TO_1256A93478
elif inOrder(c2, c9, c5, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A563478
else:
tourOrder = TO_12A9563478
of TO_12563487:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12563487A9
elif inOrder(c4, c9, c8, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1256349A87
elif inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A3487
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A563487
of TO_12785634:
if inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1278569A34
else:
tourOrder = TO_127856A934
elif inOrder(c2, c9, c7, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A785634
else:
tourOrder = TO_12A9785634
of TO_12875634:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12875634A9
elif inOrder(c6, c9, c3, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1287569A34
elif inOrder(c7, c9, c5, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_1287A95634
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A875634
of TO_12567834:
if inOrder(c6, c9, c7, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A7834
else:
tourOrder = TO_1256A97834
of TO_12568734:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12568734A9
elif inOrder(c7, c9, c3, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_125687A934
elif inOrder(c6, c9, c8, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A8734
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9568734
of TO_12653478:
if inOrder(c4, c9, c7, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1265349A78
else:
tourOrder = TO_126534A978
elif inOrder(c5, c9, c3, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A3478
else:
tourOrder = TO_1265A93478
elif inOrder(c2, c9, c6, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A653478
else:
tourOrder = TO_12A9653478
of TO_12653487:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12653487A9
elif inOrder(c4, c9, c8, fwd):
if inOrder(c4, c9, c10, fwd):
tourOrder = TO_1265349A87
elif inOrder(c5, c9, c3, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_1265A93487
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9653487
of TO_12657834:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12657834A9
elif inOrder(c8, c9, c3, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_126578A934
elif inOrder(c5, c9, c7, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A7834
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9657834
of TO_12658734:
if inOrder(c7, c9, c3, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1265879A34
else:
tourOrder = TO_126587A934
elif inOrder(c2, c9, c6, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A658734
else:
tourOrder = TO_12A9658734
of TO_12786534:
if inOrder(c4, c9, c1, fwd):
if inOrder(c4, c10, c9, fwd):
tourOrder = TO_12786534A9
elif inOrder(c5, c9, c3, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1278659A34
elif inOrder(c8, c9, c6, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A96534
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A786534
of TO_12876534:
if inOrder(c7, c9, c6, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A6534
else:
tourOrder = TO_1287A96534
of TO_12435687:
if inOrder(c3, c9, c5, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A5687
else:
tourOrder = TO_1243A95687
elif inOrder(c2, c9, c4, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A435687
else:
tourOrder = TO_12A9435687
of TO_12437856:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12437856A9
elif inOrder(c8, c9, c5, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_124378A956
elif inOrder(c3, c9, c7, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_1243A97856
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A437856
of TO_12438756:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12438756A9
elif inOrder(c7, c9, c5, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1243879A56
elif inOrder(c3, c9, c8, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A8756
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9438756
of TO_12784356:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12784356A9
elif inOrder(c3, c9, c5, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1278439A56
elif inOrder(c8, c9, c4, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A94356
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9784356
of TO_12874356:
if inOrder(c6, c9, c1, fwd):
if inOrder(c6, c10, c9, fwd):
tourOrder = TO_12874356A9
elif inOrder(c3, c9, c5, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_128743A956
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A4356
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A874356
of TO_12436578:
if inOrder(c5, c9, c7, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1243659A78
else:
tourOrder = TO_124365A978
elif inOrder(c3, c9, c6, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A6578
else:
tourOrder = TO_1243A96578
elif inOrder(c2, c9, c4, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A436578
else:
tourOrder = TO_12A9436578
of TO_12436587:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12436587A9
elif inOrder(c5, c9, c8, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1243659A87
elif inOrder(c3, c9, c6, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_1243A96587
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A436587
of TO_12437865:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12437865A9
elif inOrder(c8, c9, c6, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_124378A965
elif inOrder(c3, c9, c7, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_12439A7865
else: # inOrder(c2, c9, c4, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9437865
of TO_12438765:
if inOrder(c7, c9, c6, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1243879A65
else:
tourOrder = TO_124387A965
of TO_12784365:
if inOrder(c3, c9, c6, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1278439A65
else:
tourOrder = TO_127843A965
elif inOrder(c2, c9, c7, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A784365
else:
tourOrder = TO_12A9784365
of TO_12874365:
if inOrder(c5, c9, c1, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_12874365A9
elif inOrder(c3, c9, c6, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_128743A965
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_1287A94365
else: # inOrder(c2, c9, c8, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A874365
of TO_12564378:
if inOrder(c3, c9, c7, fwd):
if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1256439A78
else:
tourOrder = TO_125643A978
elif inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A4378
else:
tourOrder = TO_1256A94378
elif inOrder(c2, c9, c5, fwd):
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A564378
else:
tourOrder = TO_12A9564378
of TO_12564387:
if inOrder(c7, c9, c1, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_12564387A9
elif inOrder(c3, c9, c8, fwd):
s if inOrder(c3, c9, c10, fwd):
tourOrder = TO_1256439A87
elif inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A4387
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c10, c9, fwd):
tourOrder = TO_12A9564387
of TO_12567843:
if inOrder(c6, c9, c7, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A7843
else:
tourOrder = TO_1256A97843
of TO_12568743:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12568743A9
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c10, c9, fwd):
tourOrder = TO_125687A943
elif inOrder(c6, c9, c8, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_12569A8743
else: # inOrder(c2, c9, c5, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A568743
of TO_12785643:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12785643A9
elif inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1278569A43
elif inOrder(c8, c9, c5, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_1278A95643
else: # inOrder(c2, c9, c7, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A785643
of TO_12875643:
if inOrder(c6, c9, c4, fwd):
if inOrder(c6, c9, c10, fwd):
tourOrder = TO_1287569A43
else:
tourOrder = TO_128756A943
elif inOrder(c7, c9, c5, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_12879A5643
else:
tourOrder = TO_1287A95643
of TO_12654387:
if inOrder(c5, c9, c4, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A4387
else:
tourOrder = TO_1265A94387
of TO_12657843:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12657843A9
elif inOrder(c8, c9, c4, fwd):
if inOrder(c8, c10, c9, fwd):
tourOrder = TO_126578A943
elif inOrder(c5, c9, c7, fwd):
if inOrder(c5, c10, c9, fwd):
tourOrder = TO_1265A97843
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A657843
of TO_12658743:
if inOrder(c3, c9, c1, fwd):
if inOrder(c3, c10, c9, fwd):
tourOrder = TO_12658743A9
elif inOrder(c7, c9, c4, fwd):
if inOrder(c7, c9, c10, fwd):
tourOrder = TO_1265879A43
elif inOrder(c5, c9, c8, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_12659A8743
else: # inOrder(c2, c9, c6, fwd)
if inOrder(c2, c9, c10, fwd):
tourOrder = TO_129A658743
of TO_12786543:
if inOrder(c5, c9, c4, fwd):
if inOrder(c5, c9, c10, fwd):
tourOrder = TO_1278659A43
else:
tourOrder = TO_127865A943
else: # of tourOrderPrev
continue
#end of testing variants
if tourOrder == TO_00:
moveType = move_type_0
else:
moveType = move_type_5
if moveType != move_type_0: # 6-opt not implemented
tried_c9 = tried_c9 + 1
G5a = G4 + distance(c9, c10)
goodSuffix = Suffix(c2iplus1: c9, c2iplus2: c10,
Ga: G5a,
tourOrder: tourOrder, moveType: moveType)
goodSufficesList.add(goodSuffix)
#end_loop for c10
#end_loop for neighbor_number
#end_block find_promising_moves
block evaluate_promising_moves:
if len(goodSufficesList) == 0:
# no promising moves
break evaluate_promising_moves
Save_Tour()
Save_DLB()
SortSufficesByGain(goodSufficesList)
# pass promising moves, one by one, to next level
# to check them there
breadth = min(len(goodSufficesList), Max_breadth_4)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
c9 = goodSuffix.c2iplus1
c10 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
tourOrder = goodSuffix.tourOrder
moveType = goodSuffix.moveType
if moveType != move_type_0: # connecting move
gainFromCloseUp = Ga - distance(c10, c1)
if gainFromCloseUp > 0:
improved = true
Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
tourOrder)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook,
[c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
break evaluate_promising_moves
when true: # not OPT_6_IMPLEMENTED:
# below we try to use general subsequent move
# after temporary applying 5-opt move
c2subseq = c10
cLast = c10
LinksAddedClear()
AddtoLinksAdded(c2, c3)
AddtoLinksAdded(c4, c5)
AddtoLinksAdded(c6, c7)
AddtoLinksAdded(c8, c9)
Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
tourOrder)
Set_DLB_off(DontLook,
[c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
searching = true
SubseqLvl = 0
while searching:
SubseqLvl = SubseqLvl + 1
improved = LK_SubsequentMove(c1, c2subseq, Ga, cLast)
if improved:
break evaluate_promising_moves
else: # not improved
if c2subseq == cLast: # end of promising moves
Restore_Tour()
Restore_DLB()
searching = false
else:
c2subseq = cLast
if SubseqLvl > Max_Depth:
Restore_Tour()
Restore_DLB()
searching = false
#end_loop for mve
#end_block evaluate_promising_moves
result = improved
Tuesday, July 18, 2017
Why 5-opt is much better than 4-opt
When we measure complexity or effectivenes of various k-opt optimizations, then 2-opt has weight of two, since by definition it exchanges two pairs of links, 3-opt exchanges three pairs of links, 4-opt exchanges four pairs, 5-opt exchanges five pairs and so on. But quite different image appears when we focus on number of pair exchanges, that is the number of basic transformations of tour required to make given type of k-opt move.
| move | pairs exchanged | exchanges made |
|---|---|---|
| 2-opt | 2 | 1 |
| 3-opt | 3 | 2 or 3 |
| 4-opt | 4 | 3 |
| 5-opt | 5 | 4 or 5 |
As we can see from this table 3-opt should be much better than 2-opt since it makes two or even three pair exchanges instead of only one. Then we expect that 4-opt would be somewhat better than 3-opt, but much less than 3-opt is better than 2-opt. The reason is that 3-opt already includes three possible exchanges and 4-opt adds no more exchanges, even though it provides more various cases. In contrast to this 5-opt involves four or even five exchanges, then more then 4-opt. This should make 5-optimization much better than 4-optimization, more than 4-optimization is better than 3-optimization. In fact this is seen in practice, therefore hardly any implementation uses 4-opt as its best method. Almost all implementations use either 3-opt or 5-opt.
Saturday, July 15, 2017
Lin-Kernighan algorithm basics – part 11
Lin-Kernighan algorithm idea is to try the most promising sequences, therefore we should rather sort candidates by decreasing accumulated gain, not by their distance from the last city used (order of nearest neighbors). So, for example:
type
Suffix = object
c2iplus1, c2iplus2: City_Number
Ga: Length_Gain
moveType: int
tourOrder: int
proc SortSufficesByGain(goodSufficesList: var seq[Suffix]) =
# sort the list to have the most promising at top
sort(goodSufficesList) do (x,y: Suffix) -> int:
result = cmp(y.Ga, x.Ga)
proc LK_2Move(c1, c2: City_Number;
G1a: Length_Gain): bool =
...
var
goodSuffix: Suffix
goodSufficesList: seq[Suffix]
breadth: int
...
block find_promising_moves:
goodSufficesList = @[] # empty list (sequence)
for c3 in neighbors(c2):
if tried_c3 > 2*Max_Breadth_1: # note multiplier
break find_promising_moves
...
c3_succ = t_succ(c3)
c3_pred = t_pred(c3)
for c4 in [c3_pred, c3_succ]:
if fwd and (c4 == c3_succ) or
not fwd and (c4 == c3_pred):
tourOrder = TO_1234
moveType = move_type_0
else:
tourOrder = TO_1243
moveType = move_type_2
#end_if fwd...
tried_c3 = tried_c3 + 1
G2a = G1 + distance(c3, c4)
goodSuffix = Suffix(c2iplus1: c3, c2iplus2: c4,
Ga: G2a,
tourOrder: tourOrder, moveType: moveType)
goodSufficesList.add(goodSuffix)
#end_loop for c4
#end_loop for neighbor_number
#end_block find_promising_moves
block evaluate_promising_moves:
if len(goodSufficesList) == 0:
# no promising moves
break evaluate_promising_moves
SortSufficesByGain(goodSufficesList)
breadth = min(len(goodSufficesList), Max_Breadth_1)
for mve in 0 .. breadth-1:
goodSuffix = goodSufficesList[mve]
c3 = goodSuffix.c2iplus1
c4 = goodSuffix.c2iplus2
Ga = goodSuffix.Ga
tourOrder = goodSuffix.tourOrder
moveType = goodSuffix.moveType
if moveType != move_type_0: # connecting move
gainFromCloseUp = Ga - distance(c4, c1)
if gainFromCloseUp > 0:
improved = true
Make_2opt_Move(c1, c2, c3, c4)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4])
break evaluate_promising_moves
if LK_3Move(c1, c2, c3, c4,
Ga, tourOrder):
improved = true
break evaluate_promising_moves
#end_block evaluate_promising_moves
result = improved
An alternative for sorting candidates
Instead of sorting we can use simpler solution used in original Lin-Kernighan algorithm that is: each time we consider two links to remove we should try the longer link as the first one. Then for example:
proc LK_2Move(c1, c2: City_Number;
G1a: Length_Gain): bool =
var
c4_A, c4_B: City_Number
...
block find_promising_moves:
for c3 in neighbors(c2):
...
c3_succ = t_succ(c3)
c3_pred = t_pred(c3)
if distance(c3, c3_succ) > distance(c3, c3_pred):
c4_A = c3_succ
c4_B = c3_pred
else:
c4_A = c3_pred
c4_B = c3_succ
for c4 in [c4_A, c4_B]:
if fwd and (c4 == c3_succ) or
not fwd and (c4 == c3_pred):
tourOrder = TO_1234
moveType = move_type_0
else:
tourOrder = TO_1243
moveType = move_type_2
#end_if fwd...
tried_c3 = tried_c3 + 1
G2a = G1 + distance(c3, c4)
if moveType != move_type_0: # connecting move
gainFromCloseUp = G2a - distance(c4, c1)
if gainFromCloseUp > 0:
# improving move found
improved = true
Make_2opt_Move(c1, c2, c3, c4)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4])
break find_promising_moves
if LK_3Move(c1, c2, c3, c4,
G2a, tourOrder):
improved = true
break find_promising_moveses
#end_loop for c4
#end_loop for neighbor_number
#end_block find_promising_moves
Monday, July 3, 2017
Lin-Kernighan algorithm basics – part 10
When using DLB and subsequent moves we need a variable and a pair of procs to save and restore DLB array:
var
DontLook_copy: DLB_Array
proc Save_DLB() =
DontLook_copy = DontLook
proc Restore_DLB() =
DontLook = DontLook_copy
The last part contains some additional constants, variables and procs used to maintain subsequent moves:
var
Max_Depth:int = 55
var
SubseqLvl: int
type
Link = array[0..1, City_Number]
var
linksAdded: array[0 .. N-1, Link]
linksAdded_Len: int = 0
proc LinksAddedClear() =
linksAdded_Len = 0
proc AddToLinksAdded(city_A, city_B: City_Number) =
var
city_L, city_R: City_Number
if city_A < city_B:
city_L = city_A
city_R = city_B
else:
city_L = city_B
city_R = city_A
linksAdded[linksAdded_Len] = [city_L, city_R]
linksAdded_Len = linksAdded_Len + 1
proc isLinkAdded(city_A, city_B: City_Number): bool =
var
city_L, city_R: City_Number
if city_A < city_B:
city_L = city_A
city_R = city_B
else:
city_L = city_B
city_R = city_A
result = false
for idx in 0 .. linksAdded_Len-1:
if (city_L == linksAdded[idx][0] and
city_R == linksAdded[idx][1]):
result = true
break
#end_loop idx
Note that procs for saving and restoring tour are not efficient. They can be replaced by procs for storing and "undoing" exchanges made, but this would reuquire additional means to make sure that recognized type of sequence does not change or is updated.
var
t_copy: Tour_Array
p_copy: City_Position_In_Tour
l_copy: Length
proc Save_Tour() =
t_copy = tour
p_copy = position
l_copy = tourLen
proc Restore_Tour() =
tour = t_copy
position = p_copy
tourLen = l_copy
Some simple statistics
| Problem # | Method | Time | Best | Avg | Worst |
|---|---|---|---|---|---|
| 1 | NN | 100 | 100.00 | 109.45 | 117.82 |
| 3opt-ND(24) | 4881 | 85.95 | 87.32 | 90.41 | |
| LK 4+2 | 2243 | 85.38 | 86.29 | 88.67 | |
| 2 | NN | 100 | 100.00 | 108.00 | 115.44 |
| 3opt-ND(24) | 4587 | 86.88 | 88.36 | 91.37 | |
| LK 4+2 | 1468 | 86.83 | 87.40 | 90.19 | |
| 3 | NN | 100 | 100.00 | 107.33 | 117.17 |
| 3opt-ND(24) | 4981 | 84.12 | 85.87 | 89.60 | |
| LK 4+2 | 2343 | 84.12 | 85.01 | 90.19 | |
| 4 | NN | 100 | 100.00 | 106.75 | 117.44 |
| 3opt-ND(24) | 4587 | 87.10 | 89.55 | 92.74 | |
| LK 4+2 | 2149 | 87.10 | 88.47 | 91.22 | |
| 5 | NN | 100 | 100.00 | 107.14 | 123.30 |
| 3opt-ND(24) | 4781 | 89.79 | 91.33 | 93.25 | |
| LK 4+2 | 2149 | 89.55 | 90.71 | 92.17 | |
| 6 | NN | 100 | 100.00 | 109.40 | 122.11 |
| 3opt-ND(24) | 5074 | 86.36 | 87.90 | 90.88 | |
| LK 4+2 | 2050 | 85.88 | 86.64 | 88.74 | |
| 7 | NN | 100 | 100.00 | 109.81 | 121.38 |
| 3opt-ND(24) | 4687 | 91.82 | 92.92 | 96.31 | |
| LK 4+2 | 1949 | 91.71 | 92.36 | 94.48 | |
| 8 | NN | 100 | 100.00 | 107.21 | 118.20 |
| 3opt-ND(24) | 4781 | 87.57 | 88.84 | 90.88 | |
| LK 4+2 | 2837 | 87.24 | 88.25 | 90.63 | |
| 9 | NN | 100 | 100.00 | 108.36 | 117.82 |
| 3opt-ND(24) | 4981 | 88.16 | 89.33 | 91.96 | |
| LK 4+2 | 1268 | 88.16 | 88.53 | 91.97 | |
| 10 | NN | 100 | 100.00 | 108.14 | 116.89 |
| 3opt-ND(24) | 5174 | 88.76 | 90.37 | 93.61 | |
| LK 4+2 | 2637 | 88.52 | 89.24 | 91.08 |
Subscribe to:
Posts (Atom)