| 基于OBDD的含圈与或图搜索算法研究* |
| |
| 引用本文： | 赵岭忠,王雪松b.基于OBDD的含圈与或图搜索算法研究*[J].计算机应用研究,2011,28(4):1325-1329. |
| |
| 作者姓名： | 赵岭忠 王雪松b |
| |
| 作者单位： | 1. 桂林电子科技大学计算机科学与工程学院,广西,桂林,541004
2. 桂林电子科技大学电子工程与自动化学院,广西,桂林,541004 |
| |
| 基金项目： | 国家自然科学基金资助项目 |
| |
| 摘 要： | 与或图搜索是人工智能领域一项一定范围内通用的问题求解技术。基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模。本文在Mahanti等提出的含圈与或图理论框架基础上，给出了基于OBDD的含圈与或图符号表示方法，并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明：该算法在处理大规模含圈与或图时具有明显优势。
|
| 关 键 词： | 含圈与或图 最大可扩展子图 最小代价解图 有序二叉决策图 |
| 收稿时间： | 9/26/2010 3:17:48 PM |
| 修稿时间： | 2010/10/26 0:00:00 |
OBDD based symbolic algorithm for searching cyclic AND/OR graphs |
| |
| ZHAO Ling-zhong,WANG Xue-songb.OBDD based symbolic algorithm for searching cyclic AND/OR graphs[J].Application Research of Computers,2011,28(4):1325-1329. |
| |
| Authors: | ZHAO Ling-zhong WANG Xue-songb |
| |
| Affiliation: | (School of Management, Dalian University of Technology, Dalian Liaoning 116023, China) |
| |
| Abstract: | Searching AND/OR graph is an important problem-solving technique in the area of artificial intelligence. The representation of AND/OR graph based on traditional data structures greatly limits the scale of the graph that could be handled with existing AND/OR graph searching algorithm. Based on the framework for searching cyclic AND/OR graph proposed by Mahanti et al., an OBDD based representation of cyclic AND/OR graphs is proposed, on which a symbolic algorithm is formulated for searching minimal-cost solution graph of cyclic AND/OR graphs. It is shown that the algorithm has significant advantage over traditional algorithms in handling larger-scale cyclic AND/OR graphs. |
| |
| Keywords: | cyclic AND/OR graph minimal-cost solution graph OBDD |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
