当前位置: 首页 > news >正文

【人工智能】—_深度优先搜索、代价一致搜索、深度有限搜索、迭代深度优先搜索、图搜索

【人工智能】无信息搜索—BFS 、代价一致、DFS、深度受限、迭代深入深度优先、图搜索

什么是搜索

  • 搜索问题是指既不能通过数学建模解决,又没有其他算法可以套用或者非遍历所有情况才能得出正确结果。这时就需要采用搜索算法来解决问题。搜索就是一种通过穷举所有解的状态,来求得题目所要求的解或者最优解的方法。
  • 搜索的基本概念:
    1. 状态:对某一系统在某一时刻的数学描述。
    2. 动作:从当前时刻状态转移到下一时刻所处状态的操作。
    3. 状态转移:对某一时刻的状态进行动作后所达到的状态。
    4. 路径:一个状态序列,该序列被一系列动作所连接。
    5. 目标测试:评估当前状态是否是所求解的目标状态。

树搜索算法

  • 基本思想:通过扩展已探索状态的后继,离线模拟探索状态空间
    在这里插入图片描述
  • 以下图举例在这里插入图片描述
  • 根据给定的初始状态初始化搜索树在这里插入图片描述
  • 根据策略strategy决定扩展哪个叶子结点,直到达到目标状态
    在这里插入图片描述在这里插入图片描述

搜索策略

  • 通过选择节点扩展的顺序来定义搜索策略
  • 根据以下维度评估策略:
    • 完整性(完备性): 如果存在,它是否总能找到解决方案?
    • 时间复杂性(时间复杂度): 生成的节点数
    • 空间复杂性(空间复杂度) : 内存中的最大节点数
    • 最优性(最优性): 它总是找到成本最低的解决方案吗?
  • 时间和空间复杂性是根据
    • b: maximum branching factor of the search tree搜索树的最大分支因子—分支因子
    • d: depth of the least-cost solution—最浅的目标节点的深度
    • m: maximum depth of the state space状态空间的最大深度(可以是 ∞ ∞ )—最大深度

无信息搜索

不一致的搜索策略只使用问题定义中可用的信息

  • Breadth-first search 广度优先搜索
  • Uniform-cost search 代价一致搜索
  • Depth-first search 深度优先搜索
  • Depth-limited search 深度受限搜索
  • Iterative deepening search 迭代深度优先搜索

Breadth-first search

在这里插入图片描述
  • 扩展最浅的未扩展节点

  • 实施:边缘结点是一个FIFO队列,即,新来的后继放在末尾

  • 时间复杂度 :BFS算法的时间复杂度可以通过BFS中遍历的节点数来获得,直到最浅的节点。其中 d= 最浅解的深度,b是每个状态的节点。在这里插入图片描述

  • 空间复杂度: O ( b d + 1 ) O(b ^{d+1}) O(bd+1)(keeps every node in memory)

  • 完整性:BFS完成,这意味着如果最浅的目标节点处于某个有限的深度,那么BFS将找到解决方案。

  • 最优性:如果路径成本是节点深度的非递减函数,则BFS是最优的。

  • 空间是个大问题;可以轻松地以100MB/秒的速度生成节点,因此24小时=8640GB。

Uniform-cost search

  • 一致代价搜索(Uniform Cost Search),优先扩展拥有最小路径消耗函数g(n)的结点,和最佳优先搜索(Best-first Search)在代码实现上一致,即最佳优先搜索的评价函数f(n)等于g(n)时,最佳优先搜索即为一致代价搜索。
  • 一致代价搜索是用于遍历加权树或图的搜索算法。
  • 当每个边缘有不同的成本时,该算法开始起作用
  • 一致代价搜索的主要目标是找到具有最低累积成本的目标节点的路径。一致代价搜索根据路径成本从根节点扩展节点。
  • 它可用于解决需要最优成本的任何图/树。一致代价搜索算法由优先级队列实现。它最优先考虑最低累积成本。
  • 如果所有边的路径成本相同,则一致代价搜索等效于宽度优先搜索算法
  • 完整性:是,如果每一步代价 ≥ ε ≥ε ε
  • 时间复杂性: O ( b c e i l i n g ( C ∗ / ε ) O(bceiling(C*/ ε) O(bceiling(C/ε) C ∗ C* C是最佳解决方案的成本, g ≤ g≤ g最优解代价的节点数
  • 空间复杂度: O ( b c e i l i n g ( C ∗ / ε ) O(bceiling(C*/ ε) O(bceiling(C/ε) g ≤ g≤ g最优解代价的节点数
  • 最优解:节点按 g(n) 的递增顺序扩展

Depth-first search

  • DFS的核心是沿着树的深度遍历树的结点,尽可能深的探索树的分支,当结点v的所有边都已经被探索后,将回溯到发现v的那条边的起始结点。这一过程一直进行到已发现初始结点可以到达的所有结点为止,如果还有未被发现的结点,则从中选择一个作为初始结点重复上述过程,直到所有结点都被访问为止。
  • DFS的基本原则可以归纳为:按照某种条件一直往前探索,如果在过程中失败,比如死路(全部探索完但是仍没有解)则返回,另选一条道路继续,直到到达目标结点为止。
  • 深度优先搜索扩展搜索树中深度最深的结点。
  • 它既不是完备的也不是最优的,但它具有线性的空间复杂度。
  • 总是扩展在队列frontier中level最深的结点。深度优先搜索的其中一个variant是回溯搜索(Backtracking Search),可以实现更小内存开销。
  • 完整性:DFS搜索算法在有限状态空间内完成,因为它将扩展有限搜索树中的每个节点。
  • 时间复杂度:DFS的时间复杂度将等同于算法遍历的节点。它的公式如下:
    在这里插入图片描述
    其中,m = 任何节点的最大深度,这可能远大于d(Shallowest解算深度)
  • 空间复杂度:DFS算法只需要存储来自根节点的单个路径,因此DFS的空间复杂度等于边缘集的大小,即O(bm)。
  • 最优解:DFS搜索算法不是最优的,因为它可能产生大量步骤或高成本以到达目标节点。

depth-limited search

  • 深度受限搜索(Depth-limited Search),是在深度优先搜索基础上,设置搜索深度限制。因为当搜索状态空间很大的时候,深度优先搜索DFS会非常尴尬,所以可以通过设置搜索深度界限来避免。
  • 深度有限搜索算法类似于具有预定限制的深度优先搜索。深度限制搜索可以解决深度优先搜索中无限路径的缺点。在该算法中,深度限制的节点将被视为没有后继节点
  • 可以使用两个失败条件终止深度限制搜索
    • 标准故障值:表示问题没有任何解决方案。
    • 截止故障值:它在给定的深度限制内没有定义问题的解决方案。
  • 完整性:如果解决方案高于深度限制,则DLS搜索算法完成。
  • 时间复杂度:DLS算法的时间复杂度为O(bℓ)。
  • 空间复杂度:DLS算法的空间复杂度为O(b×l)。
  • 最优解:深度限制搜索可以看作是DFS的一个特例,即使ℓ> d也不是最优的。

Iterative deepening search

  • 由Depth-limited search演化而成,每轮增加深度限制
  • 迭代加深的深度优先搜索(Iterative deepening depth-first Search),逐步增大限制搜索的深度,直到返回目标结点。
  • 迭代加深的深度优先搜索是DFS和BFS算法的组合。此搜索算法找出最佳深度限制,并通过逐渐增加限制直到找到目标为止。迭代加深(Iterative deepening)搜索,实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树,若没有发现可行解,再将K+1后重复以上步骤搜索,直到搜索到可行解。
  • 在迭代加深搜索的算法中,连续的深度优先搜索被引入,每一个深度约束逐次加1,直到搜索到目标为止。
  • 迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求,又能保证发现一个最小深度的目标结点。
  • 从实际应用来看,迭代加深搜索的效果比较好,并不比广度优先搜索慢很多,但是空间复杂度却与深度优先搜索相同,比广度优先搜索小很多,在一些层次遍历的题目中,迭代加深不失为一种好方法!
  • 该算法执行深度优先搜索直到某个“深度限制”,并且在每次迭代之后它不断增加深度限制,直到找到目标节点。
  • 此搜索算法结合了广度优先搜索的快速搜索和深度优先搜索的内存效率的优势。当搜索空间很大并且目标节点的深度未知时,迭代搜索算法对于无知搜索是有用的。
  • 示例,以下树结构显示迭代加深深度优先搜索。IDDFS算法执行各种迭代,直到找到目标节点。算法执行的迭代如下在这里插入图片描述
  • 第1次迭代——-> A
    第2次迭代——> A,B,C
    第3次迭代———> A,B,D,E,C,F,G
    第4次迭代———> A,B,D,H,I,E,C,F,K,G
    在第四次迭代中,算法将找到目标节点。
  • 完整性:如果分支因子是有限的,则该算法是完整的。
  • 时间复杂性:假设b是分支因子,深度是d,那么最坏情况时间复杂度是O(bd)。
  • 空间复杂性:IDDFS的空间复杂度为O(bd)。
  • 最优解:如果路径成本是节点深度的非递减函数,则IDDFS算法是最佳的。

图搜索

  • 检测不到重复状态可能会将线性问题变成指数问题!在这里插入图片描述

  • 避免探索冗余路径的方法是牢记曾经走过的路。

  • 为了做到这一点,我们给TREE-SEARCH搜索树算法增加一个参数–这个数据结构称为探索集(也被称为 closed 表),用它记录每个已扩展过的结点。

  • 新生成的结点若与已经生成的某个结点相匹配的话–即是在探索集中或是边缘集中-那么它将被丢弃而不是被加入边缘集中。

  • 新算法叫 GRAPH-SEARCH,图搜索

小结

在这里插入图片描述

相关文章:

【人工智能】—_深度优先搜索、代价一致搜索、深度有限搜索、迭代深度优先搜索、图搜索

【人工智能】无信息搜索—BFS 、代价一致、DFS、深度受限、迭代深入深度优先、图搜索 什么是搜索 搜索问题是指既不能通过数学建模解决,又没有其他算法可以套用或者非遍历所有情况才能得出正确结果。这时就需要采用搜索算法来解决问题。搜索就是一种通过穷举所有解…...

uni-app 客服按钮可上下拖动动

项目需求: 因为悬浮客服有时候会遮挡住界面内容,故需要对悬浮的气泡弹窗做可拖动操作 movable-area:可拖动区域 movable-view:可移动的视图容器,在页面中可以拖拽滑动或双指缩放。 属性说明 属性名类型默认值说…...

基于Android的旅游管理系统 微信小程序

随着网络科技的发展,移动智能终端逐渐走进人们的视线,相关应用越来越广泛,并在人们的日常生活中扮演着越来越重要的角色。因此,关键应用程序的开发成为影响移动智能终端普及的重要因素,设计并开发实用、方便的应用程序…...

python-数据可视化-下载数据-CSV文件格式

数据以两种常见格式存储:CSV和JSON CSV文件格式 comma-separated values import csv filename sitka_weather_07-2018_simple.csv with open(filename) as f:reader csv.reader(f)header_row next(reader)print(header_row) # [USW00025333, SITKA AIRPORT, A…...

时序预测 | MATLAB实现SSA-XGBoost(麻雀算法优化极限梯度提升树)时间序列预测

时序预测 | MATLAB实现SSA-XGBoost(麻雀算法优化极限梯度提升树)时间序列预测 目录 时序预测 | MATLAB实现SSA-XGBoost(麻雀算法优化极限梯度提升树)时间序列预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实现SSA-XGBoost时间序列预测,麻…...

leetcode 823 带因子的二叉树

用动态规划 如果两个节点值不同,要乘2,因为两个节点可以互换位置 dp[i] dp[left] * dp[right] * 2 如果相同 dp[i] dp[left] * dp[right] class Solution {public int numFactoredBinaryTrees(int[] arr) {Arrays.sort(arr);int n arr.length;long[] dp ne…...

钉钉消息已读、未读咋实现的嘞?

前言 一款app,消息页面有:钱包通知、最近访客等各种通知类别,每个类别可能有新的通知消息,实现已读、未读功能,包括多少个未读,这个是怎么实现的呢?比如用户A访问了用户B的主页,难道…...

Java 读取TIFF JPEG GIF PNG PDF

Java 读取TIFF JPEG GIF PNG PDF 本文解决方法基于开源 tesseract 下载适合自己系统版本的tesseract ,官网链接:https://digi.bib.uni-mannheim.de/tesseract/ 2. 下载之后安装,安装的时候选择选择语言包,我选择了中文和英文 3.…...

研磨设计模式day14模板方法模式

目录 场景 原有逻辑 有何问题 解决方案 解决思路 代码实现 重写示例 模板方法的优缺点 模板方法的本质 何时选用 场景 现在模拟一个场景,两个人要登录一个系统,一个是管理员一个是用户,这两个不同身份的登录是由后端对应的两个接…...

7 集群基本测试

1. 上传小文件到集群 在hadoop路径下执行命令创建一个文件夹用于存放即将上传的文件: [atguiguhadoop102 ~]$ hadoop fs -mkdir /input上传: [atguiguhadoop102 hadoop-3.1.3]$ hadoop fs -put wcinput/work.txt /input2.上传大文件 [atguiguhadoop1…...

chrono学习(一)

我想用chrono进行沙土的仿真,首先学习demo_GPU_ballCosim.cpp,这个例子仿真了一些沙土的沉降过程。 首先,运行编辑完成的文件demo_GPU_ballCosim: (base) eowyneowyn-MS-7D20:~/build_chrono/bin$ ./demo_GPU_ballCosim 运行完得…...

后端面试话术集锦第 十 篇:springMVC面试话术

这是后端面试集锦第十篇博文——springMVC面试话术❗❗❗ 1. 介绍一下springMVC springmvc是一个视图层框架,通过MVC模型让我们很方便的接收和处理请求和响应。 我给你说说他里边的几个核心组件吧: 它的核心控制器是DispatcherServlet,他的作用是接收用户请求,然后给用户…...

基于Django 框架搭建的机器学习在线平台源代码+数据库,实现KNN、ID3、C4.5、SVM、朴素贝叶斯、BP神经网络等算法及流程管理

结果展示(Kmeans): 完整代码下载地址:基于Django 框架搭建的机器学习在线平台源代码数据库 python机器学习之 K-邻近算法 简单的理解:[ 采用测量不同特征值之间的距离方法进行分类 ] 优点 :精度高、对异常…...

大数据组件-Flume集群环境搭建

🥇🥇【大数据学习记录篇】-持续更新中~🥇🥇 个人主页:beixi 本文章收录于专栏(点击传送):【大数据学习】 💓💓持续更新中,感谢各位前辈朋友们支持…...

想系列服务迁移专有云效实操

想系列服务迁移专有云效实操 1注册应用 查看jenkins脚本是否需要修改代码编译路径 gemdale_jenkins/maven3-service/k8s-image/maven3-service-deploy.sh Jenkins上的打包路径 service_tgt_path s e r v i c e w s / t a r g e t / service_ws/target/ servicew​s/target/ser…...

2020 牛客多校第三场 C Operation Love (叉积判断顺逆时针)

2020 牛客多校第三场 (叉积判断顺逆时针) Operation Love 大意: 给出一个手型 , 每个手型都有 20 个点 ,手型有可能旋转后给出 , 但不会放大和缩小 . 手型点集有可能顺时针给出也可能逆时针给出 , 判断给出的是左手还…...

基于OFDM的水下图像传输通信系统matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 function [rx_img] func_TR(tx_img, num_path, pathdelays, pathgains, snr) rng(default); …...

Docsify + Gitalk详细配置过程讲解

💖 作者简介:大家好,我是Zeeland,开源建设者与全栈领域优质创作者。📝 CSDN主页:Zeeland🔥📣 我的博客:Zeeland📚 Github主页: Undertone0809 (Zeeland)&…...

React中的setState的执行机制

文章目录 前言setState是什么?更新类型批量更新后言 前言 在 React 中,setState 是用于更新组件状态的方法。它是一个异步操作 值得注意的是,由于 setState 是异步的,所以在调用 setState 后立即访问 this.state 可能得到的还是旧的状态值。…...

2023最新任务悬赏平台源码uniapp+Thinkphp新款悬赏任务地推拉新充场游戏试玩源码众人帮威客兼职任务帮任务发布分销机

新款悬赏任务地推拉新充场游戏试玩源码众人帮威客兼职任务帮任务发布分销机制 后端是:thinkphpFastAdmin 前端是:uniapp 1.优化首页推荐店铺模块如有则会显示此模块没有则隐藏。 2修复首页公告,更改首页公告逻辑。(后台添加有公…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...