摘要：定義了實數(shù)集分裂問題，并給出了一類特殊的實數(shù)集分裂問題。通過構(gòu)造與二分圖的最大權(quán)問題相應(yīng)的圖形模型，證明了這種特殊的實數(shù)集分裂問題是NP難的。

關(guān)鍵詞：實數(shù)集合 分裂問題 NP難

中圖法分類號：TP393

文獻標(biāo)識碼：A

0 引言

在多項式時間內(nèi)，由確定型圖靈機(deterministic Turing ma-chine，簡稱DTM)可以解決的問題稱為P問題；如果一個問題，其解法在多項式時間內(nèi)可以由一個非確定型圖靈機(nondeterminsticTunring machine，簡稱NTM)實現(xiàn)，那么，此問題屬于NP問題。如果所有的NP問題在有限步內(nèi)(在多項式規(guī)約時間內(nèi))可相互規(guī)約問題巧則稱為NP難題(NP-Hard)。如果某個問題是NP-hard的，同時又是NP問題，那么稱其為NP完全(NP-complete，簡稱NPC)問題。NP難是NP類中最難的一類問題。NP難理論的研究在實踐中有著重要的指導(dǎo)作用，在算法設(shè)計和分析過程中，如果證明某問題是NP難的，這就意味著在多項式時間內(nèi)找到該問題的精確解是非常難的，或者說是不可能的。因此，對于NP難問題，最好是去尋找近似解法，尋找設(shè)計在多項式時間可完成的近似解算法。

本文提出了一種新的優(yōu)化問題—實數(shù)集分裂問題，并給出了該問題的一種特殊情況，證明了這種特殊的實數(shù)集分裂問題屬于NP難問題，基本思路是：通過引入二分圖的最大權(quán)問題，而這種特殊的實數(shù)集合分裂問題可在多項式時間內(nèi)相互規(guī)約成二分圖的最大權(quán)問題，從而證明這種特殊的實數(shù)集分裂問題是NP難的。

本文其余部分組織如下：第1節(jié)對實數(shù)集分裂問題進行了定義，并給出了一種特殊情況。第2節(jié)證明了該問題屬于NP難問題。第3節(jié)總結(jié)全文。

1 問題定義

在定義實數(shù)集分裂問題之間，我們首先給出實數(shù)集之間的距離的定義。

實數(shù)集之間的距離：對于兩個均由n個數(shù)組成的集合，若存在著一種匹配，使其匹配數(shù)之差的絕對值之和最小，則稱這個值為實數(shù)集之間的距離。

實數(shù)集分裂問題：對于一個由n×m個實數(shù)組成的集合，若將其平均分配到n個子集中，使其每個子集包含的元素個數(shù)均為m個。問題是：如何分配實數(shù)，使得n個子集兩兩之間的距離之和最小。

對于實數(shù)集分裂問題，我們首先考慮n=2的情況，接下來我們證明n=2時實數(shù)集分裂問題是NP難的。

2 問題是NP難問題的證明

定理1：當(dāng)n=2時，實數(shù)集分裂問題是NP難問題。

證明：首先我們進行一下問題轉(zhuǎn)換。如果將實數(shù)集的元素對應(yīng)于頂點，元素之間的差的絕對值對應(yīng)于邊的權(quán)值，實數(shù)集可以構(gòu)成一個帶有權(quán)值的完全無向圖，其中頂點個數(shù)為2m，邊的個數(shù)為m(2m-1)。傳感器網(wǎng)絡(luò)的極大相似分布問題等價于在對應(yīng)的完全無向圖中找出m條邊，這m邊滿足如下條件：①每個頂點有且僅與其中的一條邊相連；②這m條邊的權(quán)值之和最小。

設(shè)G=(V，E)是一個加權(quán)完全二分圖，兩邊的頂點分別為A={a₁，a₂…，a_m}和B=(b₁，b₂，…，b_m)，E={i，b_j，r_ij}，其中1≤i≤m，1≤j≤m，i，b_j>表示頂點a_i和b_j之間的邊r_ij，表示邊i，b_j>的權(quán)值。二分圖的最大權(quán)匹配就是尋找到一種匹配，使得權(quán)值之和最大。

現(xiàn)在說明怎么把加權(quán)完全二分圖G轉(zhuǎn)換成帶有權(quán)值的完全無向圖G′=(V′，E′)。G中的頂點對應(yīng)于G′中的頂點，E中的任意一條邊i，b_j，>對應(yīng)于G′中連接頂點a_i和b_i的一條邊，該邊的權(quán)值為－r_ij在G中，沒有邊連接的任意兩個節(jié)點，在G′中均有邊連接，這類邊的權(quán)值為一個正數(shù)，不妨設(shè)為MAX。例如，當(dāng)加權(quán)完全二分圖為圖1時，圖2表示了這種構(gòu)造。為證明歸約滿足要求，需要證明在G中獲得二分圖的最大權(quán)匹配時，權(quán)值和為P當(dāng)且僅當(dāng)在完全圖G′中，滿足要求的這L條邊的權(quán)值之和為－p。反證法，易證。由于加權(quán)完全二分圖的最大權(quán)匹配問題為NP難問題，故定理1成立。

3 總結(jié)

本文提出了一種新的優(yōu)化問題一實數(shù)集分裂問題，并給出了該問題的一種特殊情況，通過在多項式時間內(nèi)二分圖的最大權(quán)問題可規(guī)約到這種特殊的實數(shù)集分裂問題，從而證明了該問題屬于NP難問題。