第六章 回溯法
目录
- 第六章 回溯法
- 1.3着色问题
- 2. 八皇后问题
- 3.哈密顿回路问题
回溯法是一种组织搜索的技术，被描述为有组织的穷尽搜索，它常常可以避免搜索所有的可能性。
基本思想：
- 针对所要做的选择构造一棵所谓的状态空间树，树的每一层节点代表了对解的每一个分量所做的选择。
- 用深度优先法搜索状态空间树。
- 在状态空间树中的任一节点，满足一定条件的情况下，搜索回溯。
1.3着色问题
问题描述：给出一个无向图G=（V，E），需要用三种颜色之 一为V中的每个顶点着色，三种颜色分别为1，2 和3，使得没有两个邻接的顶点有同样的颜色。我们把这样的着色称为合法的；否则，如果两个邻接的顶点有同一种颜色就是非法的。
搜索树结构：三叉树，每条路径代表一种着色指派。
递归法：
非递归法：
2. 八皇后问题
经典的8皇后问题：如何在8 x 8的国际象棋棋盘上安排8个皇后，使得没有两个皇后能互相攻击？ ( 如果两个皇后处在同一行、同一列或同一 条对角线上，则她们能互相攻击。）
同理可以定义4皇后和n皇后问题。对于4皇后问题，使用4叉树求解：
3.哈密顿回路问题
从图中的一个顶点出发，沿着边行走，经过图的每个顶点，且每个顶点仅访问一次，之后再回到起始点的一条路径。要求从起始点出发并能回到起始点，其路径是一个环。
什么是哈密尔顿回路/路径?_哈密顿回路-CSDN博客