哈明距离下1-重心问题的反问题

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (19): 39-41.

哈明距离下1-重心问题的反问题

白艳琴，王勤，吴龙树

中国计量学院理学院数学系，杭州 310018

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-01 发布日期:2011-07-01

Reverse 1-median problem under Hamming distance

BAI Yanqin，WANG Qin，WU Longshu

Department of Mathematics，School of Sciences，China Jiliang University，Hangzhou 310018，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-07-01 Published:2011-07-01

摘要/Abstract

摘要： 主要讨论哈明距离下网络中的1-重心问题的反问题。1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值，使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界。证明了在哈明距离下该问题是NP困难的。并运用动态规划的思想，在考虑改变顶点的权的情况下，对一般网络进行了求解。

关键词: 1-重心, 哈明距离, 反问题, 动态规划, NP困难

Abstract: This paper mainly discusses the reverse 1-median problem under the Hamming distance.The reverse 1-median problem is to reduce the overall sum of the weighted distances from the vertices to a given vertex by changing the parameters in a network such that it can satisfy a given budget，and the cost for changing the parameters is as small as possible.Under the hamming distance，it shows that this problem is NP-hard.By using dynamic programming method，this problem is solved in a general network by changing the weights of vertices.

Key words: 1-median, Hamming distance, reverse problem, dynamic programming, NP-hard

白艳琴，王勤，吴龙树. 哈明距离下1-重心问题的反问题[J]. 计算机工程与应用, 2011, 47(19): 39-41.

BAI Yanqin，WANG Qin，WU Longshu. Reverse 1-median problem under Hamming distance[J]. Computer Engineering and Applications, 2011, 47(19): 39-41.

[1]	周睿慜，李辉. 改进动态规划算法的移动机器人路径规划[J]. 计算机工程与应用, 2020, 56(21): 20-24.
[2]	陈俊杰，同淑荣，聂亚菲，张静文. 考虑胜任力水平的研发项目群人力资源调度[J]. 计算机工程与应用, 2019, 55(3): 209-218.
[3]	连玮. 采用树表示的全局最优形状匹配算法[J]. 计算机工程与应用, 2019, 55(1): 217-225.
[4]	张雨，崔耀东，梁泽华. 多尺寸圆木二维下料问题研究[J]. 计算机工程与应用, 2018, 54(19): 266-270.
[5]	肖红德. 最少钱币数量的计算与钱币面额的确定[J]. 计算机工程与应用, 2018, 54(16): 266-270.
[6]	孙培双，韩其睿. 彩色图像最优拼接线的改进算法研究[J]. 计算机工程与应用, 2016, 52(21): 218-221.
[7]	方刚1，张社民2. 三元统计语言模型对基因表达载体设计的优化[J]. 计算机工程与应用, 2016, 52(15): 60-64.
[8]	张新功，王慧，柏世坤. 最小化误工工件个数的两代理单机排序问题[J]. 计算机工程与应用, 2016, 52(14): 32-36.
[9]	李惠光，李峰，邵暖，沙晓鹏，王帅. 基于图像分割和控制点的立体匹配算法研究[J]. 计算机工程与应用, 2015, 51(23): 160-163.
[10]	张昱，徐洪泽，陈建强，张鹿宁. 冶金企业内部铁路进路控制优化策略研究[J]. 计算机工程与应用, 2015, 51(17): 250-254.
[11]	沈璐1，2，纪允1，纪冬宝3，李萍4. 带可变长度通配符的模式匹配算法[J]. 计算机工程与应用, 2015, 51(15): 43-47.
[12]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.
[13]	王君. 模糊时间窗VRP的动态规划和禁忌搜索混合算法[J]. 计算机工程与应用, 2014, 50(24): 58-64.
[14]	赵旭，王伟. 动态规划理论在DSAMDP方法中的优化研究[J]. 计算机工程与应用, 2014, 50(22): 83-87.
[15]	曾强1，沈玲2，吴立云1，兰建义1. 一种改进的综合生产计划动态规划优化方法[J]. 计算机工程与应用, 2014, 50(21): 248-253.