一致代价搜索的特性分析

1. 节点扩展策略

  • 处理所有代价小于最优解的节点!
  • 如果最优解的代价为C*,且每条边的最小代价为ε,则"有效深度"约为⌈C*/ε⌉

2. 复杂度分析

  • 时间复杂度:(随有效深度呈指数增长)
  • 空间复杂度:(大约需要存储最后一层的节点)

3. 算法特性

完备性:
  • 是完备的,前提是:
    • 最优解具有有限代价
    • 最小边代价为正数
最优性:
  • 是最优的!
  • 反证法证明:
如果不是最优的,那么在从起始节点到节点n的最优路径上必然存在另一个边界节点n',根据定义,n'的累积代价会比n小,因此应该先被选中。这与UCS的选择策略矛盾。
 
 
Loading...
Z_cosy
Z_cosy
浙江大学电气工程学院本科生
公告
🎉Welcome to Z-cosy🎉
-- 食用指南 ---
目前只有课程笔记以及电控学习笔记
陆续会整理更多内容!