回溯法与分枝—限界法的区别以及分支限界法分类以及LC学习

简介: 回溯法与分枝—限界法的区别以及分支限界法分类以及LC学习

区别


首先理解什么是状态空间树。

状态空间树:是指解空间的树结构

在状态空间树生成过程中有3类结点:活结点、E-结点、死结点

回溯法与分支限界法的区别主要在于:构造状态空间树的过程不一样。

回溯法是利用深度优先搜索构造,分支限界法是用广度优先搜索构造。

1685019353112.jpg


分类


接下来了解分支限界法。

可以利用队列或栈来导出分支限界法,所以依次分支限界法可以分为FIFO(队列)检索、LIFO(栈)检索

但两种扩充结点的方法过于呆板,导致偏向于正确答案的结点没有优先权。

分支限界法是扩展完一个E-结点所有儿子后再找一个结点作为E-结点扩展,上面两种扩展过于呆板,那是不是可以选择代价最小的结点的作为下一个E-结点进行拓展?

可以,这就是LC(least cost )检索的分支限界法。


LC分支限界法


LC分支限界法:选用一个成本函数C来标识结点成本,选择最小代价结点作为下一个E-结点:初始:C定义为结点x到目标答案结点的步数,但这个问题是要已知目标答案,所以不能这么精确.然后用g’来估计x到答案结点的代价,但是又会造成纵深检索;最后引入h函数表示根结点到x结点的位置减少纵深检索。

C’=f(h(x))+g’(x)

LC检索分支限界法流程:

1685019374623.jpg

当有多个答案是是否LC算法能够最小成本答案?

否,除非保证C(X)<C(Y),有C’(X)<C’(Y),或者保证C’(X)<=C(X)而且对答案结点有两种成本函数相等。


LC分支限界法应用


1. 15迷问题

1685019388939.jpg

首先先判断是否可达!

首先按照目标状态给棋盘方格编号,得出position(i)代表初始状态下标号i所在位置的棋盘编号,空格位置用16代替。

记录less(i)函数(编号比i小但是初始位置在position(i)之后的数字数目)

若less(i)累加+x(空格是否在偶数位(不考虑目标状态的偶数位),偶1,奇0)为偶数,可达!


LC算法:g’(x):该结点与目标状态的差距=不在其目标位置的非空白牌数目(精髓)


成本函数的上界的作用和定义:求答案的最小成本,过滤,初始为无穷


2.带期限的作业排序问题

1685019398350.jpg

按编号选取作业

g’(x)为已经考虑过但不在j集合的罚款数目

这里c’=g’.

1685019410952.jpg

相关文章
|
6月前
|
存储 算法 程序员
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
57 0
|
5月前
|
算法
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法:单词接龙、最小基因变化、二进制矩阵中的最短路径
|
6月前
|
算法 测试技术 C#
【树 图论 阶乘 组合 深度优先搜索】1916. 统计为蚁群构筑房间的不同顺序
【树 图论 阶乘 组合 深度优先搜索】1916. 统计为蚁群构筑房间的不同顺序
|
存储 算法 Java
数据结构与算法的关系(上):算法的特征
算法定义:描述解决问题的方法。这个描述很笼统,很多人一听可能迷迷糊糊的,不明所以。我们来看看其他的定义:算法是解题方案的准确而完整地描述,是一系列解决问题的清晰指令,并且每个操作表示一个或多个指令。这个定义是被普遍认可的,在计算机中,算法就一个多个制定的一序列的指令。
202 0
数据结构与算法的关系(上):算法的特征
|
存储 算法 Python
秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为W。一种物品要么全部装入背包,要么全部不装入背包,不允许部分装入。装入背包的物品的总重量不超过背包的容量。问应如何选择装入背包的物品,使得装入背包中的物品总价值最大?
614 0
秒懂算法 | 子集树模型——0-1背包问题的回溯算法及动态规划改进
|
算法
算法设计与分析/数据结构与算法实验4:添加括号数目问题
算法设计与分析/数据结构与算法实验4:添加括号数目问题
182 0
算法设计与分析/数据结构与算法实验4:添加括号数目问题
|
算法
Day24——组合(回溯算法)
Day24——组合(回溯算法)
101 0
Day24——组合(回溯算法)
【每日一题Day29】LC775全局倒置与局部倒置 | 树状数组 数学
给你一个长度为 n 的整数数组 nums ,表示由范围 [0, n - 1] 内所有整数组成的一个排列。
68 0
|
算法
【每日一题Day38】LC882细分图中的可到达节点 | 图论
给你一个无向图(原始图),图中有 n 个节点,编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。
101 0
LeetCode每日一题——698. 划分为k个相等的子集
给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。
121 0