维普资讯 http://www.cqvip.com ２００８年第２期 文章编号：１００６—２４７５（２００８）０２－００３４－０２ 计算机与现代化 Ｊ１ＳＵＡＮＪＩ ＹＵ ＸＩＡＮＤＡＩＨＵＡ 总第１５０期 状态空间搜索算法的进一步探索 林敬恩，滕忠坚 （福建师范大学物理与光电信息科技学院，福建福州３５０００７） 摘要：主要讨论了ＢＦＳ、ＤＦＳ、Ａ 算法在状态空间搜索中的应用并且给出其在Ｍａｔｈｅｍａｔｉｃｓ下实现。在Ｍａｈｅｍａｔｔｉｃｓ中根据 节点数据绘制出节点分布图，分别使用ＢＦＳ、ＤＦＳ、Ａ 搜索对给定的源点和目标点之间的路径进行搜索，并比较得到的路 径耗散数据，说明引入启发式函数对搜索效率的影响。 关键词：状态空间；Ａ 算法；ＢＦＳ；Ｄｌ；’Ｓ 中图分类号：ＴＰ３０１．６ 文献标识码：Ａ Ｅｘｐｌｏｒａｔｉｏｎ ｏｆ Ｓｅａｒｃｈ Ａｌｇｏｒｉｔｈｍｓ ｉｎ Ｓｔａｔｅ Ｓｐａｃｅ ＬＩＮ Ｊｉｎｇ—ｅｎ，ＴＥＮＧ Ｚｈｏｎｇ－ｊｉａｎ （Ｓｃｈｏｏｌ ｏｆ Ｐｈｙｓｉｃｓ ａｎｄ ＯｐｔｏＥｌｅｅｔｒｏｎｉｅｓ Ｔｅｃｈｎｏｌｏｇｙ，Ｆｕｊｉａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｆｕｚｈｏｕ ３５０００７，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｒｔｉｃｌｅ ｍａｉｎｌｙ ｄｉｓｃｕｓｓｅｓ ａｐｐｌｉｃａｔｉｏｎｓ ｏｆ ＢＦＳ，ＤＦＳ，Ａ’ａｌｇｏｒｉｈｍｓ ｉｔｎ ｓｔａｔｅ ｓｐａｃｅ．Ｔｈｅ ｃｏｍｐｌｅｔｅ ｆｌｏｗ ｃｈａｒｔｓ ｏｎ Ｍａｔｈｅｍａｔｉｃｓ ａｒｅ ｐｌ￣ｖｉｄｅｄ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｎｏｄｅ’Ｓ ｄａｔａ，ｔｈｅ ｐａｐｅｒ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｎｏｄｅ’Ｓ ｄｉｓｔｒｉｂｕｔｉｎｇ ｃｈａｒｔ ａｎｄ ｕｓｅｓ ＢＦＳ，ＤＦＳ， Ａ’ａｌｇｏｒｉｔｈｍｓ ｆ０ｒ ｓｅａｒｃｈｉｎｇ ｐａｔｈｓ ｂｅｔｗｅｅｎ ｓｏｕｌ￣ｃｅ ｎｏｄｅ ａｎｄ ｔａｒｇｅｔ ｎｏｄｅ．Ｆｉｎａｌｌｙ．ｔｈｅ ａｒｔｉｃｌｅ ａｎａｌｙｓｅｓ ａｎｄ ｃｏｍｐａｒｅｓ ｔｈｅ ｄａｔａ ｏｆ ｐａｔｈ ｄｉｓｓｉｐａｔｉｏｎ ｔｏ ｓｈｏｗ ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｉｎｔｒｏｄｕｃｉｎｇ ｈｅｕｒｉｓｔｉｃ ｆｕｎｃｔｉｏｎ ｏｎ ｓｅａｒｃｈ ｅｆｆｉｃｉｅｎｃｙ． Ｋｅｙ ｗｏｒｄｓ．．ｓｔａｔｅ ｓｐａｃｅ：Ａ ￣ｇｏｒｉｔｈｍ；ＢＦＳ；ＤＦＳ １概述 状态空问的搜索策略分为无信息搜索和有信息 搜索。无信息是除了状态基本定义，没有任何关于状 态的附加信息，大多数情况下这种搜索策略是非常无 效的。无信息搜索中最具代表性的是广度优先搜索 （ＢｒＳ）和深度优先搜索（ＤＦＳ）。有信息搜索策略是 除了基本定义之外还利用了特定知识的策略 。有 信息搜索中最具代表性的是Ａ 搜索。 ２构造节点分布图 为了能更直观地让我们观察得到的路径数据，我 们先在Ｍａｔｈｅｍａｔｉｃｓ中构造节点分布图。将各个节点 坐标以及各点问相互的距离耗散数据记录在表中，然 后导人绘制成图。 图１状态空间节点分布图 ３ ＢＦＳ、ＤＦＳ以及Ａ 搜索算法的原理 以及在Ｍａｔｈｅｍａｔｉｃｓ中的模拟实现流程 收稿日期：２００７４）８—１５ ， １．广度优先搜索（ＢＦＳ）：先扩展初始节点的所有 后继节点，然后再扩展它们的后继，以此类推 。搜 索过程是逐层进行的，完成本层搜索才进行下一层的 搜索，直到找到目标为止。只要最浅的目标节点处于 个有限的深度，广度优先搜索在扩展完比它浅的所 有节点之后最终能找到它，因此这种搜索是完备的。 但是完成广度优先搜索所需要的时间和空间将随着 一作者简介：林敬恩（１９８２．），男，福建福州人，福建师范大学物理与光电信息科技学院硕士研究生，研究方向：人工智能，光信 息技术，软件工程；滕忠坚（１９６７ ），男，福建福州人，教授， 美博士，研究方向：人工智能，医学图像处理，数据库，软件工程。 维普资讯 http://www.cqvip.com
２００８年第２勘 林敬恩等：状态空间搜索算法的进一步探索 ３５ 搜索深度的增加，成指数增长 其在Ｍａｔｈｅｍａｔｉｃｓ中 的实现流程： （１）初始化：定义队列Ｐ记录已通过的节点，堆栈队列 ｑｕｅ存放后继点集，变量ｐａｔｈｌｅｎ记录所 问的路径耗散。Ｐ、 ｑｕｅ ｔＩＩ默认的一个元素足源点。变量ｋ＝源点。 （２）满足ｋ 为｝＝Ｊ标点，且队列ｑｕｅ ｌＩ还有冗素时执行 （３）．否则 爪兀可达路 （３）ｋ存放ｑｕｅ队列的首元 （ｎ）＋ｈ（ｎ）最小的节点。这里的估计函数ｈ（ｎ）称为 启发式函数。如果ｈ（ｎ）满足一定的条件，Ａ’算法既 是完备的也是合理的。其在Ｍａｔｈｅｍａｔｉｃｓ中的实现流 程： （１）编写启发式函数ｈ（ｎ）。 （２）初始化：定义ａｒｒｉｖｅｄ组存放二元组｛节点，经过该点 的估计最低耗散ｆ（ＩＩ）｝，ａｒｒｉｖｅｄｌ组存放三元组｛节点，到达该 点的实际耗散ｇ（Ｉ１），该节点的父节点｝，变量ｋ＝源点。 （３）判断当前ｋ节点是否为目标节点，如果是，则显示路 （４）判断ｋ是否存住一个后继 点ｉ，如果 存住ｉ』！ｌＪ删除 ｑｎｅ队列首元素重新从（２）开始执 如果存在ｔ）ｇｌ８）ｔ行（５）。 （５）判断ｉ足否为口标 ． 。如果足，将ｉ点 人到序列Ｐ， 以及将ｋ、ｉ问的路径耗散累＿ＪＪＩ１到ｐａｔｈｌｅｎ—ｌＩ，执行（７）。如果 不是，执行（６） （６）判断ｉ点足 被访问过。如果已经访问过，则ｉ递增， 重新从（２）开始执行。如果术 问过，｛』｛ｌＪ将点ｉ ｌ』ＪＩｆ人到队列Ｐ 和队列ｑｕｅ ｔＩｌｌ＇将ｋ、ｉ阃的路 牦敞累ＪＪＩＩ到ｐａｔｈｌｅｎ ｌｌｌ。删除 ｑｕｅ队列首元索重新从（２）圩始执行。 径和总耗散值并且程序结束。否则执行（４）。 （４）ｋ是否存在一个后继点 ，如果不存在则执行（９），如 果存在则执行（５）。 （５）判断ｉ点是否被访问过，如果已经访问过，则ｉ递增， 重新从（３）开始执行。如果未访问过，继续执行（６）。 （６）计算到达ｉ的实际耗散ｇ（ｉ）。 （７）计算ｉ到目标点的估计耗散１１（ｉ）以及经过ｉ的最低 估计耗散值ｆ（ｉ）。 （８）将｛ｉ，ｆ（ｉ）｝存人ａｒｒｉｖｅｄ中，将｛ｉ，ｇ（ｉ），ｋ｝存人ｄｒ－ ｒｉｖｅｄ１中。 （７） 示路 和总耗散 ： ２ 深度优先搜索（ＤＦＳ）：总是扩展搜索树的当前 边缘中最深的节点… 搜索直接推进到搜索树的最 深层，那里的节点没有屙继节点。当那些节点扩展完 之后，它们被从边缘中去掉，然后搜索算法“向上回 到”下一个还有未扩展后继节点的稍浅的节点。它 （９）取ａｒｒｉｖｅｄ队列中ｆ值最小的点作为下一个ｋ的值。 重新从（３）开始执行。 不是完备的，冈为如果它的当前搜索路径是无限的又 不含目标节点，它将一直搜索下去。但是它所需的内 存较小。其在Ｍａｔｈｅｍａｔｉｃｓ中的实现流程： （１）初始化：定义队列ｐ记录已迎过的节点，堆栈队列 ｑｕｅ存放后继点集，变越ｐａｔｈｌｅＪ１记录所访问的路径耗敞 Ｐ、 ｑｕｅ ＩｆＩ默认的～个元素足源点。变量ｋ＝源点。 （２）满足ｋ小为口标点，且队列ｑｕｅ ＩｆＩ还有元素时执行 （３），否则 ＿，Ｊ 兀可达路 。 在执行中，我们选取源点为编号１２的点和目标 点为编号８２３２的点（多组数据中的其中一组作为例 子）。在ＢＦＳ执行中，最终产生的路径耗散值是１． １５８５４×１０６，一共遍历的节点数为１６５５个。在ＤＦＳ 执行中，最终产生的耗散值是５９５８１６，一共遍历的节 点数为１０３２个。Ａ’搜索算法所产生路径的耗散值 最小，为２８６８８．５。所遍历的点为｛１２，４８２４，４８２５， ４８２６，５１６８，１６１７，１６１４，１６１５，１６１６，８７５２，８７８４， ４８６４，４８６３，７８０，７８８４，４２０６，６５９６，４４９５，４２２８， ｌｌ８８，４１００，３８２４，３８２３，３８２２，７９８３，７９８２，７９８ｌ， （３）将ｑｕｅ队列一Ｉｌ最后一个元素存人ｋ（因为扩展点总足 添ｌ』ＪＩＩ到ｑｕｅ队列的 部，符合扬 度优先的搜索策略）。 （４）判断ｋ足甭存住一个后继节点ｉ，如果不存＿住则删除 ｑｕｅ队列的最后一个兀索重新从（２）开始执行。如果存在则 执行（５）。 ７９８０，８０７０，８００６，８０ｌｌ，８００５，９２２１，８０８７，８０４９， ８０２６，２３７Ｉ，２３７２，８２３２｝。计算消耗的时间为６７． ７０８ ｓｅｃｏｎｄ。前两种算法对于状态空间的搜索是采取 盲目扩展的方式，所得的路径是低效的，特别是随着 节点数的增加，复杂度成倍增加。基于Ａ’算法的模 拟实现了最优路径的寻找，合理的启发式函数大大提 高了搜索效率。 （５）判断ｉ是否为口标， 果是，将ｉ点ＪＪ１１人到序列Ｐ， 以及将ｋ、ｉ问的路 耗散 ＪＪ１ｌ刊ｐａｔｈ［ｅｎ・ｌ ，执行（７）。如果 小足。执行（６） （６）判断ｉ点足否被访问过，ｊｎＪ果已经访问过，ＩＪｊ４ ｉ递增， 重新从（２）开始执行 如果术访问过，则将点ｉ ＪＪＩ１人到队列Ｐ 和队列ｑｕｅ ｌＪ１，将ｋ、ｉ问的路 耗散 ）ＪＩｔ￣０ ｐａｔｈｌｅｎ 并重新 从（２）开始执行。 （７） 爪路径和总耗散他。 ４结束语 本文在Ｍａｔｈｅｍａｔｉｃｓ平台下模拟实现了几种经典 的状态空间搜索算法，并且介绍了它们各自的特点， 阐述了它们的实现流程。特别在Ａ’搜索算法的设 计中，受Ｐｏｈｌ提出的动态加权的启发，在启发式函数 的设计中加值，这样可使得搜索消耗最小化 Ｊ。 本文所做的研究是对状态空间搜索算法的一种探索， 特别是其中的Ａ 搜索算法不断改进，在状态机验证 理论、地图寻径、路由数据传送等领域将发挥更大作 用。 （下转第３９页） ３．Ａ 搜索：Ａ 算法是一种最佳优先搜索算法。 设ｇ（ｎ）是从起始节点到节点１１的路径耗散，ｈ（ｎ）是 从节点ｎ到目标节点的最低耗散路径的估计耗散值。 Ａ 算法就是结合ｇ（ｎ）和ｌ （ｎ）来对节点进行评价：ｆ （ｎ）＝ｇ（ｎ）＋ｈ（ ）。ｆ（ｎ）是经过节点ｎ的最低耗散 解的估计耗散。也就是说Ａ 算法的核心就是扩展ｇ 维普资讯 http://www.cqvip.com ２００８年第２期 Ｓｔｅｐ５：Ｒｅｔｕｒｎ ＳｉｍＩ ．１； 许方芳等：语义网中的本体映射研究 ３９ ［３］Ｈ Ｈ Ｄｏ，Ｅｒｈａｒｄ Ｒａｈｍ．ＣＯＭＡ—Ａ ｓｙｓｔｅｍ ｆｏｒ ｌｆｅｘｉｂｌｅ ｃｏｍｂｉｎａ－ ｔｉｏｎ ｏｆ ｓｃｈｅｍａ ｍａｔｃｈｉｎｇ ａｐｐｒｏａｃｈｅｓ［Ｃ］／／？ｒｏｅ．ｏｆ ｔｈｅ ２８ｔｈ Ｉｎｔ１．Ｃｏｎｆ．ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａｂａｓｅ，２０Ｏ２：６１０－６２１． ２．４概念相似度的综合计算 将概念ｃ．和概念Ｃ：的语义相似度、捕述相似度 以及邻近层次概念相似度按公式（１０）计算可得到所 求的概念相似度，并表永为Ｓｉｍ（Ｃ．，Ｃ ）： Ｓｉｎｌ（Ｃ；，Ｃ？）＝ｗ Ｓｉｍ ．．．．．．（Ｃｌ，Ｃ ）＋ｗ．Ｉ Ｓｉａｌ ； Ｃ２）＋ｗＩ Ｓｉｍ ｈ１、 ，ｗ ＋、ｖ．｛＋、ｖｔ＝１ （Ｃｌ， （１０） ［４］邓志鸿，唐世渭，等．Ｏｎｔｏｌｏｇｙ研究综述［Ｊ］．北京大学 学报（自然科学版），２００２，３８（５）． ［５］ ＧＲＵＢＥＲ ＣＴＲ．Ａ ｔｒａｎｓｌａｔｉｏｎ ａｐｐｒｏａｃｈ ｔｏ ｐｏｒｔａｂｌｅ ｏｎｔｏｌ－ｏ ｇｉｅｓ［Ｊ］．Ｋｎｏｗｌｅｄｇｅ Ａｃｑｕｉｓｉｉｔｏｎ，１９９３，５（２）：１９９－２２０． ［６］ ＢＯＲＳＴＷＮ．Ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ Ｅｎｇｉｎｅｅｒｉｎｇ Ｏｎｔｏｌｏｇｉｅｓ ｆｏｒ Ｋｎｏｗｌｅｄｇｅ Ｓｈａｒｉｎｇ ａｎｄ Ｒｅｕｓｅ［Ｄ］．ＰｈＤ Ｔｈｅｓｉｓ，Ｕｎｉｖｅｒ－ ｓｉｔｙ ｏｆ Ｔｗｅｎｔｃ，Ｅｎｓｃｈｅｄｅ，１９９７． 权值的具体设置值根据具体环境由用户来决定。 ３ 结束语 本文对概念的语义、属性、关系以及层次作了研 究，提出的方法综合改进了相似性度量方面的多种方 法，有很好的效率和准确度．但其权重一般是根据已 有经验给出的，会存在计算误差。 本体的目的就是为了实现知识的共享与重用，但 于本体的多样性和异构性．要想完成信息交流的任 务必须在本体之间架起语义映射的桥梁。本体映射 现在已经是语义网发展过程中存在的一个重要问题． 同外在这方面的研究已经取得了不少的成果．国内这 ［７］Ｇ Ｂｉｓｓｏｎ．Ｗｈｙ ａｎｄ ｈｏｗ ｔｏ ｄｅｆｉｎｅ ａ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕＦｅ ｆｏｒ ｏｂｊｅｃｔ ｂａｓｅｄ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｓｙｓｔｅｍｓ［ｚ］．Ｔｏｗａｒｄｓ Ｖｅｒｙ Ｌａｒｇｅ Ｋｎｏｗｌｅｄｇｅ Ｂａｓｅｓ，１９９５：２３６－２４６． ［８］Ｘｉａｏｍｅｎｇ Ｓｕ．Ａ ｔｅｘｔ ｃａｔｅｇｏｒｉｚａｔｉｏｎ ｐｅｒｓｐｅｃｔｉｖｅ ｆｏｒ ｏｎｔｏｌｏｇｙ ｍａｐｐｉｎｇ［Ｒ］．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ，Ｎｏｒｗｅｇｉａｎ Ｕｎｉｖｅｓｉｒｙｔ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎｏｒｗａｙ，２００２． ［９］Ｈａｌｅｖｙ Ａ，Ｉｖｅｓ Ｚ，Ｍｏｒｋ Ｐ，ｅｔ ａ１．Ｐｉａｚｚａ：Ｍｅｄｉａｔｉｏｎ ａｎｄ ｉｎｔｅｇｒａｔｉｏｎ ｉｆｎｒａｓｔｒｕｃｔｕｒｅ ｆｏｒ ｓｅｍａｎｉｔｃ Ｗｅｂ ｄａｔａ［Ｊ］．Ｊｏｕｒ－ ｎａｌ ｆ ｏＷｅｂ Ｓｅｍａｎｔｉｃｓ，２００４，１（２）：１５５—１７５． ［１０］ Ｋａｌｆｏｇｌｏｕ Ｙ，Ｓｃｈｏｆｌｅｍｍｅｒ Ｍ．Ｏｎｔｏｌｏｇｙ ｍａｐｐｉｎｇ：ｔｈｅ ｓｔａｔｅ ｏｆ ｔｈｅ ａｒｔ［Ｊ］．Ｔｈｅ Ｋｎｏｗｌｅｄｇｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｒｅｖｉｅｗ， ２００３。１８（１）：１－３１． 方面的研究相对还较少。目前儿乎所有的算法案例 中采用的都是专家人工输入．不同本体映射的半自动 化和自动化的研究取得的成就卜分有限，是今后研究 工作的一个重点。还有一点就是本体的构建是本体 映射的基础，因此完善本体的构造也是非常必要的。 参考文献： ［１１］ Ｍａｅｄｃｈｅ Ａ。Ｍｏｔｉｋ Ｂ，Ｓｉｌｖａ Ｎ，Ｖｏｋ Ｒ．ＭＡＦＲＡ—ａ ｍａｐｐｉｎｇ ｆｒａｍｅｗｏｒｋ ｆｏｒ ｄｉｓｔｒｉｂｕｔｅｄ ｏｎｔｏｌｏｇｉｅｓ［Ｃ］／／Ｐｒｏ－ ｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １３ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌ－ ｄｇｅｅ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ｋａ；ｏｗｌｄｇｅｅ Ｍａｎａｇｅｍｅｎｔ，Ｓｉｇｔｉｅｎｚａ， Ｓｐａｉｎ，２００２． ［１２］Ｂ Ｎｇｕｙｅｎ，Ｍ Ｖａｚｉｒｉｇａｌｌｉｓ，Ｉｎ Ｖａｆｌａｍｉｓ，ｅｔ ａ１．Ｏｒｇａｎｉｚｉｎｇ Ｗｅｂ ｄｏｃｕｍｅｎｔｓ ｉｎｔｏ ｔｈｅｍａｔｉｃ ｓｕｂｓｅｔｓ ｕｓｉｎｇ ａｎ ｏｎｔｏｌｏｇｙ ［１］ Ｊ Ｍａｄｈａｖａｎ，Ｐ Ａ Ｂ ’ｎｓｔｅｉｎ，Ｅ ｌｔａｈｍ．（；．ｅｎｅｒｉｃ ｓｃｈｅｍａ ｍａｔｃｈｉｎｇ ｗｉｔｈ ｃｕｐｉｄ［Ｃ］／／Ｐｒｃ．ｏｏｆ ｔｈｅ ２７ｔｈ Ｉｎｔ１．Ｃｏｄ． Ｏｉｌ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａｂａｓｅｓ，２００１：４９－５８． ［Ｊ］．ＶＬＤＢ Ｊｏｕｒｎａｌ，Ｓｐｅｃｉｌａ Ｉｓｓｕｅ ｏｎ“Ｓｅｍａｎｔｉｃ Ｗｅｂ”， ２００３，１２（４）：３２０－３３２． ［２］ Ａｎ Ｈａｉ Ｄｏａｎ，Ｊａｙａｎｔ Ｍａｄｈａ￣，ａｌｌ，Ｒｏｂｉｎ １）ｈａｍａｎｋａｒ，ｅｔ ａ１． Ｌｃａｒｎｉｎｇ ｔｏ ｍａｔｃｌＪ ｏｎｔｏｌｏｇｉｅｓ ｏｎ ｔｉｌｅ ｓｅｍａｎｔｉｃ Ｗｅｂ［Ｊ］． Ｔｈｅ ＶＬＤＢ ＪｏｎｍａＩ，２００３，１２（４）：３０３．３１９． ［１３］关估红，虞为，安杨．ＧＭＬ模式匹配算法［Ｊ］．武汉大 学学报（信息科学版），２００４，２９（２）：１６９．１７５． （上接第３５页） 参考文献： 子工业出版社，２ｏｏ２． ［５］ Ｍａｒｃｏ Ｐｉｎｔｅｒ．Ｔｏｗａｒｄ ｍｏｒｅ ｒｅａｌｉｓｔｉｃ ｐａｔｈｆｉｎｄｉｎｇ［Ｊ］．Ｇａｍｅ Ｄｅｖｅｌｏｐｅｒ Ｍａｇａｚｉｎｅ（Ａｐｒｉｌ），ＣＭＰ Ｍｅｄｉａ ＬＬＣ，２００１：５４－ ６４． ［１］ Ｒｎｓｓｅｌｌ Ｓ，Ｎｏｌｖｉｇ Ｐ．Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ：Ａ Ｍｏｄｅｒｎ Ａｐ－ ｐｒｏａｅｈ（Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ）［Ｍ］．Ｐｅａｒｓｏｎ Ｅｄｎｃａｔｉｏｎ Ｐｒｅｎｔｉｃｅ Ｈａｌ１．２００３． ［６］ Ｃａｉｎ Ｔｉｍｏｔｈｙ．Ｐｒａｃｔｉｃａｌ Ｏｐｔｉｍｉｓａｔｉｏｎｓ ｆｏｒ Ａ‘Ｐａｔｈ Ｇｅｎｅｒａｔｉ ［２］Ｇｅｏｒｇｅ Ｆ Ｌｎｇｅｒ．Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ：Ｓｔｒｕｃｔｍ＇ｅｓ ａｎｄ Ｓｔｒａｔ． ｅｇｉｅｓ ｆｏｒ Ｃｏｍｐｌｅｘ Ｐｌ‘ｏｌ Ｊｌｅｍ ＳｏＭｎｇ（Ｆｏｕｒｔｈ Ｅｄｉｔｉｏｎ）［Ｍ］． Ａｄｄｉｓｏｎ Ｗｅｓｌｅｙ，ｌ ９９７． ｏｎ［ｚ］．ＡＩ Ｇａｍｅ Ｐｒｏｇｒａｍｍｉｎｇ Ｗｉｓｄｏｍ，Ｃｈａｒｌｅｓ Ｒｉｖｅｒ Ｍｅｄｉａ，２∞ｌ２：１４６—１５２． ［７］ 丁大正．Ｍａｔｈｅｍａｔｉｃａ ５在大学数学课程中的应用［Ｍ］． 北京：电子工业出版社，２００６． ［８］ Ｍａｔｔｈｅｗｓ Ｊａｍｅｓ．Ｂａｓｉｃ Ａ‘Ｐａｔｈ＿ｉｆｎｄｉｎｇ Ｍａｄｅ Ｓｉｍｐｌｅ［Ｚ］． ＡＩ Ｇａｍｅ Ｐｒｏｇｒａｍｍｉｎｇ Ｗｉｓｄｏｍ，Ｃｈａｒｌｅｓ Ｒｉｖｅｒ Ｍｅｄｉａ， ２０ｏ２：１０５．１ｌ３． ［３］Ｃｏｒｌｎａｎ．ｒ Ｈ，Ｌｅｉｓｅｌ ＳＯＩｌ Ｃ Ｅ， ｒｅｓｔ １ｔ Ｉ ，ｅｔ ａ１．１ｎｔｎ・ｏｄｌｌＣ． ｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ（Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ）ｆ Ｍ］．Ｔｈｅ ＭＩＴ Ｐｒｅｓｓ， ２０ｏ１． ［４］ Ｃｌｉｆｏｔ’ｄ Ａ Ｓｈｄｆｅｒ．Ｐｒａｃｔｉｃｅ ｌｎｔｒｏｄｕｃｔｉｏｌＪ ｔｏ Ｄａｔａ Ｓｔｒｕｃｔｕｒｅｓ ａｎｄ Ａｌｇｏｒｉｔｌｕｎ ＡｎａｌｙｓｉｓｆＭ］．张铭，刘晓丹，等译．北京：电