计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
19期
39-41
,共3页
1-重心%哈明距离%反问题%动态规划%NP困难
1-重心%哈明距離%反問題%動態規劃%NP睏難
1-중심%합명거리%반문제%동태규화%NP곤난
主要讨论哈明距离下网络中的1-重心问题的反问题.1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其他顶点的加权距离之和不超过一个给定的上界.证明了在哈明距离下该问题是NP困难的.并运用动态规划的思想,在考虑改变顶点的权的情况下,对一般网络进行了求解.
主要討論哈明距離下網絡中的1-重心問題的反問題.1-重心問題的反問題主要研究如何儘可能少地改變網絡中的參數值,使得給定的頂點到其他頂點的加權距離之和不超過一箇給定的上界.證明瞭在哈明距離下該問題是NP睏難的.併運用動態規劃的思想,在攷慮改變頂點的權的情況下,對一般網絡進行瞭求解.
주요토론합명거리하망락중적1-중심문제적반문제.1-중심문제적반문제주요연구여하진가능소지개변망락중적삼수치,사득급정적정점도기타정점적가권거리지화불초과일개급정적상계.증명료재합명거리하해문제시NP곤난적.병운용동태규화적사상,재고필개변정점적권적정황하,대일반망락진행료구해.
