| 带多重选择的最短路问题:复杂性和算法 |
| |
| 引用本文： | 李帮义,姚恩瑜.带多重选择的最短路问题:复杂性和算法[J].数学杂志,2000,20(3):300-304. |
| |
| 作者姓名： | 李帮义 姚恩瑜 |
| |
| 作者单位： | 浙江大学应用数学系,杭州,310027 |
| |
| 基金项目： | 国家重点基础研究专项经费资助 |
| |
| 摘 要： | 本文提出了带出重选择的是短路问题，建立了该问题的数学模型，利用背包问题的一个变形问题－带限制选择的背包问题，证明了该问题是ＮＰ－Ｃ的，最后利用动态规则给出了一个伪多项式算法，其时间复杂性Ｏ（Ｃｈｍｎ），其中ｈ是最大的选择重数。
|
| 关 键 词： | 多重选择 最短路 算法 复杂性 网络优化 |
THE SHORTEST PATH PROBLEM WITH MULTIPLE CHOICE:COMPLEXITY AND ALGORITHM |
| |
| LI Bang-yi,YAO En-yu.THE SHORTEST PATH PROBLEM WITH MULTIPLE CHOICE:COMPLEXITY AND ALGORITHM[J].Journal of Mathematics,2000,20(3):300-304. |
| |
| Authors: | LI Bang-yi YAO En-yu |
| |
| Abstract: | In this paper,we put forward the concept of shortest path problem with multiple choice and give the formulation of this problem.By using a variation of (KP),it is proved that this problem is NP hard.Lastly,a psedopolynomial algorithm is given. |
| |
| Keywords: | Mutiple Choice Shortest Path Algorithm NP hard |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
