Free Pascal 中的回溯算法,具体讲一下

发布网友发布时间：2022-04-25 14:59

共2个回答

热心网友时间：2023-07-30 07:11

1 回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。　　用回溯算法解决问题的一般步骤为：　　一、定义一个解空间，它包含问题的解。　　二、利用适于搜索的方法组织解空间。　　三、利用深度优先法搜索解空间。　　四、利用限界函数避免移动到不可能产生解的子空间。　　问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。　　回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.　　递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：　　procere try(i:integer);　　var　　begin　　if i>n then 输出结果　　else for j:=下界 to 上界 do　　begin　　x:=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，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。

热心网友时间：2023-07-30 07:11

怎么讲？简单地说就是先序遍历，按这种方式自顶向下依次进行深度优先搜索追问不好意思，听不懂