人工智能:一种现代的方法 第三章 经典搜索 上

这篇具有很好参考价值的文章主要介绍了人工智能:一种现代的方法 第三章 经典搜索 上。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

人工智能:一种现代的方法 第三章 经典搜索 上

3.1 问题求解智能体

环境假设:单Agent、确定的、可观察的、离散的、已知的

问题求解智能体的工作流程通常如下:

  • 目标设定:首先,问题求解智能体需要有一个明确的目标或需要解决的问题。
  • 问题形式化:然后,智能体需要将这个目标或问题形式化为一个搜索问题。这通常涉及到定义一个初始状态(即问题的起始点),一个或多个目标状态(即问题的解决方案),以及一组可能的操作(即从一个状态移动到另一个状态的方法)。
  • 搜索策略:接下来,智能体需要选择一个搜索策略,以便在可能的解决方案中找到一个有效的解决方案。这可能涉及到使用一种或多种上述提到的搜索算法。
  • 解决方案执行:最后,一旦找到一个解决方案,智能体就会执行相应的操作或步骤,以达到其目标状态。

良定义的问题及解

在人工智能中,一个良定义的问题是指一个问题,其有明确的初始状态、目标状态和可行的动作集合。这些元素共同构成了问题的解决方案空间,其中搜索算法可以在此空间内寻找解决方案。是人工智能中问题形式化的一个重要部分

  • Agent的初始状态Init
  • Agent的可能动作Action(s)
  • Agent的目标状态target
  • 转移模型Result(s,a)
  • 目标测试函数
  • 路径耗散函数

以迷宫为例

在迷宫问题中,我们从入口(初始状态)出发,通过向上、下、左、右移动(动作),根据转移模型确定新的位置,直到达到出口(目标状态)。我们用步数或通过特定区域的成本(路径成本函数)来评估解决问题的效率。这个问题就是一个良定义的问题,可以用搜索算法来解决。

人工智能:一种现代的方法 第三章 经典搜索 上,人工智能,chatgpt

解:从初始状态到目标状态的动作序列,解的质量由路径耗散函数度量
具有最小路径耗散值的解即为最优解

3.2 问题实例

3.2.1八数码问题

八数码问题:在这个问题中,我们有一个3x3的格子,其中8个格子包含数字1到8,一个格子是空的。初始状态是数字的一个特定排列,目标状态是数字的另一个特定排列(通常是12345678x)。动作是将数字移动到相邻的空格子。转移模型根据选择的动作和当前状态决定新的状态。目标测试检查当前状态是否为目标状态。路径成本函数可以是移动的步数。

八数码BFS实现

int bfs(string state)//初始状态
{
    queue<string> q;
    unordered_map<string, int> d;//耗散函数

    q.push(state);
    d[state] = 0;

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//动作集

    string end = "12345678x";
    while (q.size())
    {
        auto t = q.front();
        q.pop();

        if (t == end) return d[t];//目标测试集

        int distance = d[t];
        int k = t.find('x');
        int x = k / 3, y = k % 3;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];//转移模型
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                swap(t[a * 3 + b], t[k]);
                if (!d.count(t))
                {
                    d[t] = distance + 1;
                    q.push(t);
                }
                swap(t[a * 3 + b], t[k]);
            }
        }
    }

    return -1;
}
3.2.2八皇后问题

八皇后问题的描述:

  • 状态:描述8个棋子在棋盘上的分布
  • 初始状态:任何状态均可
  • 目标条件:检测是否为给定的目标状态
  • 动作:每个棋子或空格的滑动Left、Right、Up、Down
  • 状态转移函数(后继函数)
  • 路径耗散函数(略)

八皇后DFS实现

void dfs(int x, int y, int s)
{
    if (s > n) return;
    if (y == n) y = 0, x ++ ;

    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i ++ ) puts(g[i]);
            puts("");
        }
        return;
    }

    g[x][y] = '.';
    dfs(x, y + 1, s);

    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
    {
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        g[x][y] = 'Q';
        dfs(x, y + 1, s + 1);
        g[x][y] = '.';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
    }
}

八皇后问题的改进描述

  • 状态:描述0-8个皇后在棋盘上的分布,满足最左侧每列放置一个皇后,无法相互攻击
  • 动作:在最左侧空列中的任一空位放置一个皇后,无法相互攻击

八皇后DFS

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; i ++ )
        if (!col[i] && !dg[u + i] && !udg[n - u + i])
        {
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
      }
  }

改进的版本在定义问题的方式上更加明确和约束,这使得搜索解决方案的过程更加高效。这说明搜索的效率与顺序有关。

3.3 搜索

3.3.1搜索树

搜索树

  • 树结点:状态
  • 边:动作/可选动作
  • 根结点:初始状态
  • 满足目标条件的叶结点:目标状态

解:从初始状态到达目标状态的动作序列

3.3.2 树搜索

树搜索的基本步骤:

  • 初始化:将初始状态作为根节点放入一个待处理节点列表(通常称为“开放列表”或“边缘表”)。
  • 节点选择:从开放列表中选择一个节点。选择的方式取决于具体的搜索策略。
  • 目标测试:检查选定的节点是否为目标状态。如果是,那么搜索成功,返回从根节点到该节点的路径。否则,继续下一步。(部分算法的目标测试也可在扩展阶段)
  • 扩展:将选定节点的所有后继节点(即通过应用所有可能的动作得到的新状态)添加到开放列表中。
  • 重复:返回第二步,继续选择新的节点。如果开放列表为空,那么搜索失败,说明没有找到从初始状态到目标状态的路径。
3.3.3 图搜索

在图搜索中,我们将每个访问过的节点添加到一个已访问节点列表中(通常称为“关闭列表”)。当我们考虑扩展一个节点时,如果它已经在关闭列表中,那么我们就跳过它。这样可以避免无限循环和不必要的重复搜索。

图搜索的基本步骤:

  • 初始化:将初始状态作为根节点放入一个待处理节点列表(通常称为“开放列表”),并且创建一个空的关闭列表。
  • 节点选择:从开放列表中选择一个节点。选择的方式取决于具体的搜索策略。
  • 目标测试:检查选定的节点是否为目标状态。如果是,那么搜索成功,返回从根节点到该节点的路径。否则,继续下一步。(部分算法的目标测试也可在扩展阶段)
  • 扩展:将选定节点的所有后继节点(即通过应用所有可能的动作得到的新状态)添加到开放列表中,前提是它们不在关闭列表中。
  • 更新关闭列表:将当前节点添加到关闭列表中。
  • 重复:返回第二步,继续选择新的节点。如果开放列表为空,那么搜索失败,说明没有找到从初始状态到目标状态的路径。
3.3.4 问题求解算法的性能

评价算法的性能

  • 完备性:问题有解,算法一定能找到
  • 有效性:算法找到的解,是问题的解
  • 最优性:问题有解,算法一定能找到最优解
  • 时间复杂度:时间开销
  • 空间复杂度:空间开销

树搜索/图搜索的复杂度

  • 分支因子b
  • 目标结点的深度d,结点的最大深度m

第三章 经典搜索 上 总结

本文我们主要讲述了问题求解智能体的工作流程,良定义的问题和解,数据结构搜索树。这方面很重要的良定义的问题和解 和搜索树,现实中很多问题都可以抽象成图的问题,然后进行搜索求解,良定义的问题和解提供一种思路来如何抽象。同时搜索树也发挥出重要作用,将状态转化为节点,边作为动作可选动作,以及搜索策略:选择哪个结点进行扩展。

接下来我们将继续讲述具体的搜索策略,敬请期待!!!文章来源地址https://www.toymoban.com/news/detail-745642.html

到了这里,关于人工智能:一种现代的方法 第三章 经典搜索 上的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【人工智能:现代方法】第19章:样例学习

    智能体学习(learning) :一个智能体通过对世界进行观测来提高它的性能 机器学习 (machine learning):智能体是一台计算机 —— 一台计算机观测到一些数据,基于这些数据构建一个 模型 (model),并将这个模型作为关于世界的一个 假设 (hypothesis)以及用于求解问题的软件

    2024年01月22日
    浏览(58)
  • 创新释放:Atlassian 人工智能引领现代工作

    随着人工智能技术的蓬勃发展, 越来越多企业开始关注将 AI 技术应用于业务 。作为一家备受瞩目的协作软件工具提供商, Atlassian 积极探索并应用人工智能技术 。 在人类历史上, 团队一直是最伟大成就的核心 。Atlassian 的使命在于 释放每个团队的潜力 ,协助他们 完成单独

    2024年02月03日
    浏览(75)
  • 自然语言处理的崛起:从人工智能的黎明到现代技术的融合

    自然语言处理的发展经历了多个阶段,大致可以分为以下四个阶段: 萌芽期(1956年以前) :这一时期可以看作自然语言处理的基础研究阶段。一方面,人类文明经过几千年的发展,积累了大量的数学、语言学和物理学知识,这些知识不仅是计算机诞生的必要条件,同时也是

    2024年01月19日
    浏览(69)
  • 自然辩证法与人工智能:一种哲学与技术的对话

    在当代科技飞速发展的背景下,人工智能作为计算机科学的一个分支,正日益渗透到我们的生活、工作、学习等各个领域。与此同时,自然辩证法作为马克思主义哲学的重要组成部分,为我们理解和应对科技发展提供了独特的视角。本文试图探讨自然辩证法与人工智能之间的

    2024年02月05日
    浏览(45)
  • Elasticsearch:为现代搜索工作流程和生成式人工智能应用程序铺平道路

    作者:Matt Riley Elastic 的创新投资支持开放的生态系统和更简单的开发者体验。 在本博客中,我们希望分享 Elastic® 为简化你构建 AI 应用程序的体验而进行的投资。 我们知道,开发人员必须在当今快速发展的人工智能环境中保持灵活性。 然而,常见的挑战使得构建生成式人工

    2024年02月04日
    浏览(57)
  • 人工智能(第三版)阅读笔记

      要确定人工智能的优缺点,就必须首先理解和定义智能。   R.斯腾伯格:智能是个体从经验中学习、正确推理、记忆重要信息,以及应对日常生活需求的认知能力。 不同的动物物种具有不同程度的智能,但并不是所有能够思维的物体都有智能--智能也许就是高效以及有效的思

    2024年01月23日
    浏览(49)
  • 基于图卷积神经网络的人工智能:一种新的图像识别技术

    近年来,随着深度学习技术的快速发展,图像识别领域也取得了显著的进步。传统的图像识别方法

    2024年02月07日
    浏览(57)
  • 人工智能(第三版)—【第一章】练习题

    逆图灵测试的一个可能的实际应用是 在线购票系统 。在购票过程中,用户可能会遇到各种问题、疑虑或困惑,例如座位选择、票价查询、支付问题等。通过进行逆图灵测试,系统可以判断用户是在与人交互还是与另一台计算机交互,从而提供更加个性化和准确的服务。 在这

    2024年02月21日
    浏览(51)
  • 《人工智能》第三版 第一章 概述 课后习题

    第一章 讨论题 1.你如何定义人工智能? 人工智能利用计算机和机器模仿人类大脑解决问题和决策的能力 2.区分强人工智能和弱人工智能。 区分强人工智能和弱人工智能的关键在于它们的功能和应用范围:强人工智能能够执行任何人类智能任务,而弱人工智能则专注

    2024年01月25日
    浏览(46)
  • 人工智能(第三版)—第一章讨论题

    人工智能是机器执行与人类思维相关的认知功能的能力,例如感知、推理、学习、与环境交互、解决问题,甚至发挥创造力的未来世界的愿景。 将人工智能称之为机器可以具有人类思维相关认知能力的愿景 目前解决的方式是通过机器学习的方法来逼近人工智能这一个愿景 其

    2024年01月20日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包