程序的设计培训的讲义搜索算法ppt课件

1、程序设计培训之5：搜索算法袁辉勇2019年4月20日 一个从起始状态到达目标状态包含多步操作，一个从起始状态到达目标状态包含多步操作，而每一步操作又有几种可能，只有正确的操作才能而每一步操作又有几种可能，只有正确的操作才能达到目标如八皇后问题），这样的问题可以看做达到目标如八皇后问题），这样的问题可以看做是一个树。是一个树。如果按照如果按照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 45

2、 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=k; imn; 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 k)if ( kn ) fo

6、r (int i=1; i=n;i+)printf(%5d,ai);printf(n); elsefor (int i=ak-1+1; i=m-n+k; i+)ak=i; comb(k+1); int main( ) scanf(%d%d,&m,&n);comb(1); /从第从第1个数开始个数开始 void DFS(int k) /处理第处理第k步步 for (int i=1; i=m; i+) /第第k步中有步中有m种可能种可能 处理第处理第k步步 if (k=n) /已经处理完已经处理完n步，到达目的状步，到达目的状态态 输出结果；输出结果； return； DFS(k+

7、1)；/进入第进入第k+1步步 二、深度优先二、深度优先(DFS)模板模板2：输出输出1-m个数中取个数中取n个数的所有多重排列。例如个数的所有多重排列。例如n=2，m=3的所有多重排列为：的所有多重排列为：1 11 21 32 12 22 33 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+) cout

8、ai ; coutmn; DFS(0); return 0; 输出输出1-m个数中取个数中取n个数的所有排列。例如个数的所有排列。例如m=3 ，n=2的所有排列为：的所有排列为：1 21 32 12 33 13 2例例2：排列问题：排列问题/从从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

9、; coutmn; 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; im; i+) if (k=n) for (int i=0; in; i+) coutai ; coutmn; DFS(0); return 0; 输出输出m个数中取个数中取n个数的所有组合。例如个数的所有组合。例如m=5，n=3的所有组合为：的所有组合为：1 2 31 2

10、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) 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个数开始个数开始 /使用数组使用数组queue 存放结点队

11、列存放结点队列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;三、广度优

12、先三、广度优先(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()