算法进阶之回溯算法

你的名字 2022-06-08 11:17 204阅读 0赞

# 回溯算法 #

**1  什么是回溯法**

回溯法实际是穷举算法，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。回溯法有“通用的解题法”之称，其采用了一种“走不通就掉头”思想作为其控制结构，用它可以求出问题的所有解和任意解。

它的应用很广泛，很多算法都用到回溯法，例如，迷宫，八皇后问题，图的m着色总是等都用到回溯法，当然其中还使用了其他策略。

**2  解的表示**

**      **

**         回溯法搜索一条路径，这条路径的节点都满足约束条件。**

**         既然，回溯法搜索的是路径， 因此可用数组 A\[0,1,2，。。。，*N-1*\]  表示。 其中A【i】 表示 第i个节点的取值。**

**3  基本思想**

回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间（一般为树结构空间）。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。

运用回溯法解题通常包含以下三个步骤：

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索；

**     算法的关键是 判断节点 （i,j） 是否为解路径上的节点，其判断方法如下所示：**

<table style="width:923px; background:#fabf8f; height:1088px"> 
 <tbody> 
 <tr> 
 <td> // 判断节点（I,j）是否为解路径上的节点,其中： //&nbsp;&nbsp; // &nbsp;&nbsp;i表示解路径上的第i个测试节点、j表示该节点的某个候选值 //&nbsp; &nbsp;A[i] 保存第i个节点选用的值 &nbsp; BOOL TestNode(I ,j) { &nbsp;&nbsp; 与0—(i-1) 层进行判断，看是否与以遍历的节点有冲突 &nbsp;&nbsp; &nbsp;&nbsp; 若有冲突， 则返回FALSE； &nbsp;&nbsp; 若无冲突， 则 将节点i的值j,保存到对应的数组中A[I]=J; &nbsp; &nbsp;&nbsp; 判断I是否为最后一层, 若是最后一层，则成功找到一条解路径，返回TRUE； &nbsp; 若不是最后一层，则判断第i+1层是否有正确的节点。 &nbsp; &nbsp;&nbsp; BOOL bFlag=FALSE; &nbsp;&nbsp; FOR(k=0;k&lt;CANDIDATE_NUM;k++) //候选值【0，。。。，CANDIDATE_NUM-1】 &nbsp;&nbsp; { &nbsp;&nbsp;&nbsp;&nbsp; If(TestNode(i+1,k)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 找到一个解； &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bFlag=True; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; } &nbsp; } &nbsp;&nbsp; &nbsp;&nbsp; RETURN bFlag; &nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

**4  算法伪代码**

** **

**1） 求解单个解**

<table style="width:885px; background:#c6d9f1; height:1303px"> 
 <tbody> 
 <tr> 
 <td> &nbsp; &nbsp; // 该函数用来测试 节点i是否是解路径上的节点 BOOL&nbsp; TestNode(int i,int j){ &nbsp; 
 <blockquote style="margin-right:0px"> 
 //与之前的0 —（i-1）层的值做比较，看看有无冲突 
 </blockquote> &nbsp; 
 <blockquote style="margin-right:0px"> 
 FOR(int k=0;k&lt;I;k++) 
 { 
 &nbsp;&nbsp; If(有冲突) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Return &nbsp;FALSE;&nbsp; //此节点为死节点，不在解路径上 
 } 
 </blockquote> &nbsp; 
 <blockquote style="margin-right:0px"> 
 //与之前的都无冲突,则选定此候选值 
 A[i]=j; 
 </blockquote> &nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp; //判断第i层是否为最后一层,若是最后一层，则成功找到一个解 &nbsp;&nbsp;&nbsp; If(i==NUM-1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Retrun TRUE; &nbsp; &nbsp;&nbsp; &nbsp;//若不是最后一层，则判断第 i+1层上&nbsp; 有无解路径上的节点 &nbsp; 
 <blockquote style="margin-right:0px"> 
 BOOL bFlag=FALSE; 
 </blockquote> &nbsp;&nbsp;&nbsp;&nbsp; FOR(int k=0;k&lt;CANDIDATA_NUM;k++) 
 <blockquote style="margin-right:0px"> 
 { 
 <blockquote style="margin-right:0px"> 
 &nbsp;&nbsp; If(TestNode(i+1,k)) 
 { 
 &nbsp;&nbsp; bFlag=TRUE; 
 &nbsp;&nbsp; Break;&nbsp;&nbsp; // 找到一个解 
 &nbsp; 
 } 
 </blockquote> 
 } 
 </blockquote> &nbsp; 
 <blockquote style="margin-right:0px"> 
 Return bFlag; //返回这个节点的信息&nbsp; 是否位于解路径上 
 </blockquote> &nbsp; } </td> 
 </tr> 
 </tbody> 
</table>

<table style="width:884px; background:#c6d9f1; height:603px"> 
 <tbody> 
 <tr> 
 <td> &nbsp; &nbsp;&nbsp; BOOL bExist=FALSE;&nbsp; // 是否存在解 &nbsp; &nbsp;&nbsp; //从最初节点 开始判断 &nbsp;&nbsp; For(int j=0;j&lt;CANDIDATA_NUM;j++) { 
 <blockquote style="margin-right:0px"> 
 &nbsp; IF(TestNode(0,j)) 
 &nbsp; { 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bExist=TRUE; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; break;&nbsp; // 找到一个解后，便退出 ，不再找其他解 
 &nbsp; }&nbsp;&nbsp;&nbsp; 
 </blockquote> } &nbsp; Return bExist; &nbsp; &nbsp; </td> 
 </tr> 
 </tbody> 
</table>

**2）所有解**

全局变量：

<table style="width:890px; background:#c6d9f1; height:175px"> 
 <tbody> 
 <tr> 
 <td> #define &nbsp;NUM&nbsp; 8&nbsp;&nbsp;&nbsp; //候选值 与 节点个数均为8 Extern int A[NUM];&nbsp; //保存一个解路径 Extern std::&lt;int&gt; OneResult; // 保存一个解路径 Extern std::&lt;std::vector&lt;int&gt;&gt; AllResult; &nbsp;//保存所有的解路径 </td> 
 </tr> 
 </tbody> 
</table>

<table style="width:897px; background:#f2dbdb; height:1705px"> 
 <tbody> 
 <tr> 
 <td> &nbsp; &nbsp; // 该函数用来测试 节点i是否是解路径上的节点 BOOL&nbsp; TestNode(int i,int j){ &nbsp; 
 <blockquote style="margin-right:0px"> 
 //与之前的0 —（i-1）层的值做比较，看看有无冲突 
 &nbsp; 
 FOR(int k=0;k&lt;I;k++) 
 { 
 &nbsp;&nbsp; If(有冲突) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Return &nbsp;FALSE;&nbsp; //此节点为死节点，不在解路径上 
 } 
 &nbsp; 
 //与之前的都无冲突,则选定此候选值 
 A[i]=j; 
 </blockquote> &nbsp; 
 <table style="width:897px; background:#b6dde8; height:490px"> 
 <tbody> 
 <tr> 
 <td> 
 <blockquote style="margin-right:0px"> 
 //判断第i层是否为最后一层,若是最后一层，则成功找到一个解，将此解添加到容器中 
 &nbsp;&nbsp; If(i==NUM-1) 
 { 
 &nbsp;&nbsp;&nbsp; OneResult.clear(); 
 &nbsp;&nbsp;&nbsp; For(int k=0;k&lt;NUM;k++) 
 &nbsp;&nbsp;&nbsp; &nbsp;&nbsp; &nbsp;OneResult.push_back(A[k]); 
 &nbsp;&nbsp;&nbsp; 
 //将本次结果保存到容器中 
 &nbsp;&nbsp;&nbsp; AllResult.push_back(OneResult); 
 &nbsp; 
 &nbsp;&nbsp;&nbsp;Retrun TRUE; 
 } 
 &nbsp; 
 </blockquote> </td> 
 </tr> 
 </tbody> 
 </table> &nbsp; &nbsp; 
 <blockquote style="margin-right:0px"> 
 &nbsp;//若不是最后一层，则判断第 i+1层上&nbsp; 有无解路径上的节点 
 </blockquote> &nbsp; 
 <blockquote style="margin-right:0px"> 
 BOOL bFlag=FALSE; 
 FOR(int k=0;k&lt;CANDIDATA_NUM;k++) 
 { 
 <blockquote style="margin-right:0px"> 
 &nbsp;&nbsp; If(TestNode(i+1,k)) 
 { 
 &nbsp;&nbsp;&nbsp; &nbsp;bFlag=TRUE; 
 &nbsp;&nbsp;&nbsp; &nbsp;// Break;&nbsp;&nbsp;//找到一个解&nbsp;找到解后，不退出，再接着尝试下一个候选值&nbsp; 
 } 
 </blockquote> 
 }&nbsp; 
 Return bFlag; //返回这个节点的信息&nbsp; 是否位于解路径上 
 </blockquote> } </td> 
 </tr> 
 </tbody> 
</table>

<table style="width:899px; background:#f2dbdb; height:603px"> 
 <tbody> 
 <tr> 
 <td> &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; BOOL bExist=FALSE;&nbsp; // 是否存在解 &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; //从最初层 开始判断 &nbsp;&nbsp;&nbsp;&nbsp; &nbsp;For(int j=0;j&lt;CANDIDATA_NUM;j++) &nbsp;&nbsp;&nbsp; { 
 <blockquote style="margin-right:0px"> 
 &nbsp; IF(TestNode(0,j)) 
 &nbsp; { 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bExist=TRUE; 
 &nbsp;&nbsp;&nbsp; &nbsp;// break;&nbsp;不退出，接着寻找下一个解 
 &nbsp; }&nbsp; 
 </blockquote> &nbsp;&nbsp; } &nbsp; Return bExist; &nbsp; &nbsp; </td> 
 </tr> 
 </tbody> 
</table>