1、搜索算法搜索給出初始節點，要求尋找到符合約束條件的目標節點給出初始節點和目標節點，要求找到從初始節點到目標節點的一條路徑。最優解？較優解？全部解？搜索算法枚舉廣度優先搜索深度優先搜索、回溯A*深度優先棧Why State?搜索深度優先搜索遞歸（系統棧）回溯（人工棧的維護）什么是棧？Function jc(n:integer):integer; begin if n=1 then jc:=1 else jc:=n*jc(n-1); end;Begin write(jc(4);End.432系統棧實例在調用過程或函數之前，系統需完成三件事：將所有的實在參數、返回地址等信息傳遞給被調用過程保存；為被

2、調用過程的局部變量分配存儲區；將控制轉移到被調過程的入口。從被調用過程返回調用過程之前，系統也應完成三件工作：保存被調過程的計算結果；釋放被調過程的數據區；依照被調過程保存的返回地址將控制轉移到調用過程。當有多個過程構成嵌套調用時，按照“后調用先返回”的原則系統棧漢諾塔（tower of Hanoi）問題。Procedure move(n:integer; A,B,C:char); if n=1 then AC else move(n-1，A，C，B) AC move(n-1，B，A，C) 請寫出系統棧的變化過程move(3,A,B,C)系統棧例線性讀寫操作都在棧頂先進后出棧的特點靜態數組Ty

3、pe arr=array1.n of integer; stack=record vec:arr; top:integer; end;Var s:stack;Var stack:arr; top:integer; 動態鏈表Type link=node; node=record info:integer; next:link; end;Var stack:link; top:link;棧的定義操作靜態數組(A,top)動態鏈表(H,top)建立棧測試棧是否為空讀棧頂元素進棧(push) 出棧(pop)Top:=0top:=nil;Top=0top=nil;AtopTTop:=top

4、+1; atop:=;？Top:=top-1; ？頭插法棧的基本操作入棧順序為1,2,3,n，出棧序列為p1,p2,p3,pn，已知p1=n，則pi=?入棧順序為1,2,3,n，出棧序列為p1,p2,p3,pn，已知pn=1，則pi=?棧s初始為空，有元素1,2,3,4,5，現進行進、進、進、初、進、出、進，問：出棧序列，棧頂指針，棧頂元素應用舉例元素e1,e2,e3,e4,e5,e6依次通過棧s，若出棧順序為2,4,3,6,5,1，則棧s的容量至少為？車廂重組：1,2,3,4,5進站，第一個到達出口的是3號車廂，問：可能的排列總數？應用舉例中綴表示法運算優先級問題、括號的出現改變運算順序后綴

5、表示法（逆波蘭式）-一次掃描棧的簡單應用表達式3/5+6 3 5 / 6 +6-9*(4+3)+5 6 9 4 3 + * - 5 +轉換方法2*(x+y)/(1-x)(25+x)*(a*(a+b)+b)后綴表示法6-9*(4+3)+5優先級運算符優先級#-1（0（入棧時不作優先級比較）+ -1* /2）單獨處理入棧標準：優先級大于棧頂元素優先級后綴表示法棧的使用# -16 - 19* 2( 04+ 13+*-+ 15+ 16943+*-5+6-9*(4+3)+5#6-9*(4+3)+53496+1(0*2-1#-1763-57+ 15-52中綴棧求解Procedure try(I); 選擇第

6、I個皇后的位置； if 安全 then (1) 放置第I個皇后； (2) if I=8 then 輸出 else try(I+1); 嘗試下一個位置；棧的應用八皇后（遞歸）13455248724648246462758245724885824762425253873837636382537335773625825523828352326374837463472486388247373663724For j:=1 to 8 do if bj and cI+j and dI-j then ai:=j; bj:=f; cI+j:=f; dI-j:=f; if I0 do j:=j+1; if j8

7、then top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top8 then print;八皇后非遞歸For j:=1 to 8 do if bj and cI+j and dI-j then ai:=j; bj:=f; cI+j:=f; dI-j:=f; if I0 do j:=j+1; if j 8 then top:=top-1; j:=atop; bj ctop+j dtop-j:=t; else if (top 8 then print;mm全排列非遞歸方式遞歸 回溯基本框架深度優先搜索素數環：將120這20個數擺成一個環，要求相

8、鄰的兩個數的和是一個素數走迷宮訓練方向：上下左右方向：右下左上研究背景背包問題簡單枚舉有5個背包（不可拆分），背包的價值(w)、體積(t)各不相等，在容量(tj)范圍內，如何選取，使價值最大？For a1:=0 to 1 do for a2:=0 to 1 do for a5:=0 to 1 do P;St:=aI*tI;Sw:=aI*wIIf stmax then 記錄狀態；有n個背包，問題如何解決？回溯窮舉A: 123450000000001000100001111111逢1進位分析問題找出實質初值：0 0 0 0 0找到需要進位的下標如何查找？N1 結束標記？實質For I:=0 to

9、n do aI:=0;While a0=0 do j:=n; while aj=1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:=0; 計算P;打??；程序框架逢1進位N個砝碼（1，3，9，3n-1）可以放在重物一側，也可以放在砝碼一側，給出一個重量，問：如何稱？While a0=0 do j:=n; while aj=1 do j:=j-1; aj:=aj+1; for I:=j+1 to n do aI:= 0 ; 計算;-1逢1進位有n種背包，每種背包有若干個(bi)，While a0=0 do j:=n; while aj= 1 do j:=j-

10、1; aj:=aj+1; for I:=j+1 to n do aI:= 0 ; 計算;Bj相等進位從1m中任意取出n個，打印所有取法123124125134135145234235245345保證不重復選擇 升序第n 位進位標志：m第n-1位進位標志：m-1第 j 位進位標志?相等進位組合問題深度優先搜索深入應用跳馬周游棋盤問題一棵八叉樹八個方向：目前位置(i,j)，下一個位置：可能為：(i+1,j+2),(i-1,j+2),(i-2,j+1),(i-2,j-1),(i-1,j-2),(i+1,j-2),(i+2,j-1),(i+2,j+1)用二維數組表示棋盤，未走過的地方設置為0bi1,j

11、1 0 當棋格 ( i1, j 1) 未被占據 i 當棋格 ( i1, j1) 在第 i 次移動中被占據范圍：未走過的和不越出棋盤邊界的那些位置為了防止馬跳出棋盤，將棋盤擴大二圈，這些位置的表示設置為-1分析縮小搜索范圍避免無效搜索改變搜索次序在幾個可能到達的位置中根據優劣條件選擇一個最優點來跳馬剪枝深度優先搜索的優化方法 編一個程序，找出一條通過迷宮的路徑。這里顯示為1的單元表示走不通，將一只老鼠從入口處經過迷宮到出口處的通路一一打印出來。010000001000010001100000111001100000 000000010入口 出口 迷宮問題基本題161234567891010001

12、0012000010101310100011140011000005000010010找出一個從入口到出口的最短路徑（八個方向）迷宮問題總行數：0m+1, 總列數： 0n+1 11111111111101000100111000010101111010001111100110000011000010010111111111111在深搜過程中，記錄搜索步數并與最小值進行比較，記錄當前最佳方案，最后打印輸出能否改進？方案1從步數的角度考慮問題，分別列舉出一步能到達的結點、兩步能到達的結點、發現的終點肯定是最優方案如何記錄方案？記錄每個結點的來由方案28個方向表示可以用數組說明：1012113104

13、1-150-16-1-17-108-11如何記錄探索的蹤跡？隊列序號123456X123332Y123144pre012233基本如何防止重復探索：將迷宮中的0替換為-1隊列中入隊、出隊情況如下表：迷宮問題程序迷宮（用不同的顏色表示步數）與深搜區別之一：搜索的方向不影響搜索規模主要影響因素是什么？迷宮變形：起點在迷宮中心、幾乎沒有障礙結論迷宮變形在寬搜過程中，隊列以幾何數量級擴展，擴展層數越大，對存儲的威脅越大如何對存儲進行壓縮？雙向搜索結論現要找出一條從A到B經過城市最少的一條路線。廣度優先遍歷: A 應用F,r,隊列初始化；While f=r do 取隊首； 寬搜基本框架sq1.x:=1

14、;sq1.y:=1 ;sq1.pre:=0 ;front :=1; rear :=1 ; mg1,1:=-1 ;while front=rear do x:=sqfront.x ; y:= sqfront.y ; for v:=1 to 8 do I:=x+zv.x ; j:= y+zv.y ; if mgI,j =0 then rear :=rear+1 ; sqrear.pre:=front ; sqrear.x:=I ; sqrear.y:=j ; mgI,j:= -1 ; if ( i=m ) and (j=n) then print; front := front+1 ; 設有數字2

15、，3，5，7，13，運算符號：+,*, 且運算無優先級之分，如2+3*5=25，3*5+2=17，編寫一個程序，給出任意一個整數n，要求用以上的數和運算符，以最少的運算次數產生出n。 例如：n=7,7=7,（0次運算）n=93，93=13*7+2 （2次運算 ）。 例 數值計算（1）數據的結構：參加運算的數據、參加運算的符號可以用常量數組 data12，data23，參與運算數據、符號順序 （2）每步參加運算的數據及運算符號 x, y , t：被加數、加數，結果（x ），t ：從哪一步計算到此。 分析算法模式給出一個整數n(n1030)和k個變換規則（k=R and 反面個數=5-R num=

16、R and (10-num)=5-R num=R and num-R=5 0=num-R=5 R=05翻幣問題問題求解模式：狀態A-狀態B且AB同質正向隊列Q1（隊列首為起始狀態A）反向隊列Q2（隊列首為目標狀態B）雙向搜索while (f1=r1) and (f2=r2) do data1=q1f1 for i=1 to 方案總數 計算得新狀態temp1 if 為新狀態 (在q1內比對判重) 入隊q1 if 與q2有相同狀態(在q2內比對判重) then 終止搜索，得到解決方案 data2=q2f2 for i=1 to 方案總數 計算得新狀態temp2 if 為新狀態(在q2內比對判重) 入隊q2 if 與q1有相同狀態(在q1內比對判重 ) then 終止搜索，得到解決方案 f1+; f2+ 在隊列中只需記錄正面個數翻了i個正面，(5-i)個反面的硬幣后正向硬幣的個數打印方向：從前往后：遞歸 從后望前：非遞歸/遞歸交界處重復打印翻幣次數如何計算易錯點最少拐彎問題作業騎士問題過河問題登山問題1345524872464824646