Notion 博客 一个NotionNext搭建的博客
数据库系统概论
大数据原理与应用
javaWeb应用开发基础教程
python
毕业设计
大数据技术综合应用
实训-航空数据系统
java面向对象程序设计
数据结构
算法分析与设计
SPARK
Python爬虫大数据采集与挖掘
云计算
概率论与数理统计
数字逻辑
计算机网络
计算机组成原理
linux
操作系统
人工智能导论
数据仓库与数据挖掘
数据可视化
大数据安全与隐私保护
c语言
C++
[第五章]搜索求解策略
搜索的概念
搜索的基本问题和过程
- 搜索需要解决的基本问题
- 搜索是否有解，是否最佳，时空复杂性如何，是否死循环
- 搜索的主要过程
- 从初始或目的状态出发，视为当前状态
- 扫描操作算子集，将使用的算子作用于当前，建立指向父结点的指针
- 检查新状态是否满足结束状态，满足，则沿指针从结束状态到开始状态；否则新状态为当前状态，重复b
搜索策略
- 初始→ 数据驱动
- 目的→ 目的驱动
盲目搜索：对问题没有相关信息的前提下，依次或随机操作算子进行搜索
启发式搜索：考虑特定知识，动态调用算子，选择合适的算子
状态空间的搜索策略
状态空间表示法
状态:表示系统状态，事实等叙述型知识的一组变量或数组，可以是某种结构的符号或数据
- Q=[q1,q2…]
操作：引起状态变化的过程型知识的一组关系或函数
- F=[f1,f2…]
状态空间是利用状态变量和操作符号，表示系统或问题的有关知识的符号体系。
- (S,O,S,G)
- S是状态集合，O是操作算子集合，G是包含问题的目的状态
状态空间的图描述
盲目的图搜索策略
回溯策略
当遇到不可解结点时，就回溯到路径中最近的父结点上，查看该节点是否还有其他的子节点未被扩展。若有，则沿这些子结点继续搜索；弱国找到目标，就成功退出搜索，返回解题路径
回溯搜索算法
- PS表（路径状态表）：保存当前路径上的状态。找到目的，PS就是解路径上的状态有序集
- NPS表（新的路径状态表）：包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展
- NSS表（不可解状态表）：列出找不到解路径的状态。如果在搜索中扩展出的状态是他的元素，则可以立即将之排除，不必沿该状态继续搜索
- 类似深度优先搜索
宽度优先搜索
BFS，类似层次遍历，一层一层的遍历，从左往右，从上到下
- open表（NPS表）：已经生成出来但其子状态未被搜索的状态
- closed表（PS表和NSS表的合并）：记录已被生成扩展过的状态
深度优先搜索策略
DFS，类似先根遍历，根左右
- 有深度限制
- 将扩展的后继节点放在open表前端
- open表先进先出
启发式图搜索策略
利用与问题有关的信息引导搜索
- 应用场景：问题模糊，无特定解；有特定解，但解空间特别大
启发信息和估价函数
Prev
[第四章]不确定性推理方法
Next
[第六章]智能计算及其应用
Loading...