[TOC] # 问题描述 > 已给一个n个点的完全图，每条边都有一个权值。求总权值最小的经过每个顶点正好一次的封闭回路。 假设有如下TSP问题：  计算从顶点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)!**  注意： 1. 该树是一棵排列树。 2. 最后到达叶子结点时，需要加上由叶子结点回到根节点的权值。 遍历：