摘要
现实世界中的复杂问题通常具有网状结构,对于此类问题的求解,常用的方法均将其转换为基于对该问题的序列结构或者树形结构描述,但复杂问题的网状结构不能简单的用序列或者树表示.为了准确描述复杂网状问题的结构,便于对问题求解,提出保序性与或图形式对其进行描述.该模型具有树形结构的分层关系,节点间存在与关系和或关系,特别强调同一节点的子节点间存在序关系.基于该模型的问题求解方法有别于常用的与或图求解算法,利用商空间理论的粒度变换方法,采用多粒度模型来求解保序性与或图.给出了基于结构描述的网状问题求解算法,以及算法的具体应用实例,并通过和传统树形搜索算法的对比,证明了算法的高效性.
Complex problems exist widely in daily life,such as crosswords,auto planning problems,maximum network flow problems,limited resource allocation problems,and disassembling and recycling of productions.Those problems are non-linear and the solving process is based on the complicated internal structure.So the description of this kind of problems seriously affects its solving process.The order relationships among sub-problems are self structure of problem which is netted.Given a original problem A,and sub-problems {ai｜i=1,…,n}.Let V={ai｜i=1,…,n}.If sub-problem ai is related to aj,let（ai,aj）∈E,so E={eij｜（ai,aj）,i,j∈{1,…,n}}.The graph G=（V,E）is called netted graph.The structure of netted graph is named as netted structure and problems with netted structure are netted problems.At present,the solving methods of those problems presented by netted graph are based on sequence structural description or tree structural description.The solution of sequence structure is searching a path through the traversal of graph,which take account of single order relationship.Tree structure is hierarchical,and state graph searching can get a solution tree which contains all paths.The transformation from graph to simple sequence or tree changes the original structure of problem.Particularly,the order relationships among the siblings are lost.Or the hierarchy which not exists in netted structure is defined in tree,and then the real structure information is changed.In this paper,the structure of netted problem is described by ordered AND/OR Graph according to its internal constraint conditions.This kind of graph has the hierarchy of tree structure,as well as nodes in graph have AND relation and OR relation.More importantly,among the siblings there exits original order relationships.That is the reason this kind graph is called Ordered AND/OR Graph.The graph is searched by Multi-granular Model which is put forward based on granular transaction of the Quotient Space Theory.Multi-granular Model projects the problem into different quotient spaces that make up the different gain-size words of the original problem.The problem can be solved in suitable gain-size space.Actually,the netted problem solving algorithm based on structure description is raised.In this paper,an applicable example is given and experiment contrasting with traditional tree searching method shows that this algorithm is efficient.
出处
《南京大学学报（自然科学版）》
CAS
CSCD
北大核心
2013年第2期235-243,共9页
Journal of Nanjing University（Natural Science）
基金
国家重点基础研究发展计划(2007CB311003)
国家自然科学基金(61073117
61175046)
安徽省自然科学基金(11040606M145)
高等学校省级优秀青年人才基金(2010SQRL021)
安徽大学青年科研基金(KJQN1118)
关键词
网状问题
结构化描述
保序性与或图
netted problem
structural description
ordered AND/OR graph
