TSP算法综述.ppt

TSP问题算法综述 理学院09212577李星晨 引言 旅行商问题 TravelingSalesmanProblem 简称TSP 是一个易于描述但难于解决的著名难题之一 TSP问题可描述为 已知n个城市各城市间的距离 某一旅行商从某个城市出发访问每个城市一次且仅一次 最后回到出发城市 怎样安排才使其所走路线最短 下面我来介绍最小生成树算法和分支界限法求解TSP问题的方法 最小生成树算法 对于N个城市的TSP问题 其城市的数目应为N 若N个城市中 每两个城市之间都有连通的路径 其连通路径数目应为n n 1 2 可以用含有n个顶点的完全连通无向图来形象的描绘TSP问题的已知条件 而此完全连通无向图中每条边上的权值 可以表示TSP问题中每两个顶点之间的路径长度 使用带权的完全无向连通图来分析TSP问题的求解过程 在一个加权图中 一棵生成树T的权是指T中各树枝的权之和 所有生成树中权最小的 成为图G的最小生成树 kruskal算法求最小生成树 Step1 把图G的所有边按边权递增顺序排列 若两条边的权相等 则其次序可任意排列Step2 选出G中最小权的边Step3 从剩下边中选取最小权的边 检查它是否和已有边构成回路 统计树枝数 若树枝数 n 1则算法停止 否则重复step3若按边权从大到小排列 则可得到最大生成树 最大手滑 最大经济效益等 例 设七城市间铺设数据线 路的造价如图所示 试求总造价最小的设计方案 解 顶点个数 v 7只需6条树枝 重绕生成树算法 Step1 求完全图G的最小生成树TStep2 重绕最小生成树T得到回路C0Step3 按访问的先后顺序检查C0 将出现的重复节点删去 最后一个节点除外 得一节点不重复的回路C 即为所求的H回路 设G是完全图 满足w u v w u x w x v 求最优回路H 1 2 3 4 5 6 重绕后的回路为12324215651 删除重复节点得1234561 分支界限算法 完全图的H回路共有 n 1 2种方案 不可能全部枚举 可采用部分枚举法来寻找最优解 先根据一些约束条件 产生解的部分空间树 从而加速搜索过程 分支界限法 定界 即求问题解的上界和下界 利用当前得到的下界排除一些次优解 任取一条回路 令其权作为上界的初始值 例 5城市间的距离矩阵如图D求旅行商推销问题的最优解 解 1 因H回路通过每个顶点一次且仅一次 故其在距离矩阵D中必含有每一行 每一列的一个元素 任取一回路 如 145321 即 v1 v4 v4 v5 v5 v3 v3 v2 v2 v1 权 14 7 11 9 17 60此权作为最优H回路的一个上界 即回路权长大于60的必不是最优解 对矩阵D作化简 确定每行的最小元素从相应行的每一个元素中间去这一行的最小元素得 14 6 6 7 8 D D1 除1 3列外 每行都有零元素 对1 3列作化简得 14 6 6 7 8 1 0 0 0 3 45 H 若回路 化简前与化简后的权分别为w和w1 则有关系式w w1 H 称为化简前回路的下界 D2 2 分支 在D2中 0元素坐在的位置整个回路权最小的可能位置 故首先选择D2元素为0的位置 i j 最优解 i j i j k l k l 首选元素d14 由于不能在选第一行第四列的其他元素 故在D2中换取第一行和第四列 同时避免从v4返回v1构成回路 令d41 A11 0 0 0 0 0 0 0 0 H 45 0 45 即含有 1 4 边的回路边权下界为45 对不含 1 4 变得回路子集 其矩阵中d14改为 然后化简矩阵 1 0 0 0 0 H 45 1 即不含 1 4 边的回路权下界为46即 45 最优解 60 46 1 4 60 45 1 4 60 沿右边分支继续分解 A12 A11中取零元素位置 2 5 令d52 划掉所在行和列 化简 A22 0 3 0 H 45 3 48 含 2 5 的最小下界为48 由A11 若回路不含 2 5 则令d25 后化简 0 0 0 11 H 45 11 56 48 在A12 不选 1 4 中 首选元素 1 5 并令d51 后化简 A 21 3 0 3 0 H 46 6 52 在A12中不选 1 5 令d15 A 22 0 0 9 0 H 46 9 55 45 最优解 60 46 1 4 60 45 1 4 60 55 1 5 52 1 5 56 2 5 48 2 5 在树中继续沿最小下界的分支作分解 因此回到含有 1 4 2 5 边的分支上 继续选边在A21中选定元素 4 2 划去v4行v2列 并令d24 A32 H 48 在A21中若不选元素 4 2 则令d42 后化简 A 32 0 12 0 H 48 12 60 继续在A32中取 3 1 元素后只剩 5 3 元素为0 且权和都不变 为48 45 最优解 60 46 1 4 60 45 1 4 60 55 1 5 52 1 5 56 2 5 48 2 5 48 4 2 48 3 1 48 5 3 60 4 2 3 1 5 3 权最小的回路由边v1v4 v2v5 v4v2 v3v1 v5v3构造 权最小的回路为 v1 v4 v2 v5 v3 v1权值为48 结束语 计算的复杂性研究表明 TSP问题是一个典型的NP难问题