人工智能:一种现代的方法 第三章 经典搜索 上
3.1 问题求解智能体
环境假设:单Agent、确定的、可观察的、离散的、已知的
问题求解智能体的工作流程通常如下:
- 目标设定:首先,问题求解智能体需要有一个明确的目标或需要解决的问题。
- 问题形式化:然后,智能体需要将这个目标或问题形式化为一个搜索问题。这通常涉及到定义一个初始状态(即问题的起始点),一个或多个目标状态(即问题的解决方案),以及一组可能的操作(即从一个状态移动到另一个状态的方法)。
- 搜索策略:接下来,智能体需要选择一个搜索策略,以便在可能的解决方案中找到一个有效的解决方案。这可能涉及到使用一种或多种上述提到的搜索算法。
- 解决方案执行:最后,一旦找到一个解决方案,智能体就会执行相应的操作或步骤,以达到其目标状态。
良定义的问题及解
在人工智能中,一个良定义的问题是指一个问题,其有明确的初始状态、目标状态和可行的动作集合。这些元素共同构成了问题的解决方案空间,其中搜索算法可以在此空间内寻找解决方案。是人工智能中问题形式化的一个重要部分
- Agent的初始状态Init
- Agent的可能动作Action(s)
- Agent的目标状态target
- 转移模型Result(s,a)
- 目标测试函数
- 路径耗散函数
以迷宫为例
在迷宫问题中,我们从入口(初始状态)出发,通过向上、下、左、右移动(动作),根据转移模型确定新的位置,直到达到出口(目标状态)。我们用步数或通过特定区域的成本(路径成本函数)来评估解决问题的效率。这个问题就是一个良定义的问题,可以用搜索算法来解决。
解:从初始状态到目标状态的动作序列,解的质量由路径耗散函数度量
具有最小路径耗散值的解即为最优解
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
接下来我们将继续讲述具体的搜索策略,敬请期待!!!文章来源地址https://www.toymoban.com/news/detail-745642.html
到了这里,关于人工智能:一种现代的方法 第三章 经典搜索 上的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!