企业🤖AI智能体构建引擎,智能编排和调试,一键部署,支持私有化部署方案 广告
[TOC] # 问题描述 > 已给一个n个点的完全图,每条边都有一个权值。求总权值最小的经过每个顶点正好一次的封闭回路。 假设有如下TSP问题: ![](https://box.kancloud.cn/2016-06-03_5750fa8e482a5.PNG) 计算从顶点1出发,依次经过剩下所有的顶点,最后回到顶点1的最小权值。 * 穷举法: 所有构成环路的情况如下: 1-2-3-4 1-2-4-3 1-3-2-4 1-3-4-2 1-4-2-3 1-4-3-2 我们可以将这个解空间组织成一棵树,从树的根节点到任一结点的路径定义了图的一条回路。如图,从A到L的路径上边的标号组成了一条路线,即1,2,3,4。图中的每一条路线对应这个解空间中的一个解,所以解空间树的结点个数为**(n-1)!** ![](https://box.kancloud.cn/2016-06-03_5750fa8e61be9.PNG) 注意: 1. 该树是一棵排列树。 2. 最后到达叶子结点时,需要加上由叶子结点回到根节点的权值。 遍历: