搜索
查看
编辑修改
首页
UNITY
NODEJS
PYTHON
AI
GIT
PHP
GO
CEF3
JAVA
HTML
CSS
搜索
Gausst松鼠会
这个屌丝很懒,什么也没留下!
关注作者
热门标签
jquery
HTML
CSS
PHP
ASP
PYTHON
GO
AI
C
C++
C#
PHOTOSHOP
UNITY
iOS
android
vue
xml
爬虫
SEO
LINUX
WINDOWS
JAVA
MFC
CEF3
CAD
NODEJS
GIT
Pyppeteer
article
热门文章
1
【网站项目】农业信息管理系统
2
量化敏感层分析Quantization-Aware-Training(QAT)_quantization aware training
3
Java开发面试--RabbitMQ专区_java简历项目经验中的rabbitmq该怎么写
4
BUUCTF:[羊城杯 2020]image_rar
5
CentOS7下安装Hadoop伪分布式_centos7 进行hadoop伪分布式安装
6
python实现双向最大匹配法_双向最大匹配算法 python
7
YOLOV4用到的一些tricks以及代码实现(2)——CIou_Loss
8
初探信息科学中“三个世界”模型_信息的三种世界是什么?彼此之间有什么联系?
9
解决:宿主机无法访问linux下docker容器中的服务_linux 服务器存在监听 docker 不能访问
10
app自动化:python + appium_python+appium自动化
当前位置:
article
> 正文
问题归约及与或图搜索
作者:Gausst松鼠会 | 2024-04-07 12:23:14
赞
踩
与或图搜索
问题归约
图片来自西安电子科技大学课件
定义
将问题通过分解和等价变换的化简,将之变为若干可解的子问题
分解
将复杂问题分解成若干简单可解决,可实现的步骤
一步一步成立,结果成立。故用逻辑与连接,是原命题的成立条件
与或树表达
等价变化
利用同构或者是同态,将原问题变为若干较为容易求解的原问题
只要有一种成立就成立,用逻辑或连接,彼此互为等价
与或树表达
归约例题
通过有序对的方式将问题进行有效的描述,确定问题的初始态(1,1,1),确定问题的目标态(3,3,3)
将三圆盘的移动问题,分解成两元盘的移动问题和一圆盘移动问题,即两元盘由(1,1,1)变为(1,2,2),单元盘由1移动到3.
进一步对问题进行分解,将两元盘问题分解成一圆盘问题。
生成对应的与或树,由初始态到目标态,分解成三个步骤。彼此之间必须要用与连接,互为分解条件。最后全部化为单元盘移动的本原问题。
与或图的结构
一般的,我们用与或图将问题归约为后继问题的替换集合
解决A问题可以分解成B,C,D若干个可实现步骤,则用与图连接
解决A问题可以用B问题,或者C问题来代替,即解答了B或C,相当于解答了A,则用或图连接
可解
可解条件
终叶节点是可解节点
所有或节点只要有一个可解,对应的父节点可解
所有与节点都可解,其对应的父节点才可解
可解标志:证明某个节点可解,必须通过递归可推出当前节点可解
不可解
不可解条件:
无后继节点的非叶子节点(对应的叶子节点不可解)
所有或节点全都不可解,对应的父节点不可解
所有的与节点只要有一个不可解,对应的父节点不可解
不可解标志:证明某个节点不可解,通过递归退出某个节点不可解
与或图搜索——宽度搜索
根本思路:在常见的宽度搜索的基础上,增加回溯,通过可解标志和不可解标志判定初始节点是否可解。
可解节点留下,作为解的一部分;不可解节点删除,不作为树的一部分
与或图搜索——深度搜索
在原先深度搜索的基础上不改变,每一次增加节点的同时都通过回溯判定根节点是否可解
深度优先,将扩展结点放在OPEN表前端,先访问
OPEN表中承载着带访问的节点;CLOSE表中承载着可解节点,将作为最终解得的与或树的节点
声明:
本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:
https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/378571
推荐阅读
article
买
了一个
腾讯
云
轻量
服务器
要怎么去操作?_
购
买
的
免费
的
腾讯
云
轻型
服务器
如何使用...
购
买
后去
腾讯
云
服务器
“站内信”里面找到自己
购
买
服务器
的
初始账号,初始密码,公网ip,保存,待会登陆要用。不要选择高级版本...
赞
踩
article
计算机
毕业设计
面向金融领域的
实体
关系
抽取
系统
(源码+论文)_
关系
抽取
软件
源代码
...
面向金融领域的
实体
关系
抽取
系统
主要包含两部分,模型训练和
关系
抽取
,
关系
抽取
是应用模型训练完成后保存的模型来进行
关系
抽取
活...
赞
踩
article
国产化
(三):
中间件
——
东方
通
TongWeb7.0
_
东方
通
中间件
...
麒麟kylin系统安装
东方
通
TongWeb7.0
_
东方
通
中间件
东方
通
中间件
一、准备工作 1、软...
赞
踩
article
基于
AI
Agent
探讨:
安全
领域下的
AI
应用范式_
ai
agent
安全
运营...
关于
AI
应用,通常都会聊准召。但在
安全
等模糊标准的场景下,事实上不存在准召的定义。因此,
AI
的目标应该是尽可能的“像人”...
赞
踩
article
什么
是
自然语言
处理
(
NLP
)?
定义
+应用一次性看个明白_nlp
定义
...
不懂什么
是
自然语言
处理
?它在商业智能中又有哪些应用?带着这样的疑问,慧都网将从
定义
和应用两个方向,通过3分钟的时间快速了...
赞
踩
article
Transformer
、
BERT
和
GPT
自然语言处理领域的重要模型_
transformers
be...
由于篇幅有限,无法提供详细的代码示例。但是,可以查阅相关的开源库和教程来获取具体的实现细节和示例代码。常用的深度学习框架...
赞
踩
article
CSDN
文章
撰写
格式
_
怎样写
csdn
那样
格式
的
文章
...
一级标题一般是总概括性的内容属于当前一级标题的二级标题,细化内容属于当前二级标题的三级标题,细化内容,
CSDN
目录不显示...
赞
踩
article
Vscode
中的
setting
s.
json
_
vscode
设置
setting
.
json
不加分
号...
【代码】
Vscode
中的
setting
s.
json
。_
vscode
设置
setting
.
json
不加分
号
vscode
设...
赞
踩
article
VSCode
中的用户自定义配置文件
setting
s.
json
和默认配置
defaultSettings
...
shotkeysCtrl+Shift+P 打开命令面板输入
setting
s,选择即可:选择>Preferences: O...
赞
踩
article
基于
Python
爬虫
山西太原
景点
数据
可视化
系统设计与实现(
Django
框架)
研究
背景与意义、国内外...
基于
Python
爬虫
山西太原
景点
数据
可视化
系统设计与实现(
Django
框架)
研究
背景与意义、国内外
研究
现状毕设毕业设计...
赞
踩
article
Vscode
:
setting
s.
json
的个人配置_
前端开发
vscode
setting
.
json
...
Vscode
:
setting
s.
json
的个人配置_
前端开发
vscode
setting
.
json
设置
前端开发
vsc...
赞
踩
article
CodingTMD’
s
Reading
Li
s
t
...
Following reading li
s
t i
s
s
elected from the paper
s
I had rea...
赞
踩
article
Intellij
和
eclipse
代码
的
抽取
对比...
Intellij
和
eclipse
代码
的
抽取
对比 第一种注释:提示性的行内注释 常用的“
抽取
”功能有三种,
抽取
常量,局部...
赞
踩
article
小
程序
物体
识别
开发(腾讯
云
轻量
云
服务器
搭建)_
微信
小
程序
物体
识别
...
进入xshell,打开一个终端,进入shendu文件夹(cd shendu/),运行编辑环境(source /home/...
赞
踩
article
国产
化
中间件
的
适配
方案_
国产
中间件
...
中间件
是一种软件组件,被广泛应用于许多软件系统中,如企业资源计划(ERP)、客户关系管理(CRM)等。在实际应用中,往往...
赞
踩
article
Spring
Security
4 使用@
PreAuthorize
,@
PostAuthorize
, ...
【相关已翻译的本系列其他文章,点击分类里面的spring security 4】上一篇:
Spring
Security
...
赞
踩
article
中文乱码
解决办法
_
text
-
encoding
-
shim
...
解决vscode,C语言输出中文乱码_
text
-
encoding
-
shim
text
-
encoding
-
shim
...
赞
踩
article
SpringBoot
+
Vue
的
房屋
租赁系统(含前后台)_
vue
房屋
出租
案例...
基于
SpringBoot
+
Vue
的租房网站系统首先声明下,这是本人的毕业设计,主要实现的是一个租房网站加后台管理系统。本...
赞
踩
article
策略
模式
:精妙替代你
的
if
-
else
_
策略
模式
代替
if
else
...
1、
策略
模式
并不是什么高大上
的
东西,其本质是利用map
的
哈希结构,优化了
if
-
else
等不优雅
的
代码结构。2、除了多个函...
赞
踩
article
清华
大学
chatGLM6B
模型
本地
化部署教程_
清华
大
模型
本地
调用...
ChatGLM-6B 是一个开源的、支持中英双语的对话语言
模型
,基于 General Language Model (G...
赞
踩
相关标签
腾讯云
服务器
阿里云
java
python
linux
中间件
人工智能
自然语言处理
NLP
商业智能
什么是自然语言处理
transformer
bert
大数据
vscode
json
ide
VSCode
json配置
defaultSettings
settings
山西太原景点数据可视化
javascript
scala