程序的設(shè)計培訓(xùn)的講義搜索算法ppt課件

1、程序設(shè)計培訓(xùn)之5：搜索算法袁輝勇2019年4月20日 一個從起始狀態(tài)到達目標(biāo)狀態(tài)包含多步操作，一個從起始狀態(tài)到達目標(biāo)狀態(tài)包含多步操作，而每一步操作又有幾種可能，只有正確的操作才能而每一步操作又有幾種可能，只有正確的操作才能達到目標(biāo)如八皇后問題），這樣的問題可以看做達到目標(biāo)如八皇后問題），這樣的問題可以看做是一個樹。是一個樹。如果按照如果按照1-2-4-5-3-6-71-2-4-5-3-6-7的順序，叫深度優(yōu)先的順序，叫深度優(yōu)先(DFS)(DFS)如果按照如果按照1-2-3-4-5-6-71-2-3-4-5-6-7的順序，叫廣度優(yōu)先的順序，叫廣度優(yōu)先(BFS)(BFS)1 12 23 34 45

2、 56 67 7一、概述一、概述void DFS(int k) /處理第處理第k步步 if (k=n) /已經(jīng)處理到第已經(jīng)處理到第n步，到達目的狀態(tài)步，到達目的狀態(tài) 輸出結(jié)果輸出結(jié)果 else /處理第處理第k步步 for (int i=1; i=m; i+) /第第k步中有步中有m種可能種可能 處理第處理第k步步 DFS(k+1)；/進入第進入第k+1步步 二、深度優(yōu)先二、深度優(yōu)先(DFS)模板模板1：輸出輸出1-m個數(shù)中取個數(shù)中取n個數(shù)的所有多重排列。例如個數(shù)的所有多重排列。例如n=2，m=3的所有多重排列為：的所有多重排列為：1 11 21 32 12 22 33 13 23 3例例1：

3、多重排列問題：多重排列問題/從從1到到m中取中取n個數(shù)，允許重復(fù)取數(shù)個數(shù)，允許重復(fù)取數(shù)#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個數(shù)中取個數(shù)中取n個數(shù)的所有排列。例如個數(shù)的所有排列。例如n=2，m=3的所有排列為：的所有排列為：1 21 32 12 33 13 2例例2：排列問題：排列問題/從從1到到m中取中取n個數(shù)，不允許重

4、復(fù)取數(shù)個數(shù)，不允許重復(fù)取數(shù)#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個數(shù)，不允許重復(fù)取數(shù)，即排列方法個數(shù)，不允許重復(fù)取數(shù)，即排列方法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個數(shù)中取個數(shù)中取n個數(shù)的所有組合。例如個數(shù)的所有組合。例如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; /存放每個數(shù)存放每個數(shù)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個數(shù)開始個數(shù)開始 void DFS(int k) /處理第處理第k步步 for (int i=1; i=m; i+) /第第k步中有步中有m種可能種可能 處理第處理第k步步 if (k=n) /已經(jīng)處理完已經(jīng)處理完n步，到達目的狀步，到達目的狀態(tài)態(tài) 輸出結(jié)果；輸出結(jié)果； return； DFS(k+

7、1)；/進入第進入第k+1步步 二、深度優(yōu)先二、深度優(yōu)先(DFS)模板模板2：輸出輸出1-m個數(shù)中取個數(shù)中取n個數(shù)的所有多重排列。例如個數(shù)的所有多重排列。例如n=2，m=3的所有多重排列為：的所有多重排列為：1 11 21 32 12 22 33 13 23 3例例1：多重排列問題：多重排列問題/從從1到到m中取中取n個數(shù)，允許重復(fù)取數(shù)個數(shù)，允許重復(fù)取數(shù)#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個數(shù)中取個數(shù)中取n個數(shù)的所有排列。例如個數(shù)的所有排列。例如m=3 ，n=2的所有排列為：的所有排列為：1 21 32 12 33 13 2例例2：排列問題：排列問題/從從1到到m中取中取n個數(shù)，不允許重復(fù)取數(shù)個數(shù)，不允許重復(fù)取數(shù)#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個數(shù)，不允許重復(fù)取數(shù)個數(shù)，不允許重復(fù)取數(shù)#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個數(shù)中取個數(shù)中取n個數(shù)的所有組合。例如個數(shù)的所有組合。例如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; /存放每個數(shù)存放每個數(shù)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個數(shù)開始個數(shù)開始 /使用數(shù)組使用數(shù)組queue 存放結(jié)點隊

11、列存放結(jié)點隊列void BFS( ) head=0; tail=1; queuehead=首結(jié)點的值首結(jié)點的值; while (headtail) /隊列不空隊列不空 temp=tail; for (k=head; k=tail; k+) /對當(dāng)前層擴展對當(dāng)前層擴展 if ( 到達目的狀態(tài)到達目的狀態(tài) ) 輸出結(jié)果輸出結(jié)果; return; for (i=1; i=m; i+) /每個結(jié)點的每個結(jié)點的m種擴展可能種擴展可能 if (可以擴展可以擴展) 處理每種可能情況；處理每種可能情況； queuetemp+=擴展出的結(jié)點值擴展出的結(jié)點值; head=tail; tail=temp;三、廣度優(yōu)

12、先三、廣度優(yōu)先(BFS)模板模板1：/使用數(shù)組使用數(shù)組queue 存放結(jié)點隊列存放結(jié)點隊列void BFS( ) head=0; tail=1; queuehead=首結(jié)點的值首結(jié)點的值; while (headtail) /隊列不空隊列不空 if ( 到達目的狀態(tài)到達目的狀態(tài) ) 輸出結(jié)果輸出結(jié)果; break; head+; for (i=1; i=m; i+) /結(jié)點結(jié)點head的的m種擴展可能種擴展可能 if (可以擴展可以擴展) 處理每種可能情況；處理每種可能情況； queuetail+=擴展出的結(jié)點值擴展出的結(jié)點值; 四、廣度優(yōu)先四、廣度優(yōu)先(BFS)模板模板2：/使用使用STL中的隊列中的隊列void BFS( ) 首結(jié)點入隊列首結(jié)點入隊列Q; while ( ! Q.empty()