网络最大流问题求解的代数决策图（ADD）技术

Hachtel G．D．和Somenzi F．提出的0-1网络最大流问题的符号有序二叉决策图(OBDD)算法在一定程度上缓减了“状态爆炸”问题，但算法仅局限于求解0-1网络的最大流。Bachar R．I．等提出的代数决策图(ADD)数据结构，是描述伪布尔函数和有限域取值函数的一种有效技术。文中利用ADD存储表示网络及描述网络最大流问题，给出一种求解网络最大流问题的符号ADD技术新思路。实验结果说明了应用ADD技术求解一般网络最大流问题的有效性，可处理0-1网络最大流问题的符号OBDD算法无法处理的非0-1网络。     

赋时Petri网的一种符号分析算法

有序二叉决策图(Ordered Binary Decision Disgram-OBDD)是布尔函数表示的规范型,布尔函数的复杂运算可以基于OBDD得到极大地简化实现.在讨论基于OBDD的有界Petri网符号分析算法的基础上,对赋时位置Petri网的符号分析进行了研究,构造了一种扩展标识向量,给出了赋时Petri网分析的一种符号OBDD算法,实现了赋时Petri网的隐式描述与分析.实验表明,符号算法能处理较大规模赋时Petri网问题.     

约束满足问题求解的符号OBDD技术

约束满足问题(CSP)是人工智能中一个重要的研究课题.通过讨论CSP的有序二叉决策图(OBDD)描述,给出了CSP的符号OBDD求解算法.其算法是在CSP的符号表示的基础上,首先对CSP中的所有变量根据其在约束图中的度的大小进行递增排序,然后按照此变量序将CSP分成n个子问题分别进行求解,其中n为CSP中变量数,最后利用OBDD的"与"操作合并所有子问题,所得的OBDD即为满足所有约束的CSP的所有解.通过与桶消元算法和符号OBDD直接求解算法的实验对比,证明本算法具有明显的优越性.     

赋时Petri网的一种符号分析算法

有序二叉决策图（0rdered Binary Decision Disgram-OBDD）是布尔函数表示的规范型，布尔函数的复杂运算可以基于OBDD得到极大地简化实现。在讨论基于OBDD的有界Petri网符号分析算法的基础上，对赋时位置Petri网的符号分析进行了研究，构造了一种扩展标识向量，给出了赋时Petri网分析的一种符号OBDD算法，实现了赋时Petri网的隐式描述与分析。实验表明，符号算法能处理较大规模赋时Petri网问题。     

一种基于OBDD的WSN可靠性评估方法

为评估组播下WSN可靠性,基于有序二叉决策图(OBDD)提出符号OBDD_Multicast算法。该算法在WSN符号OBDD表示的基础上,对WSN的节点变量进行排序,通过节点扩展,利用OBDD的"与"和"或"操作构建组播下WSN可靠性函数的OBDD。OBDD_Multicast算法通过识别相邻节点冗余路径和s-t非连通冗余路径,避免冗余扩展,减少扩展过程中中间子网的数目,有效降低了可靠性分析的复杂性。实验结果表明,针对3×N型网络,OBDD_Multicast算法比Shrestha的OBDD算法耗时少、效率高。     

二部图最大权匹配的符号ADD算法

利用代数决策图ADD数据结构,在KM算法基础上,提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念,将传统的匹配选择转化成布尔运算,"并行"地搜索匹配集合。实验结果表明:与传统算法相比,该算法可以改善问题的状态空间复杂度。     

二部图最大权匹配的符号ADD算法

利用代数决策图ADD数据结构，在KM算法基础上，提出了一种二部图最大权匹配的符号ADD算法。该算法引入优先函数概念，将传统的匹配选择转化成布尔运算，“并行”地搜索匹配集合。实验结果表明：与传统算法相比，该算法可以改善问题的状态空间复杂度。     

一种基于代数决策图的多值图像无损压缩方法

代数决策图(ADD)是布尔函数的一种简洁紧凑的符号描述方法.用ADD对多值图像进行建模,可以有效降低数据冗余,然后对ADD模型进行有效的编码,可以达到数据压缩的目的.实验结果显示本方法的压缩比高于游程编码、哈夫曼编码,较LZ77编码也有一定优势.     

基于赋时Petri网的装配序列规划符号求解

赋时Petri网非常适合装配序列规划问题的建模,然而组合复杂性严重制约了基于赋时Pefri网模型的装配序列规划问题的求解规模.OBDD能为Petri网的状态空间及装配序列规划过程中的数据提供符号表示,并在规划过程中实现隐式操作,有效地缓解了组合复杂性.通过将赋时Petri网中的赋时迁移用等价的赋时迁移结构代替,赋时Petri网转换为等价的普通Petri网,基于此提出符号有序二叉决策图OBDD装配序列规划算法,求解最优装配序列.     

基于OBDD的εL^（￢）本体判定算法

有序二叉决策图(OBDD)是一种新型的数据结构,在较大状态空间规模的模型检测和验证等领域中,已经得到了成功应用,并且在逻辑公式的可满足性判定方面也具有巨大的应用潜力.通过采用OBDD实现了描述逻辑εL(一)判定算法.以基于OBDD的SHIQ判定算法为基础,针对描述逻辑εL(一)进行了优化,应用标准化规则取代了FLAT规则,重构了知识库模型,进而将该模型转化为满足3CNF(每个从句含有3个变元的合取形式)约束的布尔函数并利用OBDD进行可满足性判定,并以实例对算法过程进行了演示.     

基于OBDD的装配序列自动推理技术研究

根据从CAD系统中直接获得的产品装配模型的数据,来建立基于OBDD的装配体模型。采用OBDD的符号操作对装配操作的可能性和有效性进行了验证,实现了可行装配序列推理的自动化。通过对例子的分析,表明基于OBDD的装配序列自动推理技术是可行和正确的,它为装配体的装配序列的推理提供了一种切实可行的新方法。     

基于 OBDD 的描述逻辑 ALC判定算法

针对描述逻辑 ALC的经典判定算法在处理大规模问题上的不足,而 OBDD 对于处理大规模问题有高效性,给出了一种基于 OBDD 的 ALC判定算法并证明正确性.该算法根据 ALC 的概念的形式,计算所有子概念和每个子概念的否定形式的集合,然后根据该集合里的每个概念的形式构造出其相应的布尔函数,将布尔函数转化为 OBDD 的表示形式来进行概念的可满足性判定.     

基于OBDD的描述逻辑SHOIQ判定算法研究与实现

描述逻辑是语义Web的逻辑基础,已成为当前计算机科学和人工智能研究的热点.鉴于描述逻辑SHOIQ的经典判定算法在处理大规模问题上的不足,以OBDD能很好处理大规模问题为基础,给出了一种基于OBDD的SHOIQ判定算法.该算法利用相关规则和技术将SHOIQ知识库转化为OBDD,在此基础上进行SHOIQ知识库的一致性判定....     

一种新的基于OBDD的装配序列推理方法

根据机械装配序列推理的特点,对PADL-2提供的CAD模型数据进行简化处理,再结合有序二叉决策图(OBDD-Ordered Binary Decision Diagram),建立了一种新的装配体模型.基于此模型,可以通过一系列的OBDD符号运算完成装配操作的可行性判断,从而实现了装配序列的推理.这种推理方法容易实现计算机化和自动化,是对文献[6]中推理方法的一种改进.通过对实例的实现和分析证明了该方法是切实可行的.     

混合噪声下移动受限水声传感器网络自定位算法

现有的水声传感器网络定位算法需要信标节点辅助定位,测距噪声服从高斯分布,定位成本高,精度低,对此,提出一种混合测距噪声下基于最大后验概率的自定位算法. 首先对受限移动节点的移动模式进行建模以获取节点位置的先验信息,测量节点间距离并基于加性和乘性混合噪声构建似然函数,在贝叶斯框架下将节点位置的先验与似然信息进行融合,通过最大化后验概率得到定位目标函数;然后利用BFGS拟牛顿法对目标函数进行优化求解. 仿真结果表明,相比同类定位方法,所提方法无需信标节点,定位精度高,收敛速度快,且对测距噪声的变化具有鲁棒性.     

一种公平的路边基站下行业务调度算法

To improve the fairness performance of the downlink traffic scheduling algorithm, a network flow based downlink traffic scheduling algorithm is proposed for the roadside unit (RSU) in vehicular networks. In the proposed algorithm, a bipartite graph is constructed firstly, where the node set is composed by the vehicle set and the timeslot set. At any given timeslot if a vehicle can communicate with the RSU, then an edge between the given timeslot and that vehicle is added into the edge set. Next, a flow network graph is constructed based on the bipartite graph by adding a virtual source node and a virtual sink node. By applying the conventional minimum cost maximum flow algorithms, a minimum cost maximum flow can be computed, which is converted to the fair traffic scheduling strategy. Simulation results show that, when the total vehicle requirements are maximized, compared with the existing algorithms, the fairness performance of the proposed algorithm is improved by 116.4％ in the offline case, and by 25.9％ in the online case.     

拥堵路网交通流均衡分配模型

为克服利用传统静态交通流分配模型分析拥堵道路网络交通流分配问题的不足,研究交通拥堵状态下静态拥堵交通流均衡分配模型.首先,基于拥堵路段上交通流特征,分析拥堵路段阻抗函数特点,包括满足拥堵路段上流量随车辆数增加而减少的特征;其次,分析拥堵状态下用户疏解路径选择行为,提出道路网静态拥堵交通流分配的用户均衡与系统最优原理;再次,构建道路网静态拥堵交通流用户均衡与系统最优分配模型,并证明模型与用户均衡原理的等价性、模型解的唯一性;最后,给出求解用户均衡模型的迭代加权求解算法.通过算例与传统静态交通流分配进行对比分析,结果表明:拥堵用户均衡分配模型与拥堵系统最优分配模型可以合理描述拥堵用户均衡原理与系统最优均衡原理,且拥堵用户均衡分配模型可以合理描述路网处于全拥堵状态下各路段实际通过流量.拥堵交通流分配模型可应用于由拥堵蔓延导致的局部全拥堵区域,可作为半拥堵静态交通流分配的核心部分之一.     

WSN聚合数据率约束最大生命期路由

无线传感器网络通常由能量受限的传感器节点以及一个数据中心构成,采用数据聚合消除数据中的冗余信息.针对目前还没有对网络生命期与聚合数据率之间约束关系的研究,提出了适用于数据聚合无线传感器的网络流模型,并通过定义聚合数据率松弛系数,将网络最大生命期与最小聚合数据率路由结合起来,并设计了一组线性规划问题消除路由中的环路.通过...