求解Hamming距离下的最短路改进问题的一个近似算法  

An approximation algorithm for solving shortest path improvement problem under Hamming distance

作　　者：张斌武[1] 王勤[2] 余维燕[3] 

机构地区：[1]河海大学常州校区数理部,江苏常州213022 [2]中国计量学院理学院数学系,浙江杭州310018 [3]新疆大学数学与系统科学学院,新疆乌鲁木齐830046

出　　处：《兰州理工大学学报》2008年第4期98-100,共3页Journal of Lanzhou University of Technology

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

摘　　要：研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法.The properties of the shortest path improvement problem under Hamming distance was investigated, and an approximation algorithm for solving this problem was given, where a tree diagram which met definite conditions was obtained according to definite rules and, then, the corresponding programming problem with integers 0-1. It was expected that the investigation in this paper could be useful for devising more efficient approximation algorithms for solving the shortest path improvement problems under Hamming distance.

关 键 词：HAMMING距离 最短路改进问题 NP-困难 近似算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] O221[自动化与计算机技术—计算机科学与技术]