回溯法

将解空间看做树形结构,即状态空间树。进行深度优先遍历+跳跃式搜素。不满足约束条件的截枝并且回溯父节点。逐步建立和修改子集树(排列树)的过程--“走不通回头”。
适合求解:组合数较大的问题。1、搜索问题:在搜索空间找一个或全部可行解(n皇后问题、图的m着色问题和装载问题等)
2、组合优化问题找该问题的一个或全部最优解[贪心法(最优子结构和最优亮度标准)、动态规划法(最优子结构)](背包问题,子集和树问题和货郎问题等)

解空间:

问题候选解的集合,表示为一n元组(x1,x2,...xn)

状态空间树&显式约束

状态空间树:

  • 用树形表示解空间,无需事先生成。

  • 每一个节点对应一个 问题状态

  • 从根节点到叶节点,每条路径对应一个候选解的n-元组。叶结点叫 解状态

  • 从根状态到某个解状态的路径代表一个可行解的n-元组,则称该解状态为答案状态

  • 对于组合优化问题时,必须使用目标函数衡量每一个答案结点,从中找出使目标函数取得最优值的最优答案状态

    状态空间树

两类状态空间树:

  • 子集树:遍历时间为O(2^n)
  • 排列树:遍历时间O(n!)

显式约束

  • 规定了每个分量的范围,规定待求解问题的所有可能的候选解,决定状态空间树的规模。(在问题描述中直接获得)
隐式约束&判定函数

隐式约束

  • 判定候选解是否可行的条件。

判定函数

  • 从隐式约束出发,设计判定函数使当且仅当函数为真时,n-元组是问题实例的满足
    隐式约束的一个可行解。(候选解是否可行)
最优解&目标函数

最优解

  • 不是唯一的

目标函数 / 代价函数

  • 衡量每个可行解的优劣
  • 组合优化问题的最优解是使用目标函数取极值(最大、最小)的一个或多个可行解。
部分向量&约束函数

部分解向量

  • 每一个结点对应一个部分解向量。
  • 每个叶子节点对应一个候选解。

约束函数

  • 源自问题的约束条件。
  • 结点Y是状态空间树中的一个问题状态,从根结点到Y的一条路径代表正在构造中的k元组,是解的一部分,称为部分向量。关于部分向量的函数Bk(x0,x1,x2...x(k-1))有满足或不确定的为true,没有为false则将子树剪掉。
    (排序问题一般不用回溯法求解,用回溯法排列时间复杂度为O(n!),内排序算法快排归并排序的时间复杂度为O(nlogn)或冒泡排序O(n²))
搜索策略&剪枝函数

搜索策略

  • 三类策略
    1、深度优先,
    2、广度优先,
    3、函数优先,宽深结合

但使用1或2的搜索法属于蛮力算法或穷举法,搜索效率较为低下。

剪枝函数

  • 提高搜索效率
    1、跳跃式搜索(隐含遍历)、
    2、剪去不必要的搜索子树

  • 两类剪枝函数
    1、约束函数

    • 源自带球解问题的隐式约束条件,即关于部分向量的函数Bk。
    • 避免搜索不可能包含答案状态的子树

    2、限界函数
    对于组合优化问题(搜索问题涉及不到)要找最优解而不是可行解,避免搜索不可能包含最优答案结点的子树。

回溯法VS分支限界法
两者对比

image.png

\color{#6739b6} {{\textbf{回溯法使用条件??}}}
是否满足多米诺性质

判断多米诺性质是否存在即为证明:前真后真

可通过变换变得符合多米诺性质,求解后再换回原式

回溯法的效率估计

方法:蒙特卡洛法(计算搜索树中平均遍历的结点数)

基本思想

选择路径:
1、从根开始,随机选择一条路径,直到不能分支为止(叶子结点或被截枝的节点[约束函数/限界函数]),即从x1,x2,,依次对xi赋值,每个xi的值是从当时的Si中随机选择,直到向量不能扩张为止。
2、假定搜索树中其他|si|-1个分支与上述随机选出的路径一样,计算搜索树的结点数。
3、重复步骤1、2将结点进行概率平均。

装载问题(组合优化问题)

只需要考虑如何装能使第一艘船装到最满。


计算过程

用回溯法设计解装载问题的O(2^n)计算时间算法,在某些情况下优于动态规划算法。

0/1背包问题(组合优化问题)

(贪心法、动态规划法、图解法、回溯法)
问题描述

背包问题概述

算法设计
单位价值大优先,构造更小的r(i)

回溯法运用贪心策略,减小r(i),提高剪枝概率。
算法时间复杂度为O( 2^(n+1) )。


算法分析

n-皇后问题(组合问题)

问题描述

算法设计

算法设计

图m着色问题(组合问题)

问题描述

对于可着色优化问题经验证明最多四种。
这里我们只考虑着色组合问题


image.png

可使用邻接矩阵或邻接表
1:红;2:蓝;3,黑。总共有6个可行解

image.png

指数,复杂度非常高

子集和数问题

问题描述

算法设计,约束条件:隐式约束<=M。可变效率更高

image.png
image.png

image.png

TSP(旅行商问题,货郎问题)(组合优化极小化)

巡回路线表示为无向连通图--哈密顿回路
算法设计,列出两两不相同是排列树;不需要隐式约束剪枝,只用限界函数剪枝。

回溯法求作业调度问题

TSP问题的回溯算法

哈密顿环问题

问题描述

算法分析,子集树,TSP种两个城市之间肯定有边,不用考虑,而哈密顿环问题需要考虑。和求解图的m可着色判定问题相似,时间复杂度差不多

image.png

image.png

image.png

TSP问题要求为完全图,而哈密顿环没有要求完全图

回溯算法效率的影响因素以及改进途径:

n皇后问题--解空间对称性

image.png

影响因素:

1.搜索树的结构:

  • 分支情况(分支是否均匀)
  • 树的深度(1/3解空间)
  • 对称程度 (对称适合裁剪)
    2.解的分布:
  • 在不同子树中,分布多少,是否均匀。
  • 分布深度
    3.约束条件判断:计算简单

改进途径
1.根据树分支设计改进策略

  • 结点少的分支优先
  • 解多的分支优先
    2.利用搜索树对称性裁剪子树
    3.分解为子问题
  • 分解时间f(n)=c2^n,组合时间T=O(f(n))
  • 如果分解为k个子问题,每个子问题大小为n/k则求解时间为
    image.png

    实际缩短了程序运行的时间,理论上时间复杂度还是原来的2^n

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 深度优先搜索 + 剪枝。回溯法的求解目标一般是找出解空间树中满足约束条件的所有解。 # 在学习回溯和分支限界法之前...
    Tenloy阅读 2,972评论 0 3
  • 回溯法与分支限界法 时间 2016-03-24 标签 搜索 回溯法 1、概念 回溯算法实际上一个类似枚举的搜索尝...
    wangchuang2017阅读 2,358评论 0 4
  • https://www.cnblogs.com/zeng-/p/4911644.html 一、基本描述 类似于回溯...
    麒麟楚庄王阅读 797评论 0 0
  • 一、基本概念   回溯法,又称为试探法,按选优条件向前不断搜索,以达到目标。但是当探索到某一步时,如果发现原先选择...
    大雄的学习人生阅读 1,216评论 1 3
  • “砰!”一声巨响,我扭头一看,一把雨伞掉落在一辆急停的出租车前,我并没有看到它的主人。出租车司机和车上的乘客匆忙下...
    籽绫阅读 372评论 1 0