欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
针对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.
同期刊论文项目
同项目期刊论文
位置：