Hamming距离下的最短路逆问题  

Inverse shortest path problems under Hamming distance

作　　者：张斌武[1] 王勤[2] 

机构地区：[1]河海大学数理部,江苏常州213022 [2]中国计量学院理学院,浙江杭州310018

出　　处：《河海大学学报（自然科学版）》2008年第4期571-574,共4页Journal of Hohai University(Natural Sciences)

基　　金：国家自然科学基金(10601051)

摘　　要：针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.In consideration of the inverse shortest path problem under the Hamming distance, a property of an optimal solution of the problem is discussed, and a sufficient and necessary condition for feasible solution of the problem is given and proved. The problem is proved to be NP-hard by an instance that the polynomial of the knapsack problem is reduced to this problem. The result can provide a theoretical basis for designing approximation algorithms for this kind of problem.

关 键 词：HAMMING距离 最短路 NP困难 多项式归约 3-SAT问题 

分 类 号：O221[理学—运筹学与控制论]