数据结构与算法---山东大学课程中心30ppt课件.ppt

文档介绍：(TSP问题)、寻求问题解的常规思路首先列出所有候选解然后依次检查每一个解,直到找到所需的解【可行性前提】:候选解数量有限,:百元百鸡问题使用枚举法求解:百元买百鸡问题公鸡每只5元,母鸡每只3元,小鸡3只1元x+y+z=1005x+3y+z/3=1001<=x<=20,1<=y<=33解法:枚举所有满足条件的候选解缺点:运算量大;改进:,同时能够保证算法运行结束可以找到所需要的解;通常能够用来求解规模很大的问题。.2020/6/14回溯算法思想回溯算法,也叫试探算法。是一种系统的搜索问题的解的方法。【基本思想】从一条路往前走,能进则进,不能进则退回来,换一条路再试。.2020/6/15示例2:n皇后问题在n行n列的国际象棋棋盘上,若两个皇后位于同一行、同一列、同一对角线上,则称它们为互相攻击。【n皇后问题】找到这n个皇后的互不攻击的布局。/6/17用回溯算法解决问题的一般步骤一、定义一个解空间,这个解空间必须至少包含问题的一个解(可能最优);二、用易于搜索的方式组织该解空间。典型的组织方式是图(如迷宫)或树(如0/1背包)。三、按深度优先法从开始节点进行搜索。四、利用限界函数避免移动到不可能产生解的子空间。【回溯算法重要特性】问题的解空间通常是在搜索问题的解的过程中动态产生的。.2020/6/18示例:3*3迷宫问题(图16-1)1、定义解空间:包含从入口到出口的所有路径;2、组织解空间:用图的形式给出。从点(1,1)到(3,3)的每一条路径都定义了3*3迷宫解空间中的一个元素;3、搜索解空间:从开始节点(1,1)进行深度优先搜索。.2020/6/19示例:n个对象的0/1背包问题(图16-2)1、定义解空间:2n个长度为n的0/1向量集合;n=3时,解空间{(0,0,0),(0,1,0),(0,0,1,(1,0,0),(0,1,1),(1,0,1,(1,1,0),(1,1,1))}2、组织解空间:用树的形式给出。第i层到第i+1层节点的一条边上的数字:向量x中第i个分量的值xi;从根节点到叶节点的每一条路径都定义了解空间中的一个元素。3、搜索解空间:开始节点为根节点进行深度优先搜索。.2020/6/110