1153_用经典蚁群算法求解旅行商问题

1．问题提出

旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。本课题要求利用经典蚁群算法求解旅行商问题。

此课题有助于学生了解群体智能（SI）计算，激发其学习计算机科学的兴趣，为其进一步深造打下一定基础并提前开启一道门径，在此基础上可以进一步研究粒子群算法、遗传算法、蛙跳算法、人工鱼算法、野草算法、蜂群算法等。

2．功能要求

重复显示如图17所示的主菜单，在主菜单中选择任意一项，均实现相应功能。

…………………………………………...…………

.       请输入选项编号(0~3):            .

……………………………………………..………

.1——建立城市信息文件 .

.2——设定相关参数     .

.3——寻优计算         .

.0——退出系统         .

………………………………..……………………

图17 用经典蚁群算法求解旅行商问题主菜单

在主菜单中选择1，建立一个城市信息文件，用于存放城市的坐标等数据。

在主菜单中选择2，可以设定蚁群算法相关的一些参数，如蚁群中蚂蚁的个数，信息素挥发系数等。

在主菜单中选择3，即可进行TSP问题寻优计算，要求追加本次设定的参数及最终计算结果到一个文本文件中。

在主菜单中选择0，显示结束信息（如“感谢使用本软件！已正常退出，按任意键结束！”），按任意键后，退出本系统。

说明：可以根据实际情况适当增减主菜单中的菜单项，如增加一些创新功能项等。

3.  知识点及参考资料

知识点：链表、文件、循环、结构体、函数、数组等。

参考资料：蚁群算法原理及其应用（段海滨，2005，科学出版社）

NULL

NULL

NULL

NULL