基于COM的启发式搜索算法库的设计与实现 |
| 时间：2011-04-23 作者：秩名 |
|
|
因此本库的接口分成两类：底层级接口IFunction和算法级接口IArithmetic。如图3所示。
图3 接口设计图
对于底层级接口，它是按照函数操作的对象分类，几乎所有算法都会对三个对象进行操作，一个是节点，一个是搜索图，另外一个就是路径，对于算法还设计的其他操作，都统一放在一个接口中。由于将算法分解以后，算法包含和操作的函数已经全部按照接口分类实现，并将这些接口放置到底层，那么就可以利用这些接口来实现算法库的算法。底层接口包括，INode接口 ：表示节点的扩展，存储节点优劣的信息，节点的比较信息；ISearchGraph接口：提供后继节点信息，以及根据搜索图判断哪些节点是不合适放在INodelist中，例如A*算法，有些节点扩展后，可能返回祖先节点继续搜索陷入循环；INodeList接口：主要表示表示节点优劣排序，搜索时候的路径安排及最优路径表示，是否为空判断，添加节点；IOther接口：主要包含一些对第三方的公共操作和判断。
而算法级接口顾名思义就是根据不同算法定义不同的接口，可以按照算法名来定义接口，如IAStarSearch、IAoStarSearch，及ICombatTreeSearch等等。这一层接口是面向普通用户，用户不需要做任何的添加和修改，可以直接调用使用算法。
3基于COM技术的启发式算法库的实现与应用
3.1 启发式算法库的实现
在算法库的底层实现中，主要实现的底层接口是基于三个对象的操作：节点，搜索图，链表。它们对应的接口是INode，ISearchGraph，以及IList。它们都是按通用数据结构建立，例如：INode的定义如下：
Interface INode //Node接口的定义
{UINT nodeId; //节点的编号
Type type; //该节点所处的算法类型，不同的算法，lParam不同，节点优劣比较也不同
LPARAM lParam;//根据type的不同，有不同的含义，一般表示结构体指针
void virtualCalculate();//计算节点的数值，通常填充lParam指向的数据结构。
……
};
InterfaceISearchGraph //SearchGraph接口的定义
{
voidAddNode(INode* pnd); //为搜索图添加一个节点
IListExpandNode(INode* pnd);//为节点扩展，并给出这次扩展后，节点的列表
BOOLIsInSearchGraph(INode* pnd);//节点是否存在与图中
……
};
Interface IList //List接口的定义
{
INode * GetFirst(); //取出列表的第一个元素
BOOL IsEmpty();//列表是否为空，主要用来判断是否结束
BOOLIsInList(INode* pnd);//判断节点是否属于列表
};
这是底层接口的定义，主要是以INode为中心。
对于每个算法，将其作为一个接口并用一个COM对象实现。
图4 组件库的实现结构框图
图4就是整个库的结构，这是一个多COM对象的COM组件。
3.2 启发式算法库的应用
算法库中的每个算法各自有各自的用途，例如：A*算法主要用在寻找路径中，主要用于游戏的开发，这里比较了著名的A*算法的应用在不使用本库和使用库的差别。这个例子可以参看文献[5]，这里调用A*算法只需要创建一个IAstarSearch接口，然后将数据文件名，起始点、结束点的编号，一个整型链表指针作为参数，如果调用成功，将在利list表中返回一个最短路径的list序列。
……
IAstarSearch*pIA;
hr =DllGetClassObject(CLSID_ALGORITHM, IID_IASTARSEARCH, &pIA);
if( hr == S_OK&& pIA)
hr=pIA->Run(“data.txt”,start,end,&m_list);
if hr == S_OK )
{
此时m_list包含节点的路径，可以使用最短路径进行操作了。
}
……
可以很明显的看出，调用过程只需几条语句，大大降低了开发的成本。
4结束语
本文实现了启发式搜索算法设计与具体应用领域无关，难于将多种数据结构的算法整合到一起等诸多问题。COM技术用于启发式搜索算法库有效的提高了算法库的通用性、扩展性，维护性。基于COM的启发式搜索算法库的实现满足了众多领域调用启发式搜索算法的需求，具有良好的应用价值。
参考文献:
[1 ] NilsJ.Nilsson. 人工智能[M].北京：机械工业出版社，2000.
[2 ] 潘爱民.COM原理与应用[M].北京：清华大学出版社，1999.
[3 ] 王伟,张波,殷赣华,等.基于技术的地图符号库结构设计与实现[J].武汉大学学报(信息科学版)，2002， 27(3):296～300.
[4 ] 夏永锋，曹元大.启发式搜索算法的面向对象设计实现[J]. 微机发展，2005，15（7）：11～13.
[5 ] Sunway. 深入A*算法. http://www.gameres.com/Articles/Program/Abstract/a8first_2.htm,2006,5.
[6 ] Mandow, L， Perez de la Cruz, J.L..Multicriteria heuristic search[J].European Journal of Operational Research，2003，150（2）：253-280.
[7 ] Zhou, Rong，Hansen, Eric A.Breadth-first heuristic search [J]. Artificial Intelligence,2006，170：385-408.
2/2 首页 上一页 1 2 |
|
|
|
