摘要
Hachtel G.D.和 Somenzi F.提出的 0 - 1网络最大流问题的符号有序二叉决策图 (OBDD)算法在一定程度上缓减了“状态爆炸”问题 ,但算法仅局限于求解 0 - 1网络的最大流。Bachar R.I.等提出的代数决策图 (ADD)数据结构 ,是描述伪布尔函数和有限域取值函数的一种有效技术。文中利用 ADD存储表示网络及描述网络最大流问题 ,给出一种求解网络最大流问题的符号 ADD技术新思路。实验结果说明了应用 ADD技术求解一般网络最大流问题的有效性 ,可处理 0 - 1网络最大流问题的符号 OBDD算法无法处理的非 0 - 1网络。
A symbolic ordered binary decision diagram(OBDD)algorithm for the maximum flow in0-1networks proposed by Hachtel G.D.and Somenzi F.could reduce the state explosion to some extent.However,this algorithm is confined to the solution of the maximum flow in0-1networks.Algebraic Decision Diagram proposed by Bachar R.I.is a new efficient approach to representation of pseudo-Boolean function and finite domain function.In this paper,the authors use ADD to represent networks and the maximum flow problems,and give a new idea of solving the maximum flow in general networks.The results show that the effectiveness of an ADD-based technique for the maximum flow in networks can handle problems that the symbolic OBDD algorithm for maximum flow in0-1networks can't.
出处
《桂林电子工业学院学报》
2004年第3期54-57,共4页
Journal of Guilin Institute of Electronic Technology
