Intelligente Systeme 课程总结

智能系统课程考试之前做的总结,教授喜欢出各种简答题,所以本文主要是各种算法的优缺点、使用场景、复杂度。另外因为是德语考试,所以除了中文以外的内容大多是德语。

1. 不带权搜索

算法 BS 广度优先搜索 TS 深度优先搜索 TBS 深度限制搜索 IV 迭代加深搜索
完整性 否(树高有限时“是”) 是(t \ge d
最优
时间复杂度 b^d b^m b^t b^d
空间复杂度 b^d bm bt bd

b:分支因数

d:解的深度

m:树高

t:限制深度

完整性和最优性条件

  • 可解
  • 有限分支因数
  • 所有路径代价相同

树高有限则深度优先搜索完整,否则不具有完整性。

IV具有BS的时间复杂度,同时又有更好的空间复杂度。

继续阅读“Intelligente Systeme 课程总结”