利用回溯算法来实现二分搜索树

❶ 回溯法搜索状态空间树是按照什么的顺序

按照中序遍历的顺序。

对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。

回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。

回溯法

与穷举法有某些联系，它们都是基于试探的。穷举法要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。

而对于回溯法，一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来。

❷ 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.