Python3趣味系列题11

Python3趣味系列题11

一、问题描述
旅行商问题(Traveling Salesman Problem)，即TSP，又称为旅行推销员问题、货郎担问题，是数学领域中著名的问题之一。说的是一个旅行商要去往N个城市，每个城市只能去一次，最后还要回到开始出发的城市。选择的路径的路程必须是所有路径中值最小的。本文以全国34城市为例，利用 遗传算法(Genetic Algorithm) 获得最终的方案。其中城市之间的距离为城市经纬度之间的地球表面的距离。

二、解题思路

TSP，已经被证明为NP完全问题。当N较大时，无法通过枚举的方法来获得最优解。此时就可以通过优化求解的算法来获得最优解。遗传算法就是一种通过模拟自然进化过程来搜索最优解的方法。

通俗来讲，该算法就是首先随机给出一些解的集合(可看作某种生物的初始种群)，在选择比较接近最优解的解(物竞天择，适者生存)，然后集合中解与解之间生成新的解(父辈之间的基因交叉，形成新的个体)，单个解也可以变成新的解(个体产生了变异)，当集合中的解都很相似时(种群中的生物个体之间差异性不大)，就停止搜索。

遗传算法的步骤(以本题为例)：

• 编码