程序设计培训讲义搜索算法.ppt

程序设计培训之5： 搜索算法,袁辉勇 2010年4月20日,一个从起始状态到达目标状态包含多步操作，而每一步操作又有几种可能，只有正确的操作才能达到目标（如八皇后问题），这样的问题可以看做是一个树。 如果按照1-2-4-5-3-6-7的顺序，叫深度优先(dfs) 如果按照1-2-3-4-5-6-7的顺序，叫广度优先(bfs),一、概述,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 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3,例1：多重排列问题,/从1到m中取n个数，允许重复取数 #include using namespace std; int n,m, a10; void dfs(int k) if (k=n) for (int i=0; imn; dfs(0); return 0; ,输出1-m个数中取n个数的所有排列。例如n=2，m=3的所有排列为： 1 2 1 3 2 1 2 3 3 1 3 2,例2：排列问题,/从1到m中取n个数，不允许重复取数 #include using namespace std; int n,m, a10; bool bz10; void dfs(int k) if (k=n) for (int i=0; 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; imn; for (int i=0; im; i+) ai=i+1; dfs(0); return 0; ,输出m个数中取n个数的所有组合。例如m=5，n=3的所有组合为： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5,例3：组合问题,#include using namespace std; int m,n,a10; /存放每个数 void comb(int k) if ( kn ) for (int i=1; i=n;i+)printf(“%5d“,ai); printf(“n“); else for (int i=ak-1+1; i=m-n+k; i+) ak=i; comb(k+1); int main( ) scanf(“%d%d“, /从第1个数开始 ,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 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3,例1：多重排列问题,/从1到m中取n个数，允许重复取数 #include using namespace std; int n,m, a10; void dfs(int k) for (int i=1; imn; dfs(0); return 0; ,输出1-m个数中取n个数的所有排列。例如m=3 ，n=2的所有排列为： 1 2 1 3 2 1 2 3 3 1 3 2,例2：排列问题,/从1到m中取n个数，不允许重复取数 #include using namespace std; int n,m, a10; bool bz10; void dfs(int k) for (int i=1; imn; for (int i=0; im; i+) ai=i+1; dfs(0); return 0; ,/从1到m中取n个数，不允许重复取数 #include using namespace std; int n,m, a10; void dfs(int k) for (int i=k; imn; dfs(0); return 0; ,输出m个数中取n个数的所有组合。例如m=5，n=3的所有组合为： 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5,例3：组合问题,#include using namespace std; int m,n,a10; /存放每个数 void comb(int 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“, /从第1个数开始 ,/使用数组queue 存放结点队列 void bfs( ) head=0; tail=1; queuehead=首结点的值; while (headtail) /队列不空 temp=tail; for (k=head; 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)模板2：,/使用stl中的队列 void bfs( ) 首结点入队列q; while ( ! q.empty()