1701020034
数学真好玩 [:1701019766]
1701020035
数学真好玩 巡回推销员之谜
1701020036
1701020037
以推销员为主角的难题
1701020038
1701020039
数学世界中存在着一个有关“巡回推销员”的有趣难题。就像题目里说的这样，这个问题的主角就是“推销员”。
1701020040
1701020041
1701020042
1701020043
1701020044
巡回推销员问题
1701020045
1701020046
所谓“巡回推销员问题”就是“一个推销员每次造访一个城市，经过所有的城市后再回到出发点，怎样做才能让他移动的距离是最短路径”。今天去大阪，明天去广岛……将这个推销员想象成在日本全国范围内进行推销的工作人员就容易理解了。
1701020047
1701020048
别看题目好像很贴近生活又很简单，这可是“排列组合最适化问题”中有名的难题，就算用上超级计算机，想要求得最适合的解答也相当困难。
1701020049
1701020050
将城市数设为n，那么可能的路径总数就有n！/2n条。
1701020051
1701020052
当n是一个小数字时，我们可以尝试所有组合的可能，然后从中找到最短路径。可是，当n是一个很大的数字时，这种组合的数量会呈爆发式增长，想要尝试所有路线事实上是不可行的。
1701020053
1701020054
比如说，要经过10个城市时，路径排列的总数就达到了181440条；经过30个城市时，可能的路径就有4.42×1030条。
1701020055
1701020056
这个数字到底有多么令人绝望，我们用计算速度为10太Flops的计算机（1秒钟能演算1013次小数点浮动的计算机。顺便告诉大家，playstation 4的运算速度是1.84太Flops，地球模拟程序的运算速度是35.86太Flops），想要运算出所有的组合需要25万兆年以上。宇宙诞生已经经过了137亿年，却无法跟这项运算所需的时间相比。
1701020057
1701020058
隐藏在生活中的“排列组合最适化问题”
1701020059
1701020060
就像“费马大定理”一样，正因为这是个绝对性的难题，所以关于它的解法才得以进化。以“巡回推销员”为例的“排列组合最适化问题”是一个非常现实的问题。
1701020061
1701020062
超市的商品配送；
1701020063
1701020064
快递等的配送计划问题；
1701020065
1701020066
汽车导航系统的路径检索；
1701020067
1701020068
手机的频率分配；
1701020069
1701020070
铁路、航空乘务员的分配；
1701020071
1701020072
制作体育比赛日程表等的调度……
1701020073
1701020074
以上都是与我们日常生活息息相关的活动，而这些都是“排列组合最适化”的问题。“巡回推销员问题”自身已经被应用到了配送计划制订和电子线路板上安装零件时挖洞的顺序决定问题上。
1701020075
1701020076
十进制算法会遗传吗？
1701020077
1701020078
在“巡回推销员”的问题中，如果城市数很多的话，想求得最适答案简直难如登天。高效又严谨的求解方法还没有确立，因此求得近似解的方法就显得尤为重要了。其中有一种有效的近似值解法被称为“遗传算法”（Genetic Algorithm）。
1701020079
1701020080
“十进制算法”是一种决定计算顺序、旨在解决问题的阶段式方法。用特定的编程语言（C、Basic、Java等）来记述算法就叫作程序。
1701020081
1701020082
遗传算法是1975年由密歇根大学的约翰·霍兰德（1929～）提出的。生物的进化依赖于遗传因子的重组，他从生物的“进化过程”中得到启示，得出了“最适化算法”，即从遗传因子中选择复数的个体（解的候补）组成集团，再利用这个集团将解的候补一个个重组，以探索最合适的答案的计算方法。
1701020083