| 网络最大流问题求解的代数决策图(ADD)技术 |
| |
| 引用本文： | 徐周波,古天龙.网络最大流问题求解的代数决策图(ADD)技术[J].桂林电子科技大学学报,2004,24(3):54-57. |
| |
| 作者姓名： | 徐周波 古天龙 |
| |
| 作者单位： | 1. 桂林电子工业学院,计算机系,广西,桂林,541004
2. 桂林电子工业学院,学院办公室,广西,桂林,541004 |
| |
| 摘 要： | Hachtel G.D.和 Somenzi F.提出的 0 - 1网络最大流问题的符号有序二叉决策图 (OBDD)算法在一定程度上缓减了“状态爆炸”问题 ,但算法仅局限于求解 0 - 1网络的最大流。Bachar R.I.等提出的代数决策图 (ADD)数据结构 ,是描述伪布尔函数和有限域取值函数的一种有效技术。文中利用 ADD存储表示网络及描述网络最大流问题 ,给出一种求解网络最大流问题的符号 ADD技术新思路。实验结果说明了应用 ADD技术求解一般网络最大流问题的有效性 ,可处理 0 - 1网络最大流问题的符号 OBDD算法无法处理的非 0 - 1网络。
|
| 关 键 词： | 符号算法 最大流 代数决策图(ADD) |
| 文章编号： | 1001-7437(2004)03-54-04 |
| 修稿时间： | 2004年3月9日 |
An ADD-based Technique for the Maximum Flow in Networks |
| |
| XU Zhou-bo ,GU Tian-long.An ADD-based Technique for the Maximum Flow in Networks[J].Journal of Guilin Institute of Electronic Technology,2004,24(3):54-57. |
| |
| Authors: | XU Zhou-bo GU Tian-long |
| |
| Affiliation: | XU Zhou-bo 1,GU Tian-long 2 |
| |
| Abstract: | 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. |
| |
| Keywords: | symbolic algorithms maximum flow algebraic decision diagram |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
