题目
以下关于启发函数和评价函数的说法中正确的是()。 A. 评价函数通常是对当前节点到目标节点距离的估计。B. 启发函数不会过高估计从当前节点到目标结点之间的实际代价。C. 如果启发函数满足可容性,那么在树搜索A*算法中节点的评价函数值按照扩展顺序单调非减;启发函数满足一致性时图搜索A*算法也满足该性质。D. 取值恒为0的启发函数必然是可容的。
以下关于启发函数和评价函数的说法中正确的是()。
- A. 评价函数通常是对当前节点到目标节点距离的估计。
- B. 启发函数不会过高估计从当前节点到目标结点之间的实际代价。
- C. 如果启发函数满足可容性,那么在树搜索A*算法中节点的评价函数值按照扩展顺序单调非减;启发函数满足一致性时图搜索A*算法也满足该性质。
- D. 取值恒为0的启发函数必然是可容的。
题目解答
答案
ABCD
解析
步骤 1:理解启发函数和评价函数的定义
启发函数(Heuristic Function)是用于估计从当前节点到目标节点的代价的函数。评价函数(Evaluation Function)是启发函数与从起始节点到当前节点的实际代价之和,用于指导搜索算法选择下一个扩展的节点。
步骤 2:分析选项A
选项A提到评价函数是对当前节点到目标节点距离的估计。这是正确的,因为评价函数是启发函数与实际代价之和,而启发函数就是对距离的估计。
步骤 3:分析选项B
选项B提到启发函数不会过高估计从当前节点到目标结点之间的实际代价。这是正确的,因为如果启发函数过高估计,那么搜索算法可能会选择错误的路径,导致搜索效率降低。
步骤 4:分析选项C
选项C提到如果启发函数满足可容性,那么在树搜索A*算法中节点的评价函数值按照扩展顺序单调非减;启发函数满足一致性时图搜索A*算法也满足该性质。这是正确的,因为可容性保证了启发函数不会过高估计,而一致性保证了启发函数的单调性,从而保证了评价函数值的单调非减。
步骤 5:分析选项D
选项D提到取值恒为0的启发函数必然是可容的。这是正确的,因为取值恒为0的启发函数不会过高估计从当前节点到目标结点之间的实际代价,因此满足可容性。
启发函数(Heuristic Function)是用于估计从当前节点到目标节点的代价的函数。评价函数(Evaluation Function)是启发函数与从起始节点到当前节点的实际代价之和,用于指导搜索算法选择下一个扩展的节点。
步骤 2:分析选项A
选项A提到评价函数是对当前节点到目标节点距离的估计。这是正确的,因为评价函数是启发函数与实际代价之和,而启发函数就是对距离的估计。
步骤 3:分析选项B
选项B提到启发函数不会过高估计从当前节点到目标结点之间的实际代价。这是正确的,因为如果启发函数过高估计,那么搜索算法可能会选择错误的路径,导致搜索效率降低。
步骤 4:分析选项C
选项C提到如果启发函数满足可容性,那么在树搜索A*算法中节点的评价函数值按照扩展顺序单调非减;启发函数满足一致性时图搜索A*算法也满足该性质。这是正确的,因为可容性保证了启发函数不会过高估计,而一致性保证了启发函数的单调性,从而保证了评价函数值的单调非减。
步骤 5:分析选项D
选项D提到取值恒为0的启发函数必然是可容的。这是正确的,因为取值恒为0的启发函数不会过高估计从当前节点到目标结点之间的实际代价,因此满足可容性。