《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 搜索法一》由會員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 搜索法一（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 搜索法一
在這里介紹兩種基本的搜索算法：深度優(yōu)先搜索和廣度優(yōu)先搜索法，以樹的搜索為例，深度優(yōu)先搜索法是優(yōu)先擴(kuò)展尚未擴(kuò)展的且具有最大深度的結(jié)點(diǎn)；廣度優(yōu)先搜索法是在擴(kuò)展完第K層的結(jié)點(diǎn)以后才擴(kuò)展K+1層的結(jié)點(diǎn)。
深度優(yōu)先搜索法與前面講的回溯法差不多，主要的區(qū)別是回溯法在求解過程中不保留完整的樹結(jié)構(gòu)，而深度優(yōu)先搜索則記下完整的搜索樹，搜索樹起記錄解路徑和狀態(tài)判重的作用。為了減少存儲空間，在深度優(yōu)先搜索中，用標(biāo)志的方法記錄訪問過的狀態(tài)，這種處理方法使得深度優(yōu)先搜索法與回溯法沒什么區(qū)別了。在回溯法中，我們己分析了非遞歸的實(shí)現(xiàn)過程，在這里就只討論深
2、度優(yōu)先的遞歸實(shí)現(xiàn)方法。
深度優(yōu)先搜索的遞歸實(shí)現(xiàn)過程：
procedure dfs(i);
for i:=1 to r do
if 子結(jié)點(diǎn)mr符合條件then 產(chǎn)生的子結(jié)點(diǎn)mr入棧；
if 子結(jié)點(diǎn) mr 是目標(biāo)結(jié)點(diǎn) then 輸出
else dfs(i+1);
棧頂元素出棧（即刪去mr）;
endif;
endfor;
在講解遞推法時(shí)，我們討論了用遞推法解騎土游歷問題，在這里我們再看看如何用深度優(yōu)先搜索法求解此題。
搜索算法應(yīng)用
例1騎士游歷:設(shè)有一個(gè)n*m的棋盤，在棋盤上任一點(diǎn)有一個(gè)中國象棋馬,馬走的規(guī)則為:1.馬走日字 2.馬只能向右走。當(dāng)N,M 輸入
3、之后,找出一條從左下角到右上角的路徑。例如:輸入 N=4,M=4，輸出:路徑的格式:(1,1)->(2,3)->(4,4)，若不存在路徑,則輸出"no"
算法分析：我們以4×4的棋盤為例進(jìn)行分析，用樹形結(jié)構(gòu)表示馬走的所有過程（如下圖），求從起點(diǎn)到終點(diǎn)的路徑,實(shí)際上就是從根結(jié)點(diǎn)開始深度優(yōu)先搜索這棵樹。
馬從（1，1）開始，按深度優(yōu)先搜索法，走一步到達(dá)（2，3），判斷是否到達(dá)終點(diǎn)，若沒有，則繼續(xù)往前走，再走一步到達(dá)（4，4），然后判斷是否到達(dá)終點(diǎn)，若到達(dá)則退出，搜索過程結(jié)束。為了減少搜索次數(shù)，在馬走的過程中，判斷下一步所走的位置是否在棋盤上，如果不在棋盤上，則另選一條路徑再走。
程序如下：
4、
const
dx:array[1..4]of integer=(2,2,1,1);
dy:array[1..4]of integer=(1,-1,2,-2);
type
map=record
x,y:integer;
end;
var
i,n,m:integer;
a:array[0..50]of map;
procedure dfs(i:integer);
var j:integer;
begin
for j:=1 to 4 do
if (a[i-1].x+dx[j]>0)and(a[i-1].x+dx[j]<
5、=n) and(a[i-1].y+dy[j]>0)and(a[i-1].y+dy[j]<=n) then{判斷是否在棋盤上}
begin
a[i].x:=a[i-1].x+dx[j];
a[i].y:=a[i-1].y+dy[j];{入棧}
if (a[i].x=n)and(a[i].y=m)then
begin
write('(',1,',',1,')');
for j:=2 to i do write('->(',a[j].x,',',a[j].y,')');
halt;
6、{輸出結(jié)果并退出程序}
end;
dfs(i+1);{搜索下一步}
a[i].x:=0;a[i].y:=0;{出棧}
end;
end;
begin
a[1].x:=1;a[1].y:=1;
readln(n,m);
dfs(2);
writeln('no');
end.
從上面的例子我們可以看出，深度優(yōu)先搜索算法有兩個(gè)特點(diǎn)：
1、 己產(chǎn)生的結(jié)點(diǎn)按深度排序，深度大的結(jié)點(diǎn)先得到擴(kuò)展，即先產(chǎn)生它的子結(jié)點(diǎn)。
2、 深度大的結(jié)點(diǎn)是后產(chǎn)生的，但先得到擴(kuò)展，即“后產(chǎn)生先擴(kuò)展”，與棧的工作原理相同，因此用堆棧作為
7、該算法的主要數(shù)據(jù)結(jié)構(gòu)，存儲產(chǎn)生的結(jié)點(diǎn)。
對于不同的問題，深度優(yōu)先搜索算法基本上是一樣的，但在具體處理方法和編程技巧上又都不相同，甚至?xí)泻艽蟮牟顒e。我們再看看另一個(gè)例子。
題二 選數(shù)（存盤名：NOIPxxpj）
[問題描述]:已知 n 個(gè)整數(shù) x1,x2,…,xn，以及一個(gè)整數(shù) k(k＜n)。從n 個(gè)整數(shù)中任選 k 個(gè)整數(shù)相加，可分別得到一系列的和。例如當(dāng) n=4，k＝3，4 個(gè)整數(shù)分別為 3，7，12，19 時(shí)，可得全部的組合與它們的和為：3＋7＋12=22 3＋7＋19＝29 7＋12＋19＝38 3＋12＋19＝34?，F(xiàn)在，要求你計(jì)算出和為素?cái)?shù)共有多少種。例如上例，只有一種的
8、和為素?cái)?shù)：3＋7＋19＝29。
[輸入]：鍵盤輸入，格式為：
n , k (1<=n<=20，k＜n)
x1,x2，…,xn （1<=xi<=5000000）
[輸出]：屏幕輸出，格式為：
一個(gè)整數(shù)（滿足條件的種數(shù)）。
[輸入輸出樣例]:
輸入：4 3
3 7 12 19
輸出：1
算法分析：本題是求從n個(gè)數(shù)中選k個(gè)數(shù)的組合，并使其和為素?cái)?shù)。求解此題時(shí)，先用深度優(yōu)先搜索法生成k個(gè)數(shù)的組合，再判斷k個(gè)數(shù)的和是否為素?cái)?shù)，若為素?cái)?shù)則總數(shù)加1。
在程序?qū)崿F(xiàn)過程中，用數(shù)組a存放輸入的n個(gè)數(shù)，用s表示k個(gè)數(shù)的和，ans表示和為素?cái)?shù)的個(gè)數(shù)。為了避免不必要的搜索
9、，程序?qū)λ阉鬟^程進(jìn)行了優(yōu)化，限制搜索范圍，在搜索過程dfs(i,m)中，參數(shù)m為第i個(gè)數(shù)的上限，下限為n-k+i。
源程序：
var
n,k,i: byte;
ans,s:longint;
a: array[1 .. 20] of Longint;
procedure prime(s:longint);{判斷K個(gè)數(shù)的和是否為素?cái)?shù)}
var
i:integer;
begin
i:=2;
while (sqr(i)<=s)and(s mod i<>0) do inc(i);
if sqr(i)>s then inc(ans){若為素?cái)?shù)則總數(shù)加1
10、}
end;
procedure dfs(i,m:byte);{搜索第i個(gè)數(shù)， }
var
j:byte;{j表示第i個(gè)數(shù)的位置
begin
for j:=m to n-k+i do{枚舉第i個(gè)數(shù)}
begin
inc(s,a[j]);{入棧}
if i=k then prime(s)
else dfs(i+1,j+1);{繼續(xù)搜第i+1個(gè)數(shù)}
dec(s,a[j]){出棧}
end
end;
begin
readln(n,k);
for i:=1 to n do read(a[i]);
ans:=0; s:=0;
dfs(1,1);
writeln(ans);
end.
從上面的兩個(gè)例子我們可以看出，用遞歸實(shí)現(xiàn)深度優(yōu)先搜索比非遞歸更加方便。
在使用深度搜索法解題時(shí)，搜索的效率并不高，所以要重視對算法的優(yōu)化，盡可能的減少搜索范圍，提高程序的速度。
在下一篇中將繼續(xù)介紹另一種搜索方法——廣度優(yōu)先搜索法。
2022年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 搜索法一
