Hamming距离下的最短路逆问题

针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.

Inverse shortest path problems under Hamming distance

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.