利用回溯演算法來實現二分搜索樹

❶ 回溯法搜索狀態空間樹是按照什麼的順序

按照中序遍歷的順序。

對於用回溯法求解的問題，首先要將問題進行適當的轉化，得出狀態空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優先搜索這棵樹，枚舉每種可能的解的情況；從而得出結果。

回溯法中通過構造約束函數，可以大大提升程序效率，因為在深度優先搜索的過程中，不斷的將每個解與約束函數進行對照從而刪除一些不可能的解，這樣就不必繼續把解的剩餘部分列出從而節省部分時間。

回溯法

與窮舉法有某些聯系，它們都是基於試探的。窮舉法要將一個解的各個部分全部生成後，才檢查是否滿足條件，若不滿足，則直接放棄該完整解，然後再嘗試另一個可能的完整解，它並沒有沿著一個可能的完整解的各個部分逐步回退生成解的過程。

而對於回溯法，一個解的各個部分是逐步生成的，當發現當前生成的某部分不滿足約束條件時，就放棄該步所做的工作，退到上一步進行新的嘗試，而不是放棄整個解重來。

❷ Free Pascal 中的回溯演算法，具體講一下

1 回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 一、定義一個解空間，它包含問題的解。 二、利用適於搜索的方法組織解空間。 三、利用深度優先法搜索解空間。 四、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。 回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題.遞歸回溯：由於回溯法是對解空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法如下：procere try(i:integer);varbeginif i>n then 輸出結果else for j:=下界 to 上界 dobeginx:=h[j];if 可行{滿足限界函數和約束條件} then begin 置值；try(i+1); end;end;end; 說明：i是遞歸深度； n是深度控制，即解空間樹的的高度；可行性判斷有兩方面的內容：不滿約束條件則剪去相應子樹；若限界函數越界，也剪去相應子樹；兩者均滿足則進入下一層；搜索：全面訪問所有可能的情況，分為兩種：不考慮給定問題的特有性質，按事先頂好的順序，依次運用規則，即盲目搜索的方法；另一種則考慮問題給定的特有性質，選用合適的規則，提高搜索的效率，即啟發式的搜索。回溯即是較簡單、較常用的搜索策略。基本思路：若已有滿足約束條件的部分解，不妨設為（x1,x2,x3,……xi），I<n,則添加x(i+1)屬於s(i+2)，檢查(x1,x2,……,xi,x(i+1))是否滿足條件，滿足了就繼續添加x(i+2)、s(i+2)，若所有的x(i+1)屬於s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察過的x1屬於s1，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。

❸ 回溯法的基本思想是什麼

回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。 補充：

回溯法在問題的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索。

❹ 用C語言實現二分查找樹數據的查找、插入、修改、刪除

給你推薦一個網址
注冊激活後
專家幫你回答哦
祝你
成功哈
http://topic.csdn.net/t/20030701/20/1979410.html

❺ 編程PASCAL題目速度

皇後問題。在一個國際象棋棋盤上，放置8個皇後，使她們相互之間不能進攻(只要在一條直線上就不可，即在每一橫列豎列斜列只有一個皇後）。求出所有布局。
program eight;
var a:array [1..8] of integer;
b,c,d:array [-7..16] of integer;
t,i,j,k:integer;
procere print;
begin
t:=t+1;
write(t,' ');
for k:=1 to 8 do write(a[k],' ');
writeln;
end;

procere try(i:integer);
var j:integer;
begin
for j:=1 to 8 do {每個皇後都有8種可能位置}
if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判斷位置是否沖突}
begin
a[i]:=j; {擺放皇後}
b[j]:=1; {宣布佔領第J行}
c[i+j]:=1; {佔領兩個對角線}
d[i-j]:=1;
if i<8 then try(i+1) {8個皇後沒有擺完，遞歸擺放下一皇後}
else print; {完成任務，列印結果}
b[j]:=0; {回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
for k:=-7 to 16 do {數據初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{從第1個皇後開始放置}
end.
這是深搜的內容
搜索資料：
搜 索 算 法
搜索演算法是利用計算機的高性能來有目的的窮舉一個問題的部分或所有的可能情況，從而求出問題的解
的一種方法。搜索過程實際上是根據初始條件和擴展規則構造一棵解答樹並尋找符合目標狀態的節點的過程。
所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分——控制結構和產生系統，而所有的算
法的優化和改進主要都是通過修改其控制結構來完成的。現在主要對其控制結構進行討論，因此對其產生系
統作如下約定：
Function ExpendNode(Situation:Tsituation;ExpendWayNo:Integer):TSituation;
表示對給出的節點狀態Sitution採用第ExpendWayNo種擴展規則進行擴展，並且返回擴展後的狀態。
（本文所採用的演算法描述語言為類Pascal。）
第一部分 基本搜索演算法
一、回溯演算法
回溯演算法是所有搜索演算法中最為基本的一種演算法，其採用了一種「走不通就掉頭」思想作為其控制結構，
其相當於採用了先根遍歷的方法來構造解答樹，可用於找解或所有解以及最優解。具體的演算法描述如下：
[非遞歸演算法]
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
Way-NO:Integer（已使用過的擴展規則的數目）;
End
<Var>
List(回溯表):Array[1..Max(最大深度)] of Node;
pos(當前擴展節點編號):Integer;
<Init>
List<-0;
pos<-1;
List[1].Situation<-初始狀態;
<Main Program>
While (pos>0(有路可走)) and ([未達到目標]) do
Begin
If pos>=Max then (數據溢出,跳出主程序);
List[pos].Way-NO:=List[pos].Way-No+1;
If (List[pos].Way-NO<=TotalExpendMethod) then (如果還有沒用過的擴展規則)
Begin
If (可以使用當前擴展規則) then
Begin
(用第way條規則擴展當前節點)
List[pos+1].Situation:=ExpendNode(List[pos].Situation,
List[pos].Way-NO);
List[pos+1].Way-NO:=0;
pos:=pos+1;
End-If;
End-If
Else Begin
pos:=pos-1;
End-Else
End-While;
[遞歸演算法]
Procere BackTrack(Situation:TSituation;deepth:Integer);
Var I :Integer;
Begin
If deepth>Max then (空間達到極限,跳出本過程);
If Situation=Target then (找到目標);
For I:=1 to TotalExpendMethod do
Begin
BackTrack(ExpendNode(Situation,I),deepth+1);
End-For;
End;
範例：一個M*M的棋盤上某一點上有一個馬，要求尋找一條從這一點出發不重復的跳完棋盤上所有的點的路線。
評價：回溯演算法對空間的消耗較少，當其與分枝定界法一起使用時，對於所求解在解答樹中層次較深的問題
有較好的效果。但應避免在後繼節點可能與前繼節點相同的問題中使用，以免產生循環。
二、深度搜索與廣度搜索
深度搜索與廣度搜索的控制結構和產生系統很相似，唯一的區別在於對擴展節點選取上。由於其保留了
所有的前繼節點，所以在產生後繼節點時可以去掉一部分重復的節點，從而提高了搜索效率。這兩種演算法每
次都擴展一個節點的所有子節點，而不同的是，深度搜索下一次擴展的是本次擴展出來的子節點中的一個，
而廣度搜索擴展的則是本次擴展的節點的兄弟節點。在具體實現上為了提高效率,所以採用了不同的數據結構.
[廣度搜索]
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
Level:Integer(當前節點深度);
Last :Integer(父節點);
End
<Var>
List(節點表):Array[1..Max(最多節點數)] of Node(節點類型);
open(總節點數):Integer;
close(待擴展節點編號):Integer;
New-S:TSituation;(新節點)
<Init>
List<-0;
open<-1;
close<-0;
List[1].Situation<- 初始狀態;
List[1].Level:=1;
List[1].Last:=0;
<Main Program>
While (close<open(還有未擴展節點)) and
(open<Max(空間未用完)) and
(未找到目標節點) do
Begin
close:=close+1;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(List[close].Situation,I);
If Not (New-S in List) then
(擴展出的節點從未出現過)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Level:=List[close].Level+1;
List[open].Last:=close;
End-If
End-For;
End-While;
[深度搜索]
<Var>
Open:Array[1..Max] of Node;(待擴展節點表)
Close:Array[1..Max] of Node;(已擴展節點表)
openL,closeL:Integer;(表的長度)
New-S:Tsituation;(新狀態)
<Init>
Open<-0; Close<-0;
OpenL<-1;CloseL<-0;
Open[1].Situation<- 初始狀態;
Open[1].Level<-1;
Open[1].Last<-0;
<Main Program>
While (openL>0) and (closeL<Max) and (openL<Max) do
Begin
closeL:=closeL+1;
Close[closeL]:=Open[openL];
openL:=openL-1;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(Close[closeL].Situation,I);
If Not (New-S in List) then
(擴展出的節點從未出現過)
Begin
openL:=openL+1;
Open[openL].Situation:=New-S;
Open[openL].Level:=Close[closeL].Level+1;
Open[openL].Last:=closeL;
End-If
End-For;
End;
範例：迷宮問題，求解最短路徑和可通路徑。
評價：廣度搜索是求解最優解的一種較好的方法，在後面將會對其進行進一步的優化。而深度搜索多用於只
要求解，並且解答樹中的重復節點較多並且重復較難判斷時使用，但往往可以用A*或回溯演算法代替。
第二部分 搜索演算法的優化
一、雙向廣度搜索
廣度搜索雖然可以得到最優解，但是其空間消耗增長太快。但如果從正反兩個方向進行廣度搜索，理想
情況下可以減少二分之一的搜索量，從而提高搜索速度。
範例：有N個黑白棋子排成一派，中間任意兩個位置有兩個連續的空格。每次空格可以與序列中的某兩個棋子
交換位置，且兩子的次序不變。要求出入長度為length的一個初始狀態和一個目標狀態，求出最少的
轉化步數。
問題分析：該題要求求出最少的轉化步數，但如果直接使用廣度搜索，很容易產生數據溢出。但如果從初始
狀態和目標狀態兩個方向同時進行擴展，如果兩棵解答樹在某個節點第一次發生重合，則該節點
所連接的兩條路徑所拼成的路徑就是最優解。
對廣度搜索演算法的改進：
1。添加一張節點表，作為反向擴展表。
2。在while循環體中在正向擴展代碼後加入反向擴展代碼，其擴展過程不能與
正向過程共享一個for循環。
3。在正向擴展出一個節點後，需在反向表中查找是否有重合節點。反向擴展時
與之相同。
對雙向廣度搜索演算法的改進：
略微修改一下控制結構，每次while循環時只擴展正反兩個方向中節點數目較少的一個，可以使兩邊的發
展速度保持一定的平衡，從而減少總擴展節點的個數，加快搜索速度。
二、分支定界
分支定界實際上是A*演算法的一種雛形，其對於每個擴展出來的節點給出一個預期值，如果這個預期值不
如當前已經搜索出來的結果好的話，則將這個節點(包括其子節點)從解答樹中刪去，從而達到加快搜索速度
的目的。
範例：在一個商店中購物，設第I種商品的價格為Ci。但商店提供一種折扣，即給出一組商品的組合，如果一
次性購買了這一組商品，則可以享受較優惠的價格。現在給出一張購買清單和商店所提供的折扣清單，
要求利用這些折扣，使所付款最少。
問題分析：顯然，折扣使用的順序與最終結果無關，所以可以先將所有的折扣按折扣率從大到小排序，然後
採用回溯法的控制結構，對每個折扣從其最大可能使用次數向零遞減搜索，設A為以打完折扣後優
惠的價格，C為當前未打折扣的商品零售價之和，則其預期值為A+a*C，其中a為下一個折扣的折扣
率。如當前已是最後一個折扣，則a=1。
對回溯演算法的改進：
1。添加一個全局變數BestAnswer，記錄當前最優解。
2。在每次生成一個節點時，計算其預期值，並與BestAnswer比較。如果不好，則調用回溯過程。
三、A*演算法
A*演算法中更一般的引入了一個估價函數f,其定義為f=g+h。其中g為到達當前節點的耗費，而h表示對從當
前節點到達目標節點的耗費的估計。其必須滿足兩個條件：
1。h必須小於等於實際的從當前節點到達目標節點的最小耗費h*。
2。f必須保持單調遞增。

A*演算法的控制結構與廣度搜索的十分類似，只是每次擴展的都是當前待擴展節點中f值最小的一個，如果
擴展出來的節點與已擴展的節點重復，則刪去這個節點。如果與待擴展節點重復，如果這個節點的估價函數
值較小，則用其代替原待擴展節點，具體演算法描述如下：
範例：一個3*3的棋盤中有1-8八個數字和一個空格，現給出一個初始態和一個目標態，要求利用這個空格，
用最少的步數，使其到達目標態。
問題分析：預期值定義為h=|x-dx|+|y-dy|。
估價函數定義為f=g+h。
<Type>
Node(節點類型)＝Record
Situtation:TSituation（當前節點狀態）;
g:Integer;(到達當前狀態的耗費)
h:Integer;(預計的耗費)
f:Real;(估價函數值)
Last:Integer;(父節點)
End
<Var>
List(節點表):Array[1..Max(最多節點數)] of Node(節點類型);
open(總節點數):Integer;
close(待擴展節點編號):Integer;
New-S:Tsituation;(新節點)
<Init>
List<-0;
open<-1;
close<-0;
List[1].Situation<- 初始狀態;
<Main Program>
While (close<open(還有未擴展節點)) and
(open<Max(空間未用完)) and
(未找到目標節點) do
Begin
Begin
close:=close+1;
For I:=close+1 to open do (尋找估價函數值最小的節點)
Begin
if List.f<List[close].f then
Begin
交換List和List[close];
End-If;
End-For;
End;
For I:=1 to TotalExpendMethod do（擴展一層子節點）
Begin
New-S:=ExpendNode(List[close].Situation,I)
If Not (New-S in List[1..close]) then
(擴展出的節點未與已擴展的節點重復)
Begin
If Not (New-S in List[close+1..open]) then
(擴展出的節點未與待擴展的節點重復)
Begin
open:=open+1;
List[open].Situation:=New-S;
List[open].Last:=close;
List[open].g:=List[close].g+cost;
List[open].h:=GetH(List[open].Situation);
List[open].f:=List[open].h+List[open].g;
End-If
Else Begin
If List[close].g+cost+GetH(New-S)<List[same].f then
(擴展出來的節點的估價函數值小於與其相同的節點)
Begin
List[same].Situation:= New-S;
List[same].Last:=close;
List[same].g:=List[close].g+cost;
List[same].h:=GetH(List[open].Situation);
List[same].f:=List[open].h+List[open].g;
End-If;
End-Else;
End-If
End-For;
End-While;
對A*演算法的改進--分階段A*：
當A*演算法出現數據溢出時，從待擴展節點中取出若干個估價函數值較小的節點，然後放棄其餘的待擴展
節點，從而可以使搜索進一步的進行下去。
第三部分 搜索與動態規劃的結合
例1. 有一個棋子，其1、6面2、4面3、5面相對。現給出一個M*N的棋盤，棋子起初處於(1,1)點，擺放狀態
給定，現在要求用最少的步數從(1,1)點翻滾到(M,N)點，並且1面向上。
分析：這道題目用簡單的搜索很容易發生超時，特別當M、N較大時。所以可以考慮使用動態規劃來解題。對
於一個棋子，其總共只有24種狀態。在(1,1)點時，其向右翻滾至(2,1)點，向上翻滾至(1,2)點。而
任意（I，J）點的狀態是由（I-1，J）和（I，J-1）點狀態推導出來的。所以如果規定棋子只能向上
和向右翻滾，則可以用動態規劃的方法將到達（M，N）點的所有可能的狀態推導出來。顯然，從（1，
1）到達（N，M）這些狀態的路徑時最優的。如果這些狀態中有1面向上的，則已求出解。如果沒有，
則可以從（M，N）點開始廣度搜索，以（M，N）點的狀態組作為初始狀態，每擴展一步時，檢查當前
所得的狀態組是否有狀態與到達格子的狀態組中的狀態相同，如果有，則由動態規劃的最優性和廣度
搜索的最優性可以保證已求出最優解。
例2.給出一個正整數n，有基本元素a，要求通過最少次數的乘法，求出a^n。
分析：思路一：這道題從題面上來看非常象一道動態規劃題，a^n=a^x1*a^x2。在保證a^x1和a^x2的最優性之
後，a^n的最優性應該得到保證。但是仔細分析後可以發現，a^x1與a^x2的乘法過程中可能有
一部分的重復，所以在計算a^n時要減去其重復部分。由於重復部分的計算較繁瑣，所以可以
將其化為一組展開計算。描述如下：
I:=n;(拆分a^n)
split[n]:=x1;(分解方案)
Used[n]:=True;(在乘法過程中出現的數字)
Repeat(不斷分解數字)
Used[I-split[I]]:=True;
Used[split[I]]:=True;
Dec(I);
While (I>1) and (not Used[I]) do dec(I);
Until I=1;
For I:=n downto 1 do(計算總的乘法次數)
If Used[I] then count:=count+1;
Result:=count;(返回乘法次數)
思路二：通過對思路一的輸出結果的分析可以發現一個規律：
a^19=a^1*a^18
a^18=a^2*a^16
a^16=a^8*a^8
a^8=a^4*a^4
a^4=a^2*a^2
a^2=a*a
對於一個n，先構造一個最接近的2^k，然後利用在構造過程中產生的2^I,對n-2^k進行二進制分解，
可以得出解。對次數的計算的描述如下：
count:=0;
Repeat
If n mod 2 = 0 then count:=count+1
Else count:=count+2;
n:=n div 2;
Until n=1;
Result:=count;
反思：觀察下列數據：
a^15 a^23 a^27
Cost:5 Cost:6 Cost:6
a^2=a^1*a^1 a^2=a^1*a^1 a^2=a^1*a^1
a^3=a^1*a^2 a^3=a^1*a^2 a^3=a^1*a^2
a^6=a^3*a^3 a^5=a^2*a^3 a^6=a^3*a^3
a^12=a^6*a^6 a^10=a^5*a^5 a^12=a^6*a^6
a^15=a^3*a^12 a^20=a^10*a^10 a^24=a^12*a^12
a^23=a^3*a^20 a^27=a^3*a^24
這些數據都沒有採用思路二種的分解方法，而都優於思路二中所給出的解。但是經過實測，思路一二
的所有的解的情況相同，而卻得不出以上數據中的解。經過對a^2－a^15的數據的完全分析，發現對於
一個a^n，存在多個分解方法都可以得出最優解，而在思路一中只保留了一組分解方式。例如對於a^6
只保留了a^2*a^4，從而使a^3*a^3這條路中斷，以至採用思路一的演算法時無法得出正確的耗費值，從
而丟失了最優解。所以在計算a^n=a^x1*a^x2的重復時，要引入一個搜索過程。例如:a^15=a^3*a^12，
a^12=a^6*a^6，而a^6=a^3*a^3。如果採用了a^6=a^2*a^4，則必須多用一步。
<Type>
Link=^Node; （使用鏈表結構紀錄所有的可能解）
Node=Record
split:Integer;
next :Link;
End;
<Var>
Solution:Array[1..1000] of Link; （對於a^n的所有可能解）
Cost :Array[1..1000] of Integer; （解的代價）
max :Integer; （推算的上界）
<Main Program>
Procere GetSolution;
Var i,j :Integer;
min,c:Integer;
count:Integer;
temp,tail:Link;
plan :Array[1..500] of Integer;
nUsed:Array[1..1000] of Boolean;
Procere GetCost(From,Cost:Integer); （搜索計算最優解）
Var temp:Link;
a,b :Boolean;
i :Integer;
Begin
If Cost>c then Exit; （剪枝）
If From=1 then （遞歸終結條件）
Begin
If Cost<c then c:=Cost;
Exit;
End;
temp:=Solution[From];
While temp<>NIL do （搜索主體）
Begin
a:=nUsed[temp^.Split];
If not a then inc(cost);
nUsed[temp^.Split]:=True;
b:=nUsed[From - temp^.Split];
If not b then inc(cost);
nUsed[From-temp^.Split]:=True;
i:=From-1;
While (i>1) and (not nUsed) do dec(i);
GetCost(i,Cost);
If not a then dec(cost);
If not b then dec(cost);
nUsed[From-temp^.Split]:=b;
nUsed[temp^.Split]:=a;
temp:=temp^.next;
End;
End;
Begin
For i:=2 to Max do（動態規劃計算所有解）
Begin
count:=0;
min:=32767;
For j:=1 to i div 2 do （將I分解為I-J和J）
Begin
c:=32767;
FillChar(nUsed,Sizeof(nUsed),0);
nUsed[j]:=True;nUsed[i-j]:=True;
If j=i-j then GetCost(i-j,1)
Else GetCost(i-j,2);
If c<min then
Begin
count:=1;
min:=c;
plan[count]:=j;
End
Else if c=min then
Begin
inc(count);
plan[count]:=j;
End;
End;
new(solution); （構造解答鏈表）
solution^.split:=plan[1];
solution^.next:=NIL;
Cost:=min;
tail:=solution;
For j:=2 to count do
Begin
new(temp);
temp^.split:=plan[j];
temp^.next:=NIL;
tail^.next:=temp;
tail:=temp;
End;
End;
End;
背包問題：
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
{可用DP做}

❻ 請問什麼是回溯演算法

回溯（backtracking）是一種系統地搜索問題解答的方法。為了實現回溯，首先需要為問題定義一個解空間（solution space），這個空間必須至少包含問題的一個解（可能是最優的）。
下一步是組織解空間以便它能被容易地搜索。典型的組織方法是圖(迷宮問題)或樹(N皇後問題)。
一旦定義了解空間的組織方法，這個空間即可按深度優先的方法從開始節點進行搜索。

回溯方法的步驟如下：
1) 定義一個解空間，它包含問題的解。
2) 用適於搜索的方式組織該空間。
3) 用深度優先法搜索該空間，利用限界函數避免移動到不可能產生解的子空間。
回溯演算法的一個有趣的特性是在搜索執行的同時產生解空間。在搜索期間的任何時刻，僅保留從開始節點到當前節點的路徑。因此，回溯演算法的空間需求為O（從開始節點起最長路徑的長度）。這個特性非常重要，因為解空間的大小通常是最長路徑長度的指數或階乘。所以如果要存儲全部解空間的話，再多的空間也不夠用。

❼ java或者C/C++怎麼用回溯法解決最小長度電路板排列問題

以java為例，希望能夠幫到你。

電路板排列問題

問題描述

將n塊電路板以最佳排列方式插入帶有n個插槽的機箱中。n塊電路板的不同排列方式對應於不同的電路板插入方案。設B={1, 2, …, n}是n塊電路板的集合，L={N1, N2, …, Nm}是連接這n塊電路板中若干電路板的m個連接塊。Ni是B的一個子集，且Ni中的電路板用同一條導線連接在一起。設x表示n塊電路板的一個排列，即在機箱的第i個插槽中插入的電路板編號是x[i]。x所確定的電路板排列Density (x)密度定義為跨越相鄰電路板插槽的最大連線數。

例：如圖，設n=8, m=5，給定n塊電路板及其m個連接塊：B={1, 2, 3, 4, 5, 6, 7, 8}，N1={4, 5, 6}，N2={2, 3}，N3={1, 3}，N4={3, 6}，N5={7, 8};其中兩個可能的排列如圖所示，則該電路板排列的密度分別是2，3。

❽ 用偽碼描述回溯法搜索排列樹的演算法模式。

希望能幫到你！！！

❾ 簡述回溯法的2種演算法框架,並分別舉出適合用這兩種框架解決的一個問題實例

回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
基本思想
在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索演算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束

一般表達
可用回溯法求解的問題P，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關於n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。

規律
我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<=i）元組（x1，x2，…，xj）一定也滿足d中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反d中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反d中僅涉及到x1，x2，…，xi的一個約束，n≥i≥j。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…，xj）違反d中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題p的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。

❿ Pascal演算法之回溯及遞推詳細介紹、

遞歸 遞歸是計算機科學的一個重要概念,遞歸的方法是程序設計中有效的方法,採用遞歸編寫程序能是程序變得簡潔和清晰.2.1 遞歸的概念
1.概念一個過程(或函數)直接或間接調用自己本身,這種過程(或函數)叫遞歸過程(或函數).如:procere a; begin . . . a; . . .end;這種方式是直接調用.又如: procere b; procere c; begin begin . . . . . . c; b; . . . . . .end; end;這種方式是間接調用.例1計算n!可用遞歸公式如下: 1 當 n=0 時 fac(n)={n*fac(n-1) 當n>0時可編寫程序如下:program fac2;varn:integer;function fac(n:integer):real;beginif n=0 then fac:=1 else fac:=n*fac(n-1)end;beginwrite('n=');readln(n);writeln('fac(',n,')=',fac(n):6:0);end.例2 樓梯有n階台階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法.設n階台階的走法數為f(n)顯然有 1 n=1 f(n)={2 n=2 f(n-1)+f(n-2) n>2可編程序如下：program louti;var n:integer;function f(x:integer):integer;beginif x=1 then f:=1 elseif x=2 then f:=2 else f:=f(x-1)+f(x-2);end;beginwrite('n=');read(n);writeln('f(',n,')=',f(n))end.2.2 如何設計遞歸演算法
1.確定遞歸公式2.確定邊界(終了)條件練習:用遞歸的方法完成下列問題1.求數組中的最大數2.1+2+3+...+n3.求n個整數的積4.求n個整數的平均值5.求n個自然數的最大公約數與最小公倍數6.有一對雌雄兔,每兩個月就繁殖雌雄各一對兔子.問n個月後共有多少對兔子?7.已知:數列1,1,2,4,7,13,24,44,...求數列的第 n項. 2.3典型例題例3 梵塔問題 如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現要求把所有的盤子 從1針全部移到3針,移動規則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上不能出現大盤壓小盤.找出移動次數最小的方案. 程序如下:program fanta;varn:integer;procere move(n,a,b,c:integer);beginif n=1 then writeln(a,'--->',c)else beginmove(n-1,a,c,b);writeln(a,'--->',c);move(n-1,b,a,c);end;end;beginwrite('Enter n=');read(n);move(n,1,2,3);end.例4 快速排序快速排序的思想是:先從數據序列中選一個元素,並將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1, 處理結束.程序如下:program kspv;
const n=7;
type
arr=array[1..n] of integer;
var
a:arr;
i:integer;
procere quicksort(var b:arr; s,t:integer);
var i,j,x,t1:integer;
begin
i:=s;j:=t;x:=b[i];
repeat
while (b[j]>=x) and (j>i) do j:=j-1;
if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;
while (b[i]<=x) and (i<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=x;
i:=i+1;j:=j-1;
if s<j then quicksort(b,s,j);
if i<t then quicksort(b,i,t);
end;
begin
write('input data:');
for i:=1 to n do read(a[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]:6);
writeln;
end.練習:1.計算ackerman函數值: n+1 m=0 ack(m,n)={ ack(m-1,1) m<>0 ,n=0 ack(m-1,ack(m,n-1)) m<>0,n<>0 求ack(5,4)
回溯 回溯是按照某種條件往前試探搜索,若前進中遭到失敗,則回過頭來另擇通路繼續搜索.3.1 回溯的設計 1.用棧保存好前進中的某些狀態.2.制定好約束條件例1由鍵盤上輸入任意n個符號;輸出它的全排列.program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;
end;
begin
input;
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;
end.例2.n個皇後問題:program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
begin
k:=1;x[k]:=0;
while k>0 do
begin
x[k]:=x[k]+1;
while (x[k]<=n) and (not place(k)) do x[k]:=x[k]+1;
if x[k]>n then k:=k-1
else if k=n then print
else begin k:=k+1;x[k]:=0 end
end ;end.回溯演算法的公式如下:3.2 回溯演算法的遞歸實現由於回溯演算法用一棧數組實現的,用到棧一般可用遞歸實現。上述例1的遞歸方法實現如下：program hh;
const n=4;
var i,k:integer;
x:array[1..n] of integer;
st:string[n];
t:string[n];
procere input;
var i:integer;
begin
write('Enter string=');readln(st);
t:=st;
end;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if x[i]=x[k] then
begin place:=false; break end ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(t[x[i]]);
writeln;readln;
end;
procere try(k:integer);
var i :integer;
begin
if k=n+1 then begin print;exit end;
for i:=1 to n do
begin
x[k]:=i;
if place(k) then try(k+1)
end
end;
begin
input;
try(1);
end.例2：n皇後問題的遞歸演算法如下：程序1：program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.程序2：說明:當n=8 時有30條對角線分別用了l和r數組控制，用c數組控制列.當(i,j)點放好皇後後相應的對角線和列都為false.遞歸程序如下:program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.練習：1.找出所有從m個元素中選取n(n<=m)元素的組合。2.設有A,B,C,D,E 5人從事j1,j2,j3,j4,j5 5項工作每人只能從事一項,它們的效益表如下:求最佳安排,使效益最高.3.N個數中找出M個數(從鍵盤上輸入正整數N,M後再輸入N個正數),要求從N個數中找出若干個數,使它們的和為M,把滿足條件的數組找出來,並統計組數.4.地圖著色。如下圖12個區域用4種顏色著色要求相鄰的區域著不同的顏色5.將任意一正整數(1<n<100)分解成若干正整數的和. 如:4=1+1+1+1 =2+1+1 =2+2 =3+1.