搜索效率与启发能力和问题属性有关的分析

一个搜索过程的搜索效率不仅取决于过程自身的启发能力，而且还与被解问题的有关属性等多种因素有关。目前虽已有多种定义和计算搜索效率的方法，但都有一定的局限性。下面讨论两种常用的方法，它们适用于比较同一问题的不同搜索方法的效率。

（一）外显率

外显率定义为，其中，L为从初始节点到目标节点的路径长度；T为整个搜索过程中所生成的节点总数。

外显率反映了搜索过程中从初始节点向目标节点前进时搜索区域的宽度。当L＝T时，P＝1，表示搜索过程中每次只生成一个节点，它恰好是解路径上的节点，搜索效率最高。P越小表示搜索时产生的无用节点越多，搜索效率越低。

（二）有效分枝因数

有效分枝因数B定义为B＋B2＋···＋BL＝T，其中，B是有效分枝因数，它表示在整个搜索过程中每个有效节点平均生成的子节点数目；L为路径长度；T为节点总数。

当B＝1时，有

此时所生成的节点数最少，搜索效率最高。

不难证明，有效分枝因数与外显率之间有如下关系：(www.xing528.com)

由此可以看出，当B一定时，L越大则P越小；当L一定时，B越大则P越小。另外，对同一个L而言，B越大则T越大，即对一定的解路径来说，分枝越多，搜索空间产生的节点也越多。

【注释】

[1]尚福华，曹茂俊.人工智能[M].哈尔滨：哈尔滨工业大学出版社，2008：51.

[2]涂序彦，马忠贵，郭燕慧.广义人工智能[M].北京：国防工业出版社，2012：34.

[3]张皓，刘万久，黎俞琳，韩有才.风力发电偏航控制系统研究及技术展望[J].四川水泥，2018（6）.

[4]史忠植，王文杰.人工智能[M].北京：国防工业出版社，2007：75.

[5]邢传鼎，杨家明，任庆生.人工智能原理及应用[M].上海：东华大学出版社，2005：104.