关于路径搜索算法的实用性优化

UESTC 20013080 林 伟 2002.9.12

介绍：本文阐述对著名的路径搜索算法 A* 算法的重要改进，使之更实用于大规模，高效率，多阻塞，模糊求解的任务中。希望本文起一个抛砖引玉的作用，使读者能举一反三。

这里所提及的 A* 算法在许多领域内得到广泛的应用，比如我们熟悉的即时战略游戏正是利用这个算法来实现路径搜索的。 但是人工智能的书上只是说，却很少有实现的例子，理论与实际差距太大，一些专业人士也曾经书写过代码，但代码的优点在于说明算法，而在效率与实用性方面就有些欠缺。

A* 是启发试搜索加动态规划。具体实现依靠两个队列Open队列和Close队列。从一点开始探走几个相邻的格子如果可以移动且当前移动为起点到哪个格子的历 史最佳方法则把那个格子按照估价值从小到大插入Open队列里面，几个方向试探结素后取出估价值最小的节点放入Close再从这里开始试探几个相邻的方向 同样放入Open队列里面，放入Open的条件是1.这步在地图上面是可以移动的，2.这步所在节点在Open里面并不存在，3.从起点到这步的实际距离 比这点的历史最小距离还短满足这三个条件就把节点放入Open队列。具体的算法网友们已经描述的再清楚不过了大致算法如下:

WHILE TRUE BEGIN
  1. 把S点加入OPEN队列（按该点到E点的距离排序+走过的步数从小到大排序） 
  2. 排序队列OPEN队列中距离最小的第一个点出列，并保存入CLOSE队列中 
  3. 从出列的点出发，分别向4个（或8个）方向中的一个各走出一步 
  4. 估算第3步所走到位置到目标点的距离，并把该位置按估价距离从小到大排序后并放入OPEN中 
  5. 如果该点从四个方向上都不能移动，则把该点从CLOSE队列中删除 
  6. 从目标点回溯树，直到树根则可以找到最佳路径，并保存在PATH中 
END

图表1：A*路径搜索算法流程

2001-2002期间开发的虚拟机/编译器开源项目代码和资料

1. 关于虚拟机及其编译器的说明
2. VmBasic开发/调试环境的介绍及说明
3. 关于其他

所有资料可以从下面地址下载： 下载可执行 源程序下载 设计说明书

关于虚拟机及其编译器的说明

记得3DS/MAX里面实现了一个类似BASIC的脚本，Animator里面实现了一个类C的脚本语言，Autodesk公司的软件对于脚本支持的很出色，好的脚本引擎在乎平台无关性、高效性和扩充性，一个脚本引擎的需要对一个好程序来说非常迫切，于是半年前我写了一款虚拟机，最近又实现了一个类Basic的脚本编译器，特性说明：

1. 高效性和独立于平台：由于虚拟机运行是解释二进制的字节码因此速度明显快于每次运行及时解释的脚本语言，比如Perl和PHP，而虚拟机的核心程序代码也经过数个C++编译器和平台的测试，可以毫无修改的编译运行于多个操作系统。
2. 充分的开放：通过虚拟机的端口I/O技术，要对它进行扩充变得十分容易，VmBeta指令通过输出/输入的方法向用户自己的程序进行通讯，用户通过处理输出输入消息来达到功能的扩充，使它符合你产品的需要，具体的虚拟机实现和设计说明参考文档 vmbeta.txt
3. 可设安全级别：通过可设置安全级别，对程序运行状态进行检控

通过半年的修改我自己觉得虚拟机够高效开放，就是vmbasic编译器写的没有多高的水准：完全没有对生成代码做优化，弄出许多繁琐的中间代码，不过还是明显快于及时解释语言，通过测试速度大概是DOS自带的QBASIC程序的三倍左右(可以通过目录下的几个算法程序来实验)。

麻雀虽小，五脏具全，对编译原理的代码以TPASCAL格式重新整理和排版，还原最原版的代码。

使用 Turbo Pascal 编译：