程序设计培训讲义6：搜索算法

1、程序设计培训之5：搜索算法袁辉勇2014年8月4日 一个从起始状态到达目标状态包含多步操作，一个从起始状态到达目标状态包含多步操作，而每一步操作又有几种可能，只有正确的操作才能而每一步操作又有几种可能，只有正确的操作才能达到目标（如八皇后问题），这样的问题可以看做达到目标（如八皇后问题），这样的问题可以看做是一个树。是一个树。如果按照如果按照1-2-4-5-3-6-71-2-4-5-3-6-7的顺序，叫深度优先的顺序，叫深度优先(DFS)(DFS)如果按照如果按照1-2-3-4-5-6-71-2-3-4-5-6-7的顺序，叫广度优先的顺序，叫广度优先(BFS)(BFS)1 12 23 34 4

2、5 56 67 7一、概述一、概述void DFS(int k) /处理第处理第k步步 if (k=n) /已经处理到第已经处理到第n步，到达目的状态步，到达目的状态 输出结果输出结果 else /处理第处理第k步步 for (int i=1; i=m; i+) /第第k步中有步中有m种可能种可能 处理第处理第k步步 DFS(k+1)；/进入第进入第k+1步步 二、深度优先二、深度优先(DFS)模板模板1：输出输出1-m个数中取个数中取n个数的所有多重排列。例如个数的所有多重排列。例如n=2，m=3的所有多重排列为：的所有多重排列为：1 11 21 32 12 22 33 13 23 3例例1

3、：多重排列问题：多重排列问题/从从1到到m中取中取n个数，允许重复取数个数，允许重复取数#include using namespace std;int n,m, a10;void DFS(int k) if (k=n) for (int i=0; in; i+) coutai ; coutendl; else for (int i=1; imn; DFS(0); return 0; 输出输出1-m个数中取个数中取n个数的所有排列。例如个数的所有排列。例如n=2，m=3的所有排列为：的所有排列为：1 21 32 12 33 13 2例例2：排列问题：排列问题/从从1到到m中取中取n个数，不允许

4、重复取数个数，不允许重复取数#include using namespace std;int n,m, a10; bool bz10;void DFS(int k) if (k=n) for (int i=0; in; i+) coutai ; coutendl; else for (int i=1; imn; DFS(0); return 0; /从从1到到m中取中取n个数，不允许重复取数，即排列方法个数，不允许重复取数，即排列方法2#include using namespace std;int n,m, a10;void DFS(int k) if (k=n) for (int i=0;

5、 in; i+) coutai ; coutendl; else for (int i=1; i=m; i+) int ok=1; for (int j=0; jmn; DFS(0); return 0; /从从1到到m中取中取n个数，不允许重复取数，即排列方法个数，不允许重复取数，即排列方法3#include using namespace std;int n,m, a10;void DFS(int k) if (k=n) for (int i=0; in; i+) coutai ; coutendl; else for (int i=k; imn; for (int i=0; im; i+

6、) ai=i+1; DFS(0); return 0; 输出输出m个数中取个数中取n个数的所有组合。例如个数的所有组合。例如m=5，n=3的所有组合为：的所有组合为：1 2 31 2 41 2 5 1 3 41 3 51 4 5 2 3 42 3 52 4 5 3 4 5例例3：组合问题：组合问题#includeusing namespace std;int m,n,a10; /存放每个数存放每个数void comb(int k)if ( kn ) for (int i=1; i=n;i+) coutai ; coutendl; else for (int i=ak-1+1; imn; com

7、b(1); /从第从第1个数开始个数开始 给定一个有给定一个有n个元素的集合，输出它所有可能个元素的集合，输出它所有可能的子集（共的子集（共2n个）。例如个）。例如3个数个数1、2、3的所有子集的所有子集为：为：空集空集11 21 31 2 322 33例例4：子集问题：子集问题/ 子集问题子集问题 dfs代码代码1#includeusing namespace std;int m,n,a10; /存放每个数存放每个数void DFS(int k) for (int i=0; ik; i+) coutai ; coutak-1+1; im; DFS(0); return 0; / 子集问题子集

8、问题 dfs代码代码2#include using namespace std;int n,m, a10;void DFS(int k) if (k=n) for (int i=0; in; i+) if (ai=1) couti+1 ; coutendl; else for (int i=0; in; DFS(0); return 0; / 子集问题子集问题 二进制转换法二进制转换法#include using namespace std;int n;int main() int i,j; cinn; for (i=0; i(1n); i+) for (j=0;jn;j+) if ( i&a

9、mp;(1j) coutj+1 ; coutendl; return 0;void DFS(int k) /处理第处理第k步步 for (int i=1; i=m; i+) /第第k步中有步中有m种可能种可能 处理第处理第k步步 if (k=n) /已经处理完已经处理完n步，到达目的状态步，到达目的状态 输出结果；输出结果； return； DFS(k+1)；/进入第进入第k+1步步 二、深度优先二、深度优先(DFS)模板模板2：输出输出1-m个数中取个数中取n个数的所有多重排列。例如个数的所有多重排列。例如n=2，m=3的所有多重排列为：的所有多重排列为：1 11 21 32 12 22 3

10、3 13 23 3例例1：多重排列问题：多重排列问题/从从1到到m中取中取n个数，允许重复取数个数，允许重复取数#include using namespace std;int n,m, a10;void DFS(int k) for (int i=1; i=m; i+) ak=i; if (k=n) for (int i=0; in; i+) coutai ; coutmn; DFS(0); return 0; 输出输出1-m个数中取个数中取n个数的所有排列。例如个数的所有排列。例如m=3 ，n=2的所有排列为：的所有排列为：1 21 32 12 33 13 2例例2：排列问题：排列问题/从

11、从1到到m中取中取n个数，不允许重复取数个数，不允许重复取数#include using namespace std;int n,m, a10; bool bz10;void DFS(int k) for (int i=1; i=m; i+) if ( !bzi ) ak=i; if (k=n) for (int i=0; in; i+) coutai ; coutmn; DFS(0); return 0; /从从1到到m中取中取n个数，不允许重复取数个数，不允许重复取数#include using namespace std;int n,m, a10;void DFS(int k) for

12、(int i=k; im; i+) if (k=n) for (int i=0; in; i+) coutai ; coutmn; for (int i=0; im; i+) ai=i+1; DFS(0); return 0; 输出输出m个数中取个数中取n个数的所有组合。例如个数的所有组合。例如m=5，n=3的所有组合为：的所有组合为：1 2 31 2 41 2 5 1 3 41 3 51 4 5 2 3 42 3 52 4 5 3 4 5例例3：组合问题：组合问题#includeusing namespace std;int m,n,a10; /存放每个数存放每个数void comb(int

13、 k) for (int i=ak-1+1; in ) for (int i=1; i=n;i+) printf(%5d,ai); printf(n); return; comb(k+1); int main( ) scanf(%d%d,&m,&n);comb(1); /从第从第1个数开始个数开始 有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。例如：设限制重量为7，现有4件物品，它们的重量和价值见下表，问如何物品的价值之和最大？物品0123重量5321价值4431例例4：0-1背包问题

14、回溯求解背包问题回溯求解/ 0-1背包问题的回溯算法：背包问题的回溯算法：#include #define M 10int wM=5,3,2,1, vM=4,4,3,1, limit_w=7, n=4; int tw=0, maxv=0, tv=0, bM=0 ;void find(int i) if (i=n) return; /已对所有物品作了判断已对所有物品作了判断if (tw+wi=limit_w ) /选择第选择第i件物品件物品 if (i=n-1) /进入第进入第i+1件的条件件的条件 tw=tw+wi; tv=tv+vi; bi=1; /选了第选了第i件件if (maxvtv)

15、maxv=tv;find(i+1); /进入第进入第i+1件件tw=tw-wi; tv=tv-vi; bi=0; /不选第不选第i件了件了 if (i=n-1) find(i+1); /不选择第不选择第i件物品件物品void main( )find(0); /从第从第0件物品开始选择件物品开始选择printf(maxv=%dn,maxv); /使用数组使用数组queue 存放结点队列存放结点队列void BFS( ) head=0; tail=1; queuehead=首结点的值首结点的值; while (headtail) /队列不空队列不空 temp=tail; for (k=head;

16、k=tail; k+) /对当前层扩展对当前层扩展 if ( 到达目的状态到达目的状态 ) 输出结果输出结果; return; for (i=1; i=m; i+) /每个结点的每个结点的m种扩展可能种扩展可能 if (可以扩展可以扩展) 处理每种可能情况；处理每种可能情况； queuetemp+=扩展出的结点值扩展出的结点值; head=tail; tail=temp;三、广度优先三、广度优先(BFS)模板模板1：/使用数组使用数组queue 存放结点队列存放结点队列void BFS( ) head=0; tail=1; queuehead=首结点的值首结点的值; while (headtail) /队列不空队列不空 if ( 到达目的状态到达目的状态 ) 输出结果输出结果; break; head+; for (i=1; i=m; i+) /结点结点head的的m种扩展可能种扩展可能 if (可以扩展可以扩展) 处理每种可能情况；处理每种可能情况； queuetail+=扩展出的结点值扩展出的结点值; 四、广度优先四、广度优先(BFS