| 一种生成直角斯坦纳树的算法 |
| |
| 引用本文： | 蒋君伟,唐璞山.一种生成直角斯坦纳树的算法[J].复旦学报(自然科学版),1986(3). |
| |
| 作者姓名： | 蒋君伟 唐璞山 |
| |
| 作者单位： | 复旦大学电子工程系，复旦大学电子工程系 八四级硕士研究生. |
| |
| 摘 要： | 构造最优化的直角斯坦纳树(RST)是一个NP完全问题。为了解决实际问题,本文提出一种采用回路检查的算法,构造出优化程度很高的直角斯坦纳树。对于以前文献中以及已经运算过的任意构造的例子,达到了最优或接近最优的结果。
|
| 关 键 词： | 最优化 NP-完全问题 回路 路径 |
AN ALGORITHM FOR RECTILINEAR STEINER TREE |
| |
| Jiang Junwei,Tang Pushan.AN ALGORITHM FOR RECTILINEAR STEINER TREE[J].Journal of Fudan University(Natural Science),1986(3). |
| |
| Authors: | Jiang Junwei Tang Pushan |
| |
| Institution: | Electronics Engineering Department |
| |
| Abstract: | It is proved that the problem of constructing an optimal Eectilinear Steiner Tree (RST) is NP-complete. For solving practical problems, a new algorithm using a loopcheck method is proposed here by constructing a RST whose optimization is excellent. For some examples given in the literature papers and some arbitrary constructed examples, the results of the algorithm are optimal or suboptimal. |
| |
| Keywords: | optimal NP-problem loop path |
| 本文献已被 CNKI 等数据库收录！ |
