启发式搜索中的寻路问题 -- 一篇课程报告

最近在 <Artificial Intelligence> 这门课的课程论文上写了一个 survey , 主要涉及了一些常见的寻路问题, 包括寻找最短路径的若干问题,寻找第 k 短路径的若干问题以及未知全局的寻路问题. 本来想把论文的内容翻译出来贴在博客上, 后来发现和之前的几篇博文有一部分重复的地方, 只有几个算法在博客中没有提到. 于是决定把摘要目录翻译一下, 另直接把文章贴出来和大家分享.

原文章使用英文撰写, 题目是<A Survey on the Form for Heuristic Determination of Pathfinding>. 内容上主要以讲算法的动机, 内容和效率为主, 也有一些不同算法之间的比较. 翻译如下.

题目: 关于启发式决策中寻路问题的求解框架之调查

摘要: 寻路问题及其求解策略在人工智能及其之外的领域有着重要而广泛的应用. 自20世纪70年代以来, 便出现了大量的总结性工作, 试图把不同种类的寻路问题求解算法归纳在一个统一框架里. 该文在这些工作中作了一系列调查研究, 并通过一个逻辑主线在不同问题的求解策略之间建立了联系. 该文主要围绕这些方法的动机, 适用性和性能进行探讨, 一些典型的应用和扩展也会被涉足.

目录:
1. 引言
2. 图模型中的寻路问题
2.1 有向无环图中的基本寻路策略
2.2 有环图中的基本寻路策略
3. 基于搜索顺序的启发式决策
3.1 有向图模型中的启发式搜索
3.2 优先队列与搜索顺序
3.3 有向图模型中的改进
3.4 无向图模型中的启发式搜索
3.5 几种策略间的比较
4. 复杂需求上的启发式方法
4.1 方块剪枝与复杂寻路
4.2 复杂寻路问题上的 k 最优启发式搜索
5. 在线搜索中的启发式方法
6. 拓展与讨论
7. 致谢

文章用的LaTeX模板不是很好, 以后考虑改进一下. 原文链接如下:

PDF file in Google Drive

欢迎大家批评指正!