数学的实践与认识
數學的實踐與認識
수학적실천여인식
MATHEMATICS IN PRACTICE AND THEORY
2011年
13期
113-118
,共6页
1-重心%哈明距离%反问题%动态规划%NP困难
1-重心%哈明距離%反問題%動態規劃%NP睏難
1-중심%합명거리%반문제%동태규화%NP곤난
主要讨论哈明距离下圈图上1-重心问题的反问题.1-重心问题的反问题主要研究如何尽可能少地改变网络中的参数值,使得给定的顶点到其它顶点的加权距离之和不超过一个给定的上界.通过将该问题转化为0-1背包问题,证明了在哈明距离下该问题是NP困难的,并运用动态规划的思想,在考虑改变边的长度的情况下,对圈图进行了求解.
主要討論哈明距離下圈圖上1-重心問題的反問題.1-重心問題的反問題主要研究如何儘可能少地改變網絡中的參數值,使得給定的頂點到其它頂點的加權距離之和不超過一箇給定的上界.通過將該問題轉化為0-1揹包問題,證明瞭在哈明距離下該問題是NP睏難的,併運用動態規劃的思想,在攷慮改變邊的長度的情況下,對圈圖進行瞭求解.
주요토론합명거리하권도상1-중심문제적반문제.1-중심문제적반문제주요연구여하진가능소지개변망락중적삼수치,사득급정적정점도기타정점적가권거리지화불초과일개급정적상계.통과장해문제전화위0-1배포문제,증명료재합명거리하해문제시NP곤난적,병운용동태규화적사상,재고필개변변적장도적정황하,대권도진행료구해.