|
|||||
|
|
| 求解Hamming距离下的最短路改进问题的一个近似算法 | |
| 引用本文： | 张斌武,王勤,余维燕.求解Hamming距离下的最短路改进问题的一个近似算法[J].兰州理工大学学报,2008,34(4). |
| 作者姓名： | 张斌武 王勤 余维燕 |
| 作者单位： | 1. 河海大学,常州校区数理部,江苏,常州,213022 2. 中国计量学院,理学院数学系,浙江,杭州,310018 3. 新疆大学,数学与系统科学学院,新疆,乌鲁木齐,830046 |
| 摘 要： | 研究Hamming距离下的最短路改进问题的性质,并给出一个求解Hamming距离下的最短路改进问题的近似算法:按照一定规则得到满足一定条件的树型图,求解相应的0-1整数规划问题.该研究有助于设计求解Hamming距离下的最短路改进问题的有效的近似算法. |
| 关 键 词： | Hamming距离 最短路改进问题 NP-困难 近似算法 |
An approximation algorithm for solving shortest path improvement problem under Hamming distance |
|
| ZHANG Bin-wu,WANG Qin,YU Wei-yan.An approximation algorithm for solving shortest path improvement problem under Hamming distance[J].Journal of Lanzhou University of Technology,2008,34(4). | |
| Authors: | ZHANG Bin-wu WANG Qin YU Wei-yan |
| Abstract: | 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. |
| Keywords: | Hamming distance shortest path improvement problem NP-hardness approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |