算法 第5章 回溯法

《算法 第5章 回溯法》由会员分享，可在线阅读，更多相关《算法 第5章 回溯法（17页珍藏版）》请在文档大全上搜索。

1、12n“通用的解题法”。采用回溯法可以系系统地统地搜索一个问题的所有解所有解或任一解任一解。n算法的基本框架算法的基本框架：n需要为问题定义一个解空间解空间，这个解空间至少包含问题的一个（最优）解；n解空间: 给定问题的所有可能解解（情形情形） 0-10-1背包问题背包问题( (0-1 0-1 Knapsack Problem Knapsack Problem ) )设有设有n n个物体和一个背包个物体和一个背包, , 物体物体i i的重量为的重量为w wi i , , 价值为价值为v vi i, , 背包的承重背包的承重量为量为c c, , 若将物体若将物体i i (1(1 i i n)n)

2、装入背包装入背包, , 则有价值为则有价值为v vi i . .目标是找到一个方案目标是找到一个方案, , 使得能放入背包的物体总价值最高使得能放入背包的物体总价值最高例子例子当当n=3 , n=3 , 问题所有可能的解问题所有可能的解x=(x1, x2, x3) （解空间）（解空间）为为: (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)233n“通用的解题法”。采用回溯法可以系系统地统地搜索一个问题的所有解所有解或任一解任一解。n算法的基本框架算法的基本框架：n需要为

3、问题定义一个解空间解空间，这个解空间至少包含问题的一个（最优）解；n组织解空间组织解空间以便它能被容易地搜索。典型的组织方式是图图或是树树；n解空间树解空间树: : 假定左子树为假定左子树为1 1，右子树为，右子树为0 0 x1x2x34n“通用的解题法”。采用回溯法可以系统系统地地搜索一个问题的所有解所有解或任一解任一解。n算法的基本框架算法的基本框架：n需要为问题定义一个解空间解空间，这个解空间至少包含问题的一个（最优）解；n组织解空间组织解空间以便它能被容易地搜索。典型的组织方式是图图或是树树；n确定解空间的组织结构后，按深度优先深度优先方式从开始结点开始结点( (根结点根结点) )出发

4、搜索解空间。5nn=3，w=16,1515,15,v=45,2525,25,c=30V=45, r=14x1x2x3XV=45, r=14XV=45x=(1, 0, 0)V=0, r=30V=25, r=15V=50 x=(0, 1, 1)V=25x=(0, 1, 0)V=0, r=30V=25x=(0, 0, 1)V=0 x=(0, 0, 0)6 旅行商问题（旅行商问题（Travelling Salesman ProblemTravelling Salesman Problem）某售货员要到某售货员要到若干城市若干城市去推销商品，已知各城市间的路程去推销商品，已知各城市间的路程( (或旅或旅

5、费费) )。现要选定一条从驻地出发，经过。现要选定一条从驻地出发，经过每个城市每个城市一遍，最后回到驻一遍，最后回到驻地的路线，使总的路程地的路线，使总的路程( (总旅费总旅费) )最小。（以最小。（以4 4个城市为例）个城市为例）例例 2设设G=(V, E, W)G=(V, E, W)是一个带权完全图。图是一个带权完全图。图G G中的一条周游路线是包括中的一条周游路线是包括V V中的每个顶点在内的一条回路。旅行商问题就是要在图中的每个顶点在内的一条回路。旅行商问题就是要在图G G中找出中找出权值（费用）最小的周游路线。权值（费用）最小的周游路线。解空间：所有可以周解空间：所有可以周游的回路游