搜索求解2019-MOOC.pdf

启发式搜索

• 辅助信息：所求解问题之外、与所求解问题相关的特定信息或知识（直线距离）
• 评价函数（evaluation function）f(n)：从当前节点𝑛出发，根据评价函数来选择后续节点
• 启发函数（heuristic function）h(n)：计算从节点𝑛到目标节点之间所形成路径的最小代价值。这里将两点之间的直线距离作为启发函数。

Greedy best-first search

• 评价函数f(n)=启发函数h(n)
• 每次寻找当前节点的最短的边，无法确保一定是最优解
• 有可能会遇到死循环，不完备 →需要一个良好的启发函数

A* Algorithm

• 评价函数：优先级的决定

• 为了保证A*算法是最优 (optimal) ，需要启发函数 ℎ(𝑛) 是可容的 (admissible heuristic) 和一致的 (consistency，或者也称单调性，即 monotonicity)

  • 理解：曲线越来越直线的过程
  • 可容性：启发函数不会过高估计(over-estimate)从节点𝑛到目标结点之间的实际开销代价（即小于等于实际开销）
  • 一致性：假设节点𝑛的后续节点是𝑛′，则从𝑛到目标节点之间的开销代价一定小于从𝑛到𝑛′的开销再加上从𝑛′到目标节点之间的开销（后续开最小开销肯定小于你弯曲走的路）

• 算法步骤

  • 每次扩展评估函数最小的
  • 启发函数 → 距离，可以使用曼哈顿距离，对角距离，欧几里得距离
  • 启发函数也可以恒为0 ，此时 g(n) 决定节点的优先级，此时算法就退化成了 Dijkstra 算法

• 结论

  • 如果函数满足一致性条件，则一定满足可容条件
  • Tree-search的A算法中，如果启发函数ℎ 𝑛 是可容的，则A算法是最优的和完备的；在Graph-search的A算法中，如果启发函数ℎ 𝑛是一致的，A算法是最优的。

对抗搜索

• 通过竞争一方最大化利益，另外一方最小化利益
• 主要内容
  • Minimax Search：基本，一种让玩家来计算最优策略的方法。
  • Pruning Search：可以剪除无需搜索的分支节点，且不影响搜索结果
  • Monte-Carlo Tree Search：采样而非穷举方法来实现搜索
• 描述