| 哈明距离下的最短路反问题 |
| |
| 引用本文： | 陈志民.哈明距离下的最短路反问题[J].长春师范学院学报,2007,26(2):24-26. |
| |
| 作者姓名： | 陈志民 |
| |
| 作者单位： | 杭州职业技术学院,浙江杭州310018 |
| |
| 摘 要： | 反优化问题是指修改给定的参数，使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题：通过修改给定网络上弧的长度，使得修改后网络中指定点之间的最短路长度不超过给定的常数，而其中修改费用是用哈明距离来衡量的，我们证明了哈明距离下的最短路反问题是强NP-完全的。
|
| 关 键 词： | 最短路 反问题 计算复杂性 |
| 文章编号： | 1008-178X（2007）02-0024-03 |
| 修稿时间： | 2006-11-15 |
The Reverse Problem of Shortest Path under the Hamming Distance |
| |
| CHEN Zhi-min.The Reverse Problem of Shortest Path under the Hamming Distance[J].Journal of Changchun Teachers College,2007,26(2):24-26. |
| |
| Authors: | CHEN Zhi-min |
| |
| Institution: | Hangzhou Vocational Technical College,Hangzhou 310018,China |
| |
| Abstract: | The reverse optimization problem is to modify the parameter so that the optimal solution meets some given constraint.In this paper,we consider the reverse problem of shortest path under the Hamming distance: modify the length of the arcs so that the shortest path between the given nodes is not more than a given constant,and the modification cost is measured by Hamming distance.We show that this problem is strongly NP-complete. |
| |
| Keywords: | Shortest path Reverse problem computational complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
