| 网络上的最优干线选择问题 |
| |
| 引用本文： | 刘林.网络上的最优干线选择问题[J].郑州大学学报(理学版),2007,39(4):22-25. |
| |
| 作者姓名： | 刘林 |
| |
| 作者单位： | 郑州航空工业管理学院数理系,郑州,450015 |
| |
| 摘 要： | 考虑在网络上点到路的距离意义下的最优干线选择问题——最小加权距离和问题和最小最大加权距离问题.首先证明所讨论的两个问题的判定形式是NP-完全的,然后对于网络是树的情况,给出了求解问题的算法,该算法的复杂性是O(n2).
|
| 关 键 词： | 网络选址 点-路距离 算法复杂性 多项式算法 |
| 文章编号： | 1671-6841（2007）04-0022-04 |
| 收稿时间： | 2006-11-27 |
| 修稿时间： | 2006年11月27 |
The Problems of Selecting an Optimal Path on Network |
| |
| LIU Lin.The Problems of Selecting an Optimal Path on Network[J].Journal of Zhengzhou University:Natural Science Edition,2007,39(4):22-25. |
| |
| Authors: | LIU Lin |
| |
| Abstract: | Selecting an optimal path on network is considered.One problem is to determine a path on the network to minimize the total weighted distance and the other problem is to determine a path on the network to minimize the maximum weighted distance from it to n given points of the network.It is proved that the two problems are NP-complete.When the network is a tree,problems are solved by polynomial-time algorithm,and this algorithm complexity is O(n2). |
| |
| Keywords: | network location point-path distance algorithm complexity polynomial algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
