用回溯法分析着色问题 - 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 回溯法的基本思想 回溯法的基本思想是,在确定了解空间的组织结构后,回溯法就从开始结点(根结点)出发,以深度优先的方式搜索整个解空间。这个开...