2．搜索算法分析

　　算法分析主要要回答这些方法执行的效果怎样，找到的解其优劣程度如何。在一般的计算机科学领域中，主要强调对算法进行数学分析，如严格数学分析遇到困难，则采取运行一组经过精心挑选的问题，再对其执行情况作统计分析。而人工智能领域研究这个问题的途径则采取将算法用某种语言具体实现，然后运行某个智能问题的典型实例，并观察其表现行为来进行分析比较。这主要是由于人工智能问题比较复杂，通常不容易对一过程是否可行作出令人信服的分析证明。此外，有时甚至无法把问题的值域描述清楚，因而也难于对程序行为作统计分析。再一点就是人工智能是一门实验科学，实践是目前主要的研究途径。
　　搜索过程最基本的一个分析是对深度为D、分支因数为B的一棵完全树的节点数（为BD）进行讨论。显然如果一过程执行的时间随问题的规模变大而指数增长时，则该过程无实用意义。因此要研究改进穷举搜索的各种方法，并通过所得到的搜索时间上界，来和穷举法比较改善的程度。目前优于穷举法的若干方法有三种情况。
　　（1）能保证找到的解与穷举法所得结果一样好，但耗时较少。这类方法的问题是能否给出某一方法具体有多快。
　　（2）对问题的一些实例，耗费时间和穷举法一样，但对另一些实例则较穷举法好得多。这类方法的问题是运行一组一般问题，期望有多快。
　　（3）得到的解比穷举法结果较差。问题是要在给定时间内找到解，这个解与最佳解之间有多大差别。
　　此外对NP－完全类问题，已知若干非确定型（即每次可得到任意数目的路径数）多项式时间的算法，但所有已知的确定性算法都是指数型的。可以证明，NP－完全类中的若干问题在下述意义上彼此等价：如果能找到其中一个问题的一种确定型多项式时间算法，则该算法可应用于所有的问题。
　　综上所述，求解人工智能问题的一个途径是企图以多项式时间求解NP－完全类问题。实现这一点可有两种选择：一是寻找平均角度看执行较快的一些算法，即使在最坏的情况下不慢也行；另一是寻找近似算法，使能在可接受的时间限度内获得满意的解答。
分支界限法实际上是第一种选择的实例，对这种策略有如下评述：
　　（1）各种选择按完美排序进行时，最好情况下其性能有多好。
　　（2）各种选择按不良排序（从最坏到最好）进行时，最差情况下其性能有多好。结果显然，其搜索节点数同穷举法，此外还必须附加跟踪当前约束及进行无畏的比较工作量。
　　（3）各种选择按某种随机过程的排序进行时，平均情况下其性能有多好。
　　（4）各种选择按应用于一组特定问题的启发函数排序进行时，在实际世界中，平均角度看其性能有多好。通常这个结果优于真正随机世界的平均情况。
　　总的来说，人们愿意接受良好的平均时间性能，但即使如此也未必能做得满意，就连分支界限法的平均时间也是指数型的（~1.2eN，N为问题的规模）。因此有时也得牺牲完美解的要求并接受近似的解法。一种进一步改进的分支界限法，用于求解旅行商问题称为最近邻居算法就是求满意解的一个实例，通过分析得到所需的时间与N2成比例。
　　至于A算法既是"寻找平均较快"策略的例子，又是求满意解策略的例子，关键是启发函数h的选取问题。至于更深入的讨论可参阅有关文献。