李小龍　段雪峰　徐增敏

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

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

中圖法分類號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

0引言

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

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

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

1問題定義

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

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

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

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

2問題是NP難問題的證明

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

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

設(shè)G=(V，E)是一個(gè)加權(quán)完全二分圖，兩邊的頂點(diǎn)分別為A={a₁，a₂…，a_m}和B=(b₁，b₂，…，b_m)，E={i