干货|十分钟快速复习禁忌搜索(c++版)
说到的话一定要做到！做到！到！
昨天向大家保证今天分享 Tabu Search (TS) 代码 c++ 版本，然后，小编就去熬了个夜...
现在的小编 ↓ ↓ ↓
总之经过小编昨晚的狂肝，今天终于能将这份Tabu Search(TS) 复习加强攻略书(c++)版如约介绍给广大 骨·骼·清·奇 的算法master们！！
下面小编开始划重点了！
—禁忌搜索 · 概念篇 · 要素篇 · 代码篇—
坐稳发车！
概念篇
通过上一篇文章“干货 | 到底是什么算法，能让人们如此绝望？”的介绍，相信大家对于禁忌搜索算法都有了初步的认识...
什么？忘了？
不用担心！下面小编将帮大家简单划一下重点以供复习！拿走不谢！
所谓禁忌搜索是Local Search（LS）的扩展，是一种全局逐步寻优的全局性邻域搜索算法。
传统的 LS 通过迭代，不断搜寻邻域中更优的解来替换当前解，实现优化，该方式十分容易陷入局部最优。
而 TS 则是模仿人类的记忆功能，在搜索过程中标记已经找到的局部最优解及求解过程，并于之后的搜索中避开它们。
禁忌算法通过禁忌策略实现记忆功能，通过破禁准则继承LS的强局部搜索能力。种种机制的配合，使得TS一方面具备高局部搜索能力，同时又能防止算法在优化中陷入局部最优。
禁忌搜索的主要构成要素是
（1）评价函数（Evaluation Function）
（2）邻域移动（Move Operator）
（3）禁忌表（Tabu Table）
（4）邻居选择策略（Neighbor Selection Strategy）
（5）破禁准则（Aspiration Criterion）
（6）停止规则（Stop Criterion）
下面我们将着重从如上几个要素来透彻的理解禁忌搜索，且后续将给出相应的C++源码。
要素篇
代码篇
下面是日常溜代码时间 ↓ ↓ ↓
算
例
呈
现
例一 满秩矩阵式 ( type = 1 )
输入文件格式为：
File_name File_type
salesman.in 1
5
0 1 2 2 3
2 0 3 4 2
3 2 0 4 1
3 4 5 0 5
2 4 1 4 0
输出结果为：
opt_solution:
11
例二 二维坐标式 ( type = 2 )
输入文件格式为：
File_name File_type
KroA100.tsp 2
100
1 1380 939
2 2848 96
3 3510 1671
4 457 334
5 3888 666
6 984 965
7 2721 1482
8 1286 525
9 2716 1432
10 738 1325
11 1251 1832
12 2728 1698
13 3815 169
14 3683 1533
15 1247 1945
16 123 862
17 1234 1946
18 252 1240
19 611 673
20 2576 1676
21 928 1700
22 53 857
23 1807 1711
24 274 1420
25 2574 946
26 178 24
27 2678 1825
28 1795 962
29 3384 1498
30 3520 1079
31 1256 61
32 1424 1728
33 3913 192
34 3085 1528
35 2573 1969
36 463 1670
37 3875 598
38 298 1513
39 3479 821
40 2542 236
41 3955 1743
42 1323 280
43 3447 1830
44 2936 337
45 1621 1830
46 3373 1646
47 1393 1368
48 3874 1318
49 938 955
50 3022 474
51 2482 1183
52 3854 923
53 376 825
54 2519 135
55 2945 1622
56 953 268
57 2628 1479
58 2097 981
59 890 1846
60 2139 1806
61 2421 1007
62 2290 1810
63 1115 1052
64 2588 302
65 327 265
66 241 341
67 1917 687
68 2991 792
69 2573 599
70 19 674
71 3911 1673
72 872 1559
73 2863 558
74 929 1766
75 839 620
76 3893 102
77 2178 1619
78 3822 899
79 378 1048
80 1178 100
81 2599 901
82 3416 143
83 2961 1605
84 611 1384
85 3113 885
86 2597 1830
87 2586 1286
88 161 906
89 1429 134
90 742 1025
91 1625 1651
92 1187 706
93 1787 1009
94 22 987
95 3640 43
96 3756 882
97 776 392
98 1724 1642
99 198 1810
100 3950 1558
输出结果为：
best_known_solution: 21282
注意：
使用本程序的时候只需要建立一个上述文件名的文档，放在与源程序同目录下面，并运行程序，输入文件名以及数据类型。
例如：
运行程序之后会遇到以下提升：
input file_name and data type
只需要输入
KroA100.tsp 2
即可得到一个启发解以及相应路径
更多的数据可以从TSPLIB下载。
上述代码仅供分享交流学习用，如有需要请复制下面链接自取 ↓ ↓ ↓
http://paste.ubuntu.com/25449352/
或者戳文章底部 阅读原文 获取代码！
相信现在大家对禁忌搜索的相关内容更加了解了！
如果大家对 禁忌算法 及 文中所叙内容 还有疑问或想要交流心得建议，欢迎移步留言区！
最后再来一发安利——如果你是初学算法，或者是喜欢交流算法的master，再或者仅仅是想要了解算法是什么...欢迎关注我们的公众号和我们一起交流！学习！进步！
—end—
编辑：谢良桢（1922193128@qq.com）
贺兴（hexing15@gmail.com）
代码：贺兴（hexing15@gmail.com）
指导老师：秦时明岳（professor.qin@qq.com）