QSCTech#zju-icicles#考点1

# AI Notebook 第一题：给了一幅图，求不同搜索方法的路径（图搜索而非树搜索）：a.深度优先； b.广度优先； c.uninformed cost search； 一致代价搜索，expand a cheapest node first， frontier 是一个优先队列。这个算法要注意的是: node 产生的时候进行goal test会出错!! 需要expand这个节点的时候再goal test。 把每一步的代价g(n)考虑进去, 根据代价小的结点来扩展. d.给了h(n)的A*搜索； 那就是h(n)+g(n)考虑最小损耗. e.d中给的启发式函数admissible和consistency的判断和理由 admissible : 就是 小于实际损耗, 常见的是去掉一些限制条件, 比如有一些位置不能走, h(n)不考虑这些限制. consistency就是两边之和大于第三边, 一个状态s1 的h(n), 走一步到达 s2的耗费cost,s2为hn2, 如果 hn+cost >hn2那就是consiste