摘要
与或图搜索是人工智能领域一项重要的问题求解技术。基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模。在无圈与或图符号OBDD表示的基础上,给出了一种求解无圈与或图最小代价解图的符号搜索算法。实验结果表明,与AO*算法相比,该算法可处理问题的规模有较大的提高。
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 symbolic representation of acyclic AND/OR graph using OBDD(ordered binary decision diagram), we proposed a novel symbolic algorithm for searching minimalcost solution graph of acyclic AND/OR graph. It is shown that the symbolic algorithm has lower space complexity and can be used to handle larger-scale acyclic AND/OR graphs.
出处
《计算机科学》
CSCD
北大核心
2010年第7期169-173,共5页
Computer Science
基金
国家自然科学基金(60803033
60663005)
广西青年科学基金(桂科青0728093
桂科青0542036)资助