13.多选题(4分)若一搜索树的树高有限且所有单步损耗均非负，则为每条边的损耗乘上一正常数w>0，以下树搜索算法中（）所得搜索路径保持不变。A. BFSB. DFSC. UCSD. 无

本题考查不同树搜索算法的特性以及单步损耗变化对搜索路径的影响。解题思路是分别分析每个选项所代表的搜索算法的原理，判断当每条边的损耗乘上一个正常数 $w>0$ 时，搜索路径是否保持不变。

选项A：BFS（广度优先搜索）

• 原理：BFS 是一种盲目搜索算法，它按照层次依次扩展节点，从根节点开始，先扩展距离根节点最近的所有节点，然后再依次扩展下一层的节点。其搜索过程只关注节点的层次，不考虑边的损耗。
• 分析：由于 BFS 不依赖于边的损耗来决定搜索顺序，所以当每条边的损耗乘上一个正常数 $w>0$ 时，搜索路径不会受到影响，仍然按照原来的层次顺序进行搜索，所得搜索路径保持不变。

选项B：DFS（深度优先搜索）

• 原理：DFS 也是一种盲目搜索算法，它从根节点开始，沿着一条路径尽可能深地搜索，直到无法继续扩展，然后回溯到上一个节点，继续搜索其他路径。其搜索过程只关注节点的深度，不考虑边的损耗。
• 分析：因为 DFS 不依赖于边的损耗来决定搜索顺序，所以当每条边的损耗乘上一个正常数 $w>0$ 时，搜索路径不会发生改变，仍然按照原来的深度优先顺序进行搜索，所得搜索路径保持不变。

选项C：UCS（一致代价搜索）

• 原理：UCS 是一种启发式搜索算法，它总是选择扩展路径代价最小的节点。设原路径的代价为 $C$，路径上有 $n$ 条边，每条边的损耗分别为 $c_1, c_2, \cdots, c_n$，则 $C = \sum_{i = 1}^{n} c_i$。
• 分析：当每条边的损耗乘上一个正常数 $w>0$ 后，新的路径代价 $C'=\sum_{i = 1}^{n} (w\times c_i)=w\times\sum_{i = 1}^{n} c_i = w\times C$。由于 $w$ 是正常数，对于任意两条不同的路径，它们的代价比例关系保持不变。也就是说，原来代价小的路径，在乘以 $w$ 后仍然代价小。所以 UCS 仍然会选择原来的最优路径进行扩展，所得搜索路径保持不变。