精选优质文档-倾情为你奉上预备知识_回溯法回溯法：在实际生活中，有些问题是不能用数学公式去解决的，它需要通过一个过程，此过程要经过若干个步骤才能完成，每一个步骤又分为若干种可能；同时，为了完成任务，还必须遵守一些规则，但这些规则无法用数学公式表示，对于这样一类问题，一般采用搜索的方法来解决，回溯法就是搜索算法（广度优先、深度优先等）中的一种控制策略，它能够解决许多搜索中问题。回溯法基本思想：试探法，撞了南墙就回头。（一般采用深度优先搜索策略）搜索策略：深度优先（不撞南墙不回头）。在搜索过程中，如果求解失败，则返回搜索步骤中的上一点，去寻找新的路径，以求得答案。要返回搜索，前进中的某些状态必须保存，才能使得退回到某种状态后能继续向前。白话搜索：如果用数组存放搜索信息，i表示数组下标（当前状态）， +i表示往前走（下一个状态），-i表示回溯（往回退，返回上一次状态）。第8节 图论应用实例_图着色（graph coloring）问题数学定义：给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为k个颜色组（k为颜色
