论文导读：启发式搜索是要求把解决问题具体领域的知识加进搜索算法中，控制搜索过程，以提高算法效率的搜索方法。COM(Component Object Model，组件对象模型)，是一种以组件为发布单元的对象模型，这种模型使各软件组件可以用一种统一的方式交互。由于COM是语言无关的，所以利用COM技术建立的算法库组件也是通用的。
关键词：COM,启发式搜索,算法库
思想来设计库，使算法的开发者也能利用本文提供的COM组件，来高效开发算法。
1启发式搜索与COM技术
1.1 启发式搜索
启发式搜索是要求把解决问题具体领域的知识加进搜索算法中，控制搜索过程，以提高算法效率的搜索方法。启发信息按其用途可分为下列3种：(1) 用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。(2) 在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。(3)用于决定某些应该从搜索树中抛弃或修剪的节点。论文检测。
1.2 COM技术
COM(Component Object Model，组件对象模型)，是一种以组件为发布单元的对象模型，这种模型使各软件组件可以用一种统一的方式交互。COM既提供了组件之间进行交互的规范，也提供了交互的环境。COM技术是由面向对象技术发展起来，COM技术目前也是解决软件危机的一种有效的方法，COM技术也可以认为是一种软件设计的分析方法或框架。由于COM组件是以二进制形式发布，所以在Win32平台下，它是语言无关的。COM组件是可扩展的，通过使用聚合和包容技术可以扩展COM组件的功能，使其支持更多的应用。同时COM组件又是地域无关的，可以通过网络访问远程的COM组件，达到一种分布式应用。
1.3 COM技术与启发式搜索算法
由于COM是语言无关的，所以利用COM技术建立的算法库组件也是通用的。COM又是可扩展的，只要经过良好的设计和规划，算法开发者可以利用包容和聚合技术实现COM组件的功能扩展，又由于对于搜索算法来说，往往计算量是很大的，利用COM技术提供的分布式计算能力，可以很容易实现算法的分布式计算。这样充分利用了网络上的计算机资源。
2基于COM的启发式搜索算法库的设计
2.1 启发式搜索算法的分析
目前各种启发式搜索算法变体很多，即使是完全不同的算法，也或多或少存在某些方面的相似性。由于这种特性，本文不是直接一个一个算法的实现，而是利用模型化的方法对整个算法库建模。对算法库建模即是对这些算法进行建模，找出一种分析算法的方案。
这里以A*算法和博弈树算法为例。观察这两个算法可以发现，A*算法和博弈树算法，其组成元素是（1）open表（2）closed表。对应的主要操作是：（1）循环的从open表中拿出一个节点放入closed表中；（2）判断结束状态是依赖于当时open表和closed表的状态；（3）还有一个操作是比较。它们不同之处就是一个A*算法往往对排序使用的是启发式函数和博弈树算法使用的直接估计节点的倒推值评估是不同的形式的。论文检测。
其实这些相视之处不仅存在A*和博弈树算法中，其他启发式搜索算法也都有这些相似之处。因此在设计启发式搜索算法时，可以采用统一的数据结构来实现open表和closed表，以及提取它们共有的操作，如循环从open表中取一个元素到closed中等等。分析得到，在启发式搜索算法中公有的部分为：（1）open表和closed表的数据结构；（2）节点的扩展；（3）中间节点的数据结构；（4）启发式函数的函数指针；（5）各过程的对外接口。
2.2 启发式算法库的设计
基于以上分析，可以将一系列的启发式搜索算法的进一步抽象、分类，提取算法的共性和差异性，把算法涉及的过程、操作，以及它们所使用的数据结构做统一和抽象，利用这种统一性，建立一个通用的底层函数接口集合，这样可以使用最少或者很少的代码实现整个启发式搜索算法库。本文对算法库的实现过程遵循以下操作，如图1所示。
（1）统一算法描述
（2）算法拆分成各个元素
（3）分析各元素之间的相似性和抽象出公共部分。
（4）设计通用方法实现多数元素的共性，对算法元素的异性单独实现。
（5）定义元素的函数实现和通用型数据结构实现。
（6）将函数按操作对象分类定义成基本接口。
（7）在这些基本接口之上，建立算法库。
 图1 算法库解析图
对于整个启发式搜索算法而言，如图2所示底层主要实现公用的函数接口和公共的类接口，主要为第二层启发式搜索算法库的实现提供服务。但是由于这里实现的算法库只是大量搜索算法的一个小的集合，不可能涵盖所有搜索算法，所以将底层的函数和类接口公开，为以后开发者开发适应自己需求的启发式搜索函数提供一些帮助，使其更高效的开发，同时其成果也能为更高一层的开发者使用，这样极大程度提高了库的实用性，以及软件的复用性。同时这些接口不光可以给库的开发者使用，也可以给更高一级的启发式搜索算法的调用者使用。集合提供公共操作及相关的数据结构，当然，由于目前实现的库只能包含一定量的算法，为了将来维护这个算法库，这里将这些底层接口同时也提供给第三方使用，使其可以扩展启发式算法算法库，让其中包含更多的启发式搜索算法，或其他的搜索算法。
图2 整个算法库的结构图
2.3 COM接口的设计
接口是COM组件的基本构成单位，接口的设计直接影响着库的设计和使用。根据在库的设计所提到的，为了增加扩展性，库设计完成后，并不将内部实现的中间函数关闭，而是将这些函数做成通用的函数向外提供接口，以使算法的开发者便于开发自己的算法，并让开发者利用聚合或者包容技术扩展本文的算法构件库。在本库中结构分配原则是基层接口分配到一个组件中，每个算法都实现成为带一个接口的COM对象。这样设计是基于COM组件的内存模型，因为一旦调用COM对象的一个接口，必然将整个COM对象加载，对象过大将会占据很大的内存块，通常基层接口是所有算法接口都要调用的，而算法类接口，往往一个应用程序不会每次访问所有的算法，所以如果把所有算法放在一个组件中，必然带来每次加载内存过大，导致系统运行效率降低。论文检测。
1/2 1 2 下一页 尾页 |
