在开始设计各种搜索算法之前, 需要考虑在这些算法中进行选择时所使用的标准。我们可以从以下4个方面评价算法的性能。
-
完备性: 当存在解时，算法是否能保证找到解，当不存在解时，是否能保证报告失败？ -
代价最优性: 它是否找到了所有解中路径代价最小的解？ -
时间复杂性: 找到解需要多长时间？可以用秒数来衡量，或者更抽象地用状态和动作的数量来衡量。 -
空间复杂性: 执行搜索需要多少内存？
为了理解完备性，考虑一个具有单一目标的搜索问题。这个目标可能是状态空间的任何地方；因此，一个完备的算法必须能够系统地探索从初始状态可以到达的每一个状态。在有限状态空间中，这是很容易实现的：只要我们跟踪路径并切断循环，最终我们将到达每一个可到达的状态。
在无限状态空间中，则需要更加小心。在一个没有障碍的无限网格上，沿着直线不停前进也会形成由新状态组成的无限路径。在这种情况下，算法永远不会返回它之前到达的状态，但它是不完备的，因为状态空间中的大部分状态永远都不会到达。
完备的搜索算法探索无限状态空间的方式必须是系统的，以确保它最终能够到达与初始状态相关的任何状态。例如，在无限网格上，一种系统搜索算法是螺旋路径，它覆盖了距离原点s步远的所有单元格，然后移动到s+1步远的单元格，遗憾的是，在一个不存在解的无限状态空间中，一个合理的算法会一直搜索，它不会终止，因为它不知道下一个状态是否是目标状态。
时间复杂性和空间复杂性与问题的困难程度相关。在理论计算机科学中，一种典型的度量方式是状态空间图的大小，|v|+|E|, 其中 |v|是图中顶点的数量，|E|是边的数量。当状态空间图是显示的数据结构时，这种度量是合适的。但是在许多人工智能问题中，状态空间图只是由初始状态、动作和转移模型隐式地表示。对于隐式的状态空间，复杂性可以用3格量来衡量：d,最优解的深度或动作数；m,任意路径的最大动作数；b,需要考虑的节点的分支因子或后继节点数。
