基于动态规划算法在TSP研究中的应用

　　时间：5月8日(周三)

　　地点：教13(101)

　　参训人员：21计科本1班；22人工智能本1班

　　专家简介：

　　余云，大数据与人工智能学院，副教授，硕士，软工教研室教师。主持省级质量工程3项，参与多项省级、校级教科研项目。指导多名学生参加学科竞赛分别荣获省级一、二、三等奖。

　　内容概要：

　　旅行商问题(Traveling Salesman Problem, TSP)是经典的组合优化问题，要求找到一条经过一系列城市的最短可能路径，每个城市仅访问一次，并最终返回起点城市。比如在物流配送、电路设计、制造调度等方面都面临最短路径求解。利用动态规划法解决TSP问题，如何定义子问题、构建最优解，建立TSP模型、构造状态转移方程等都是我们研究的重点内容。

　　本次报告分为两部分：

　　1.旅行商问题(TSP)、动态规划算法介绍，理解动态规划算法设计思想，以及如何建立状态转移方程和最优子结构

　　2.利用动态规划法解决TSP问题，实现最短路径求解，并解决实际问题。