学习笔记整理之状态图与状态图搜索

开篇

本篇笔记来自于我对于学习人工智能的笔记整理，整理自《人工智能导论》（廉师友版）第三章的部分。

何为状态图？

状态图（也叫状态机图或有限状态机）是一种用来描述系统行为的工具。它通过图形化的方式表示系统在不同状态下的可能行为和状态之间的转换。

• 什么是状态？
  状态是系统在某一时刻的条件或情况。可以想象成系统的“情景”或“模式”。比如，自动贩卖机的状态可能包括“待机中”、“接受硬币”、“出货中”等。
• 状态图的组成部分
  • 状态（节点）：代表系统的某个具体条件或情景。状态通常用圆圈或矩形表示。
  • 转换（边）：表示系统从一个状态转变到另一个状态的过程。转换通常用箭头表示。
  • 事件或条件：引发状态转换的触发事件或条件。这些通常在箭头旁边标注，说明在什么情况下状态会发生变化。

状态图搜索

描述

所谓搜索，顾名思义，就是从初始节点出发，在图中试探地前进，寻找目标节点的过程（也可以反向进行）。那么，当目标节点找到后，路径也就找到了。所以寻找目标和寻找路径是一致的。可以想象，由于图中有许多节点和边，因此搜索过程中经过的节点和边，按连接关系，便会构成一个树形的有向图。这种树形有向图称为搜索树。

搜索方式

用计算机来实现状态图的搜索有两种基本方式：树式搜索和线式搜索。

树式搜索

所谓树式搜索，形象的说就是以“画树”的方式进行搜索。即从树根（初始节点）出发，一笔一笔的描绘出一棵树来。准确的讲，树式搜索就是在搜索过程中记录所经过的所有节点和边。所以树式搜索所记录的轨迹始终是一棵“树”，这棵树也就是搜索过程中所产生的搜索树。

线式搜索

所谓线式搜索，形象的说就是以“画线”的方式进行搜索。准确的讲，线式搜索在搜索过程中只记录那些当前认为是处在所找路径上的节点和边。所以，线式搜索所记录的轨迹始终是一条线（折线）。

线式搜索的基本方式可分为不回溯和可回溯的两种。

• 不回溯

不回溯的线式搜索就是每到一个“岔路口”仅沿一条路进行前进，即对每一个节点始终都仅生成一个子节点（如果有子节点的话）。生成一个节点的子节点也称为对该节点进行拓展。这样，如果扩展到某一个节点，该节点恰好就是目标节点，则搜索成功；如果直到不能再扩展时，还没找到目标节点，则搜索失败。

• 可回溯

可回溯的线式搜索也是对每一个节点都仅扩展一条边，但当不能再扩展时，则退回一个节点，然后再扩展另一条边（如果有的话）。这样，要么最终找到了目标节点，搜索成功；要么一直回溯到初始节点也未找到目标节点，则搜索失败。

• 搜索策略

对于状态图搜索，已经提出了许多策略，大体可分为【盲目搜索】和【启发式搜索】两大类。

盲目搜索

盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。那么，树式盲目搜索就是穷举式搜索，即从初始节点出发，沿连接边逐一考察各个节点（看是否为目标节点），或者反向进行；而线式盲目搜索，对于不回溯的就是随机碰撞式搜索，对于回溯的则也是穷举式的搜索。

启发式搜索

启发式搜索则是利用“启发性信息”引导的搜索。所谓的“启发性信息”就是与问题有关的有利于尽快找到问题解的信息或知识。

按搜索范围的扩展顺序的不同，搜索又可分为广度优先和深度优先两种类型。树式搜索即可深度优先进行，也可广度优先进行；不回溯的线式搜索，则总是深度优先进行。

搜索算法

树式搜索算法

• 算法描述
  （注：这里强烈建议自己在纸上画一画，会更容易理解）

1.把初始节点S0放入OPEN表中
2.若OPEN表为空，则搜索失败，退出
3.移除OPEN表中第一个节点N放入CLOSED表中，并冠以顺序编号n
4.若目标节点Sn = N,则搜索成功，结束
5.若N不可扩展，则转2
6.拓展N，生成一组子节点，对这组子节点做如下处理：

• 删除N的先辈节点（如果有的话）
• 对已存在于OPEN表的节点（如果有的话）也删除之；但删除之前要比较其返回初始节点的新路径与原路径，如果新路径“短”，则修改这些节点在OPEN表中的原返回指针，使其沿新路径返回
• 对已存在于CLOSED表的节点（如果有的话），做与b同样的处理，并且再将其移出CLOSED表，放入OPEN表重新拓展（为了重新计算代价）
• 对其余子节点配上指向N的返回指针后放入OPEN表中某处，或对OPEN表进行重新排序，转2

不回溯的线式搜索

1.把初始节点S0放入CLOSED表中
2.令N=S0
3.若N是目标节点，则搜索成功，结束
4.若N不可扩展，则搜索失败，退出
5.拓展N，选取其一个未在CLOSED表中出现过的子节点N1，放入CLOSED表中，令N=N1，转步骤3

可回溯的线式搜索

1.把初始节点S0放入CLOSED表中
2.令N=S0
4.若N是目标节点，则搜索成功，结束
4.若N不可扩展，则移除CLOSED表中的末端节点Ne，若Ne=S0，则搜索失败，退出。否则，以CLOSED表新的末端节点Ne作为N，即令N=Ne，转步骤3
5.扩展N，选取其一个未在CLOSED表中出现过的子节点N1，放入到CLOSED表中，令N=N1，转步骤3

注

以上便是本次笔记的全部整理内容，后面会把对应算法的描述和具体代码实现整理。