回溯法与分枝—限界法的区别以及分支限界法分类以及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

相关文章
|
12月前
|
Rust 前端开发 JavaScript
前端技术新探索:从React到WebAssembly的高效之路
前端技术新探索:从React到WebAssembly的高效之路
337 2
|
存储 算法 Java
【DFS(深度优先搜索)详解】看这一篇就够啦
本文介绍了深度优先搜索(DFS)算法及其应用。DFS从某个顶点出发,深入探索图的每条路径,直到无法前进为止,然后回溯。文章详细解释了DFS的基本思想,并通过示例图展示了其执行过程。此外,文中还探讨了三种枚举方式:指数型枚举、排列型枚举和组合型枚举,并提供了具体的代码实现。最后,文章通过几道练习题帮助读者更好地理解和应用DFS算法。
8801 19
【DFS(深度优先搜索)详解】看这一篇就够啦
|
12月前
|
存储 Java 索引
Java LinkedList详解
`LinkedList`是Java集合框架中的一个重要类,实现了`List`、`Deque`和`Cloneable`接口。它基于双向链表,支持动态扩展,允许重复元素。虽然通过索引访问元素的时间复杂度为O(n),但在插入和删除操作上表现优异,时间复杂度为O(1)。常用操作包括创建、添加、获取、删除和查找元素,以及使用迭代器遍历。适用于频繁插入和删除的场景,如队列和栈的实现。
408 7
|
运维 关系型数据库 网络安全
宝塔面板忘记了登录用户名密码怎么办?
当忘记宝塔面板的用户名或密码,可通过以下方法解决: 1. 登录后台修改:访问面板设置-&gt;面板用户,输入新用户名和密码。 2. 使用SSH连接服务器,输入`bt`命令选择相应选项(5修改密码,6修改用户名)。 3. Windows用户可在CMD输入`bt`同样操作。
1248 0
 宝塔面板忘记了登录用户名密码怎么办?
|
IDE Java 开发工具
python缩进错误(IndentationError)
【7月更文挑战第12天】
2146 10
BERT+PET方式模型训练(二)
• 本项目中完成BERT+PET模型搭建、训练及应用的步骤如下(注意:因为本项目中使用的是BERT预训练模型,所以直接加载即可,无需重复搭建模型架构): • 一、实现模型工具类函数 • 二、实现模型训练函数,验证函数 • 三、实现模型预测函数
|
存储 Java 关系型数据库
基于JSP的二手交易平台网站
基于JSP的二手交易平台网站
|
算法 测试技术 编译器
【算法】优先队列式分支限界法,以01背包问题为例
📑 例题:01背包问题 题目链接:采药-洛谷 当洛谷上不让下载测试用例,可以试试:采药-ACWing
1593 0
|
JSON Shell Linux
Shell获得Curl命令返回的json值
使用curl命令,获取solr中query的结果笔数 Linux中Shell获得json中的值
349 0
|
缓存 NoSQL 关系型数据库
Redis与MySQL的数据情感:延迟双删的秘密揭示
Redis与MySQL的数据情感:延迟双删的秘密揭示
987 0