用回溯法分析着色问题

用回溯法分析着色问题 - 1 - 算法设计与分析课程设计 题目：用回溯法分析着色问题 学院：理学院 专业：信息与计算科学 班级：09 信科二班 姓名：*** 学号: 200910010207 用回溯法分析着色问题 - 2 - 用回溯法分析着色问题 目录 1 回溯法 ..................................................... 3 1.1 回溯法的概述 ........................................... 3 1.2 回溯法的基本思想 ....................................... 3 1.3 回溯法的一般步骤 ...................................... 3 2 图的m 着色问题 ........................................... 3 2.1 图的着色问题的来源 ..................................... 3 2.2 通常所说的着色问题 ..................................... 3 2.3 图的着色问题描述 ....................................... 3 2.4 回溯法求解图着色问题 ................................... 5 2.5 图的m 可着色问题的回溯算法描述 ......................... 6 2.5.1 回溯算法 ............................................. 6 2.5.2 m 着色回溯法递归 ..................................... 8 2.5.3 m 着色回溯法迭代 .................................... 9 2.5.4 例题利用回溯法给图着色 .............................. 11 2.6 复杂度分析着色回溯法迭代 .............................. 12 用回溯法分析着色问题 - 3 - §1 回溯法 1.1 回溯法的概述 回溯法是一种系统地搜索问题解的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 1.2 回溯法的基本思想 回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开...