【算法设计与分析】-回溯法的回忆-学习【期末复习篇章】

在这里插入图片描述

引言

简单说,迷宫问题的求解方法就是走的通就走，走不通就回头寻找另外的路径的一种满足某约束条件的穷举式搜索技术

回溯法是一种在解空间中搜索可行解或最优解的方法。
该方法通常将解空间看做树形结构，即状态空间树。从根结
点开始,以深度优先对状态空间树进行遍历避免遗漏可行解。
另
外，该过程以跳跃式搜索改善算法的运行效率，即不满足约束条
件的内结点的子树将被剪掉，
此时，搜索过程将回溯至该结点的父结点进行后续深度遍历。
通俗的讲，就是走的通就走，走不通就回头寻找另外的路径
的一种满足某约束条件的穷举式搜索技术。

回溯法的概述

回溯法适合于求解那些涉及到寻找一个或全部可行解的问
题（搜索问题）或者求满足某些约束条件的一个或全部最优解
的最优化问题

适合于用回溯法求解的问题应具备以下特征：
q 问题的解可表示成n-元组形式；
q 问题提供 显示约束确定状态空间树（解空间），并提供
来判定可行解；
q 应能设计有效的约束函数 ，缩小检索空间

问题的解空间

相关概念:
•解向量：一个问题的解能够表示成一个n元式(x0,x1,…,xn-1)
的形式。
•显约束：规定每个分量xi的取值的约束条件,称为~。
•解空间：满足显式约束条件的所有多元组(侯选解),构成了一
个解空间。
•隐约束：判定一个侯选解是否是可行解的约束条件。
•判定函数：判定部分元组是否满足隐式约束的函数。
•目标函数：用来衡量每个可行解的优劣程度的函数。
•最优解：使目标函数取最大值（或最小值）的可行解。

问题的解空间

相关概念:
•状态空间树：描述问题解空间的树型结构。

例：n=3时 w=[2,4,3]，p=[5,10,3]，背包容量M=5
在这里插入图片描述
n=3时的0-1背包问题用完全二叉树表示的解空间

求解过程分为3步，分别对第0、1、2个物品做决策，该解空间的每
个叶子结点都构成一个解

问题的解空间

问题状态：状态空间树中的每个结点称为一个问题状态。
•解状态：从根到树中某结点的路径代表一个作为侯选解的元组,则该
结点称为解状态。
•答案状态：从根到某个解结点的路径代表一个作为可行解的元组,则
称该解状态为答案状态。
•最优答案状态：使目标函数取最优值的答案结点称为最优答案结点。

通过搜索状态空间树来寻找答案状态的方法
最简单的方法是:使用某种搜索方法，检查树中每个问题状态，
如果是解状态，则用判定函数判定它是否是答案状态;对于最优化问
题，在搜索过程中还需对每个答案结点计算其目标函数值，并记录下
其中最优者。
注:状态空间树不需要事先生成,只需在求解的过程中，随着搜
索算法的进展，逐个生成状态空间树的问题状态结点

扩展结点:正在产生儿子的结点称为扩展结点
活结点:自身已生成但其儿子还没有全部生成的节点称做活结点
死结点:一个所有儿子已经产生的结点称做死结点
生成问题状态的基本方法
深度优先的问题状态生成法：对一个扩展结点R，一旦产生了它
的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为
根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R
的下一个儿子（如果存在）
宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，
它一直是扩展结点。

为了提高搜索效率，在搜索过程中，可使用剪枝函数,剪去
那些不必要搜索的子树，减少问题求解所需实际生成的状态结
点树。
l常用的剪枝函数
l 约束函数:剪去那些已知不含答案状态的子树
l 限界函数:剪去那些不可能包含最优答案结点的子树

例：n=3时 w=[2,4,3]，p=[5,10,3]
背包容量M=5

在这里插入图片描述
约束函数如何定义?
设Y是状态空间树中的一个问题状态，从根到Y的一条路径
代表正在构造中的n元组的一部分(x0
,x1…xk
),可称之为部分向量.
约束函数是关于部分向量的函数Bk
(x0
,x1…xk
),它被定义为:
如果可以断定Y的子树上不含任何答案状态,则Bk
(x0
,x1…xk
)为
false,否则为true.

回溯法：深度优先生成结点,并使用剪枝函数的求解方法.
•分枝限界法:广度优先生成结点，并使用剪枝函数的方法

针对所给问题，定义问题的解空间；
(2)确定易于搜索的解空间结构，并构造判定函数；
(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数
避免无效搜索

在这里插入图片描述
递归回溯法

void RBacktrack (int k)
{
for(每个x[k],使得x[k]∈T(x[0],x[1]…x[k-1])&& (Bk
(x[0],x[1]…x[k])))
{
if((x[0],x[1]…x[k])是一个可行解)
输出x[0],x[1]…x[k]；
else
RBacktrack(k+1);
}
}

迭代回溯法

void IBacktrack (int n)
{ int k=0;
while(k>=0)
{
if(还有尚未检测的x[k]∈T(x[0],x[1]…x[k-1])&& (Bk
(x[0],x[1]…x[k]))
{
if((x[0],x[1]…x[k])是一个可行解)
输出x[0],x[1]…x[k]；
k++;
}
else
k--;
}
}