问题形式化
回到之前的探讨，我们应该知道人工智能应该是“正确的行为”，而在需要采用的正确动的作不明显时，智能体需要提前规划：考虑一个形成通往目标状态路径的动作序列。这样的智能体被称为问题求解智能体（$problem$-$solving$ $agent$），它所进行的计算过程被称为搜索（$search$）。
最开始我们只需要考虑最简单的环境，即回合式的、单智能体的、完全可观测的、确定性的、静态的、离散的和已知的环境，并对有信息（$informed$）算法和无信息（$uninformed$）算法进行区分。在有信息算法中，智能体可以估计自己到目标的距离，而在无信息算法中不能进行这样的估计。
目标通过限制智能体的目的和需要考虑的动作来组织其行为。
智能体刻画实现目标所必需的状态和动作——进而得到这个世界中与实现目标相关的部分所构成的抽象模型。
在真实世界中采取任何动作之前，智能体会在其模型中模拟一系列动作，并进行搜索，直到找到一个能到达目标的动作序列。这样的序列称为解（$solution$）。智能体可能不得不模拟多个无法到达目标的序列，但最终它要么找到一个解，要么发现问题是无解的。在一个完全可观测的、确定性的、已知的环境中，任何问题的解都是一个固定的动作序列。
智能体执行解中的动作。
状态空间（$state$ $space$）：可能的环境状态（$state$）的集合；
初始状态（$initial$ $state$）：智能体启动时的状态；
目标状态（$goal$ $state$）：一个或多个目标状态（goal state）的集合；
行动集合（$action$）：给定一个状态$s$，$Actions(s)$将返回在 s 中可以执行的有限动作集合；
转移模型（$transition$ $model$）：用于描述每个动作所起到的作用，$Result(s, a)$将返回在状态$s$中执行动作$a$所产生的状态；
动作代价函数（$action$ $cost$ $function$）：在编程中记作$Action-Cost(s, a, s’ )$，在数学运算中记作$c(s, a, s’ )$。它给出了在状态$s$中执行动作$a$从而转移到状态$s’$的数值代价。
搜索算法
搜索算法（$search$ $algorithm$）将搜索问题作为输入并返回问题的解或返回$failure$（当解不存在时）。对搜索算法的分析主要考虑在状态空间图上叠加一棵搜索树（$search$ $tree$）的算法，该算法从初始状态形成各条路径，并试图找到一条可以达到某个目标状态的路径。搜索树中的每个节点（$node$）对应于状态空间中的一个状态，搜索树中的边对应于动作。树的根对应于问题的初始状态。
搜索树的根节点位于初始状态，按如下方式扩展节点：考虑该状态的可用动作$Actions$，使用$Result$函数查看这些动作指向何处，并为每个结果状态生成一个新节点，称为子节点或后继节点。
随后需要从这几个子节点中选择一个考虑下一步扩展。这就是搜索的本质——先跟踪一个行为，之后再考虑其他行为。假定选择先扩展某个节点，其子节点就会被加入到未被扩展的节点当中，一般称这些未被扩展的节点为搜索树的边界（$frontier$）。任何已经生成过节点的状态都称为已达（$reached$）状态（无论该节点是否被扩展）。边界的意义在于分离了状态空间图的两个区域，即内部区域（其中每个状态都已被扩展）和外部区域（尚未到达的状态）。
最佳优先搜索（$bestfirst$ $search$）是一种非常通用的用于决定下一步从边界扩展哪个节点的方法。在这种方法中，需要先选择使得某个评价函数$f(n)$的值最小的节点 n。在每次迭代中，选择边界上具有最小$f(n)$值的一个节点，如果它的状态是目标状态，则返回这个节点，否则调用$Expand$生成子节点。对于每个子节点，如果之前未到达过该子节点，则将其添加到边界；如果到达该子节点的当前路径的代价比之前任何路径都要小，则将其重新添加到边界。
该算法要么返回$failure$，要么返回一个节点（表示一条通往目标的路径）。通过使用不同的$f(n)$函数，可以得到不同的具体算法，后文将介绍这些算法。
以下是最佳优先搜索的伪码描述：
function Best-First-Search(problem, f) returns 一个解节点或 failure
node <- Node(状态=问题.初始状态)//解序列
frontier（一个以 f 排序的优先队列）
reached（已达状态记录表，记录到达某节点的花费）
while frontier 非空：
node <- Pop(frontier)
如果已达目标状态则 return node
for child in Expend(problem,node)；
s <- child.state
如果 s 状态 未达 或 此路径到达 s 状态 的花费小于 reached 表所记录的：
更新 reached 表的 s 状态信息 并把 child 加入 frontier
return failure
function Expend(problem,node) yields 节点
s <- node.state
for action in problem.Actions(s):
s- <- problem.Result(s,action)
cost <- node.cost + problem.Actions-cost(s,action,s-)
yield Node(state=s-,Parent=node,Action=action,path-cost=cost)
● 优先队列（$priority$ $queue$）首先弹出根据评价函数 f 计算得到的代价最小的节点。它被用于最佳优先搜索。
● $FIFO$队列（$FIFO$ $queue$），即先进先出队列（$first$-$in$-$first$-$out$ $queue$），首先弹出最先添加到队列中的节点；它被用于广度优先搜索。
● $LIFO$队列（$LIFO$ $queue$），即后进先出队列（$last$-$in$-$first$-$out$ $queue$），也称为栈（$stack$），首先弹出最近添加的节点；它被用于深度优先搜索。
如果搜索算法会检查冗余路径，称之为图搜索（$graph$ $search$）；否则，称之为树状搜索（$tree$-$like$ $search$）。前文伪码描述的$Best$-$First$-$Search$算法是一种图搜索算法；如果删除所有对$reached$的引用，即为树状搜索，它使用更少的内存，但会出现到达相同状态的冗余路径，因此运行速度会更慢。
在选择使用的算法前一般需要对算法的性能进行分析，一般来说分析的角度包括四个：
● 完备性（$completeness$）：当存在解时，算法是否能保证找到解，当不存在解时，是否能保证报告失败？完备的搜索算法探索无限状态空间的方式必须是系统的，以确保它最终能够到达与初始状态相关的任何状态。但是，在一个不存在解的无限状态空间中，一个合理的算法会一直搜索，它不会终止，因为它不知道下一个状态是否是目标状态。
● 代价最优性（$cost$ $optimality$）：它是否找到了所有解中路径代价最小的解？
● 时间复杂性（$time$ $complexity$）：找到解需要多长时间？可以用秒数来衡量，或者更抽象地用状态和动作的数量来衡量。
● 空间复杂性（$space$ $complexity$）：执行搜索需要多少内存？
