一般而言，人工智能遇到的问题较为复杂，往往不能在一步之内解决，因此在实际问题中，存在一个寻找一组合适的动作序列，从而达到目标的过程。这个过程我们称之为搜索。“搜索”问题在生活中相当常见，公路导航和魔方复原其实就属于这一类问题。
一个搜索问题一般可由6个部分形式化描述：
1.状态空间（S）：代表所有可能的状态集合，这里状态指的是待解决问题中系统所处的状态。
2.初始状态（s0）：即系统的起始状态。
3.动作空间（A）：智能体所有可执行的状态集合，其中A（s）为系统处于状态s下的可执行动作全体。
4.转移函数T（s，a）：有2个参数，表示在状态s下执行动作a到达的状态。
5.损耗函数c（s，a，s1）：在状态s下执行动作a到达状态s1的损耗。
6.目标测试函数（G（s））：用于验证给定状态s是不是目标状态。一些情况下目标状态s是一个集合而并不是单个状态。
在搜索问题中，把系统从初始状态转化为目标状态的一系列动作称为一个“解”。若以路径上的总损耗为衡量标准，我们把取得最小总损耗的解称为最优解。为了讨论方便，我们不妨假设转移函数是确定的（否则需要将问题建模成一个Markov决策过程），且系统是完全可观测的（这代表智能体总可以获取系统有关的信息）。
在搜索算法中，描述搜索问题的“载体”是数据结构。常见的数据结构包括了图、树、队列等等。
1.图
一个图（G）由节点集（V）和边集（E）组成，记为G=（V，E）；若G中节点之间的边都存在方向（即边单向连接两节点），则称G为有向图，否则称G为无向图（边双向连接两节点）。我们把与一个节点相关联的边数称为该节点的度数，例如三角形中每个顶点的度数都为2；有向图中度数被进一步区分为出度和入度，其中出度代表从此结点指向其他节点的边数，而入度代表从其他结点指向该结点的边数。若为每条边赋上一个权重，就可以代表从一个节点到另一个节点的代价，或者损耗。
在图中，路径代表一个节点通向另一节点所经过的边的序列，而路径长度则为这些边的总数或者权重之和。若一个图中任意两节点有路径相连，则为连通图；更进一步，若这个图还是有向的，则称为强连通图。
2.树
树可以视为一种特殊的无向图，每个节点只有一个父节点（前置的结点），并且只有一个无父节点的节点（称为根节点）。在树结构中，根节点为第1层，根节点为第2层，依此类推。路径表示根节点到目标节点的通路，路径长度是其经过所有边的数量总和。
3.队列
若需要存储未搜索的节点，常用的存储数据结构之一是队列，这是一种线性数据结构，有3种形式：
a.先进先出队列（最先被放入的数据也最优先被取出）
b.优先级队列（队列中所有元素按某优先级排列，高优先级元素先出列）
c.后进先出队列（最后被放入的数据最优先被取出）
网友评论