问题：若等代价搜索算法中所有连接弧线具有相等代价，则退化为宽度优先搜索算法（ ）。
A.对 B.错
您的当前位置是：第三章 确定性推理>>学习内容>>知识点二
三、等代价搜索
下面学习等代价搜索
1．定义
在上面的讨论中，都没有考虑搜索的代价问题，认为图中各边的代价都相同，事实上，图中各边的代价是可能完全不一样。在等代价搜索中，搜索树中每条连接弧线上标有代价值，表示时间、距离等花费。
等代价搜索是宽度优先搜索的一种推广，不是深度最小的节点进行扩展，而是选择代价最小的节点进行扩展。若所有连接弧线具有相等代价，则退化为宽度优先搜索算法。
2．几个记号
①起始节点记为S；
②把从节点i到其后继节点j的连接弧线代价记为c（i，j）。
③把从起始节点S到任一节点i的路径代价记为g（i）。
g（j）=g（i）+c（i，j）
3．基本思想
OPEN表中的节点在任一时刻都是按其代价从小到大排序的，代价小的节点排在前面，代价大的节点排在后面，每次扩展时总是从OPEN表中选取代价最小的节点进行扩展。
4．等代价搜索算法
等代价搜索方法以g（i）的递增顺序扩展其节点。具体算法如下：
①把起始节点放到OPEN表中。如果该起始节点为一目标节点，则求得一个解；否则令g（S）=0。
②如果OPEN是个空表，则没有解，失败退出；
③从OPEN表中选择一个节点i，使其g（i）最小。如果有几个节点都合格，那么就要选择一个目标节点i（要是有目标节点的话）；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。
④如果节点i为目标节点，则求得一个解。
⑤扩展节点i。如果没有后继节点，则转向上述第②步。
⑥对于节点i的每个后继节点j，计算g（j）=g（i）+c（i，j），并把所有后继节点放到OPEN表，并提供回溯到节点i的指针。
⑦转向第②步。
等代价搜索算法框图如图3.13所示。
例3.4 图3.14是五城市之间的交通线路图，A是出发地，E是目的地，两城市间的交通费用如图中数字所示。求从A到E的最小费用交通路线。
该问题的等代价搜索树如图3.15所示。
由搜索过程可知，问题的最优解路径为：A→C1→D1→E2
