本文共 2843 字，大约阅读时间需要 9 分钟。

一、前言

• 寻找问题的解的一种可靠的方法：
  • 是首先列出所有候选解，然后逐个，在检查完所有或部分候选解之后，即可找到所需要的解
  • 理论上，只要候选解数量有限，并且在检查了所有或部分候选解之后可以确定所需解。
• 这种方法是可行的。不过在实际应用中，很少使用这种方法， 因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机，也只能对实例规模相当小的问题在合理的时间内解决
• 对候选解进行系统检查的方法有多种，其中“回溯”和“分支定界法”是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大 的问题。
• 本文阐述回溯方法，分支定界在后面几篇文章介绍

二、回溯算法概述

• 回溯法是搜索问题解的一种系统方法

解决问题的步骤

• 第一步：设定解空间，这个空间至少包含问题的一个（最优的）解。
• 第二步：组织解空间，使解空间便于搜索，典型的组织方法是图或树
• 第三步：一旦确定了空间的组织方法，便可以对这个空间进行遍历。搜索过程中一些方法与术语为：
  • 开始节点即是一个活动节点又是一个E-节点
  • 从E-节点我们试着移到一个新节点
  • 如果从当前的E-节点移到一个新节点，那么这个新节点就变成一个活动节点和新的E-节点。而原来的E-节点仍是一个活动节点
  • 如果不能移到一个新节点，那么当前E-节点“死掉”，即不再是活动节点。然后我们回到最近的活动节点。这个活动节点变成了新的E-节点。当我们已经找到了答案或者不再有活动节点时，搜索过程结束

三、实际应用之迷宫老鼠

问题描述

• 在一个矩阵迷宫中，从一个起点开始逐个进行前进与后退，最终找到重点

回溯方法解决

• 第一步：设定解空间这个空间至少包含问题的一个（最优的）解。在这个案例中，我们可以把从入口到出口的所有路径定义为解空间
• 第二步：组织解空间，使解空间便于搜索，典型的组织方法是图或树。在本案例中使用的是图，如下图所示

• 第三步：一旦确定了空间的组织方法，便可以对这个空间进行遍历。在此案例中使用深度优先方式进行遍历，假设在此案例中我们的初始化解空间如图a)所示，那么步骤如下：
  • 从(1,1)开始，它是此时唯一的活动节点，它也是一个E-节点，为了避免重复揍过这个位置，置maze(1,1)为1
  • 然后从(1,1)开始移动，这一点可以到达(1,2)或(2,1)两个点。我们假设先移动到(1,2)，然后置(1,2)为1。此时迷宫如下图b)所示
  • 这时我们有两个活动节点(1,1)和(1,2)。(1,2)成为了E-节点，此时有三个地方可以移动，但是唯一可以走的是(1,3)，因此移动到(1,3)，并置mzae(1,3)为1，此时迷宫如下图c)所示
  • 但是(1,3)这个节点没有新的节点可以继续走了，那么就回溯到(1,2)，但是这个节点也没有地方可以走了，那么回溯到(1,1)，此时继续移动，移动到(2,1)，然后移动到(3,1)，(3,2)，(3,3)，最终找到终点

四、实际应用之0/背包问题

问题概述

• 有n个物品和一个容量为c的背包。物品i的重量为Wi，价值为p。现在要从n个物品中选出一些物品装入书包中
• 现在的最佳要求是：在装包的物品总重量不超过背包的容量下，使装入的物品总价值最高
• 问题描述是：

• 约束条件是：

• Xi=1表示物品装入背包，Xi=0表示物品没有装入背包

回溯方法解决

• 第一步：设定解空间这个空间至少包含问题的一个（最优的）解。在这个案例中，我们把个长度为n的0/向量的集合定义为解空间。本案例中n=3，因此解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,1,0)}
• 第二步：组织解空间，使解空间便于搜索，典型的组织方法是图或树。在本案例中使用的是树，如下图所示

• 第三步：一旦确定了空间的组织方法，便可以对这个空间进行遍历
  • 假设本案例中，n=3，w=[20,15,15]，p=[40,25,25]，c=30
  • 在此案例中使用深度优先方式进行遍历，步骤如下：
    • 从根节点开始，此时我们能移动到B或C。假设移动到B，此时剩余容量r=10，收益cp=40；从B到D或E可行，但是移动到D不行，因为移动到D所需的容量w2=15；移动到E是可行的，因为这个移动不占用任何容量；E变为新的E-节点，这是活动节点为A、B、E。在节点E，r=10，cp=40，我们从E可以移动到J或K，但是J不行，移动到K可以；那么移动到K，其是一个叶节点，所以得到一个可行解，这个解的收益cp=40。那么此次遍历的路径为（A、B、E、K）
    • 因为K是叶节点不可以继续遍历，所以其死亡了；所以我们回溯到B，由于B也死亡了，那么回溯到A，此时可以继续移动到C，此时r=30，cp=0；从C可以达到F或G，假设移动到F，F变为新的E-节点，活动节点为A、C、F；在F点，r=15，cp=25。从F可以到达L或M；假设移动到L，此时r=0，cp=50。既然L是一个叶节点，而且它代表了一个比目前最优解（即在节点K的解）更好的可行解，我们把这个解作为最优解
    • 节点L死亡，我们回溯到F....以此类推，遍历完整棵树，在遍历的过程中找到最优解

五、实际应用之旅行商问题

待续

六、相关术语

子集树、排列树

• 当问题需要n个元素的一个子集来优化函数时，解空间树称为子集树。对n个对象的0/1背包问题来说，解空间树便是一个子集树。这样的一棵树有个叶节点，全部节点有个。因此，访问树中所有节点的每一个算法都要耗时
• 当问题需要n个元素的一个排列来优化函数时，解空间树称为排列树。这样的数有n!个叶节点。遍历树中所有节点的每一个算法都要耗时。上图的树便是，寻找顶点{2，3，4}的最佳排列时的树。顶点1是履行的起点和终点

界定函数

• 确定一个新到达的节点能够导致一个比当前最优解还要好的解，可加速最优解的搜索过程。如果不能，则移动到该节点的任何一颗子树都是无意义的。这个节点可被立即杀死。用来杀死活动节点的策略称为界定函数
• 在上面的0/背包问题中，我们使用了如下界定函数：杀死那些代表不可行解的节点
• 对于旅行商问题，可使用这样的界定函数：如果到达当前节点的一段旅行的耗费不少于当前最佳路径的耗费，则杀死当前节点。如果在旅行商问题的“四顶点网格”图案例中使用该界定函数，那么当达到上图的节点I时，已经找到了具有耗费25的1，3，2，4，1的履行。而到达节点I的一段旅行（1，3，4）的耗费为26.若继续这段旅行，则不会得到一个耗费小于25的结果。因此，搜索以I为根节点的子树毫无意义

七、编码案例（货箱装载）

• 待续

八、编码案例（0/1背包问题）

• 待续

九、编码案例（最大完备子图）

• 待续

十、编码案例（旅行商问题）

• 待续

十一、编码案例（电路板排列）

• 待续

转载地址：https://dongshao.blog.csdn.net/article/details/105814315 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！