【摘 要】在當前互聯(lián)網(wǎng)通信研究課題中，如何來進行信息合理的選擇，并把其科學且合理的發(fā)布至全部Web服務器上這一問題已逐漸成為了其研究的焦點。針對該焦點問題，下面文章就基于某數(shù)學模型，對其計算的復雜性和近似性進行論述，并在此基礎上，提出一種近似算法，實施相應的數(shù)值模擬試驗來證明該模型的可行性。

【關鍵詞】互聯(lián)網(wǎng)通信 信息選取和分布 建模 分解

一、數(shù)學模型以及其計算復雜性的分析

（一）數(shù)學模型

在該模型中，一共設了n個信息塊，即J1，J2，J3…，Jn，訪問的頻率為Pi，第i個信息塊Ji容量是Si，其中Web服務器一共設有m個，第j個Web服務器容量是Cj，其總的訪問頻率上限是Bj。在該模型中，引入變量Xij的個數(shù)為n×m個，當變量Xij為1時，則表示Ji信息塊放至第J個服務器上，如其為0，則其問題模型如下，在這里將其稱之為P1。

其中公式1表示的是在第J個服務器中所放入的信息塊總量不可大于該服務器量上限。公式2表示的是在每一個服務器中所放入的信息塊，其總的訪問頻率不可大于上限。而公式3則表示每一個信息塊均應該被放入到相對應的服務器上。若因信息塊太多，不能實現(xiàn)這一要求時，則其公式可改為?；谄涔降母淖?，就可獲得以下這一問題模型，在文章中該問題模型稱之為P2。

（二）計算復雜性的分析

在分析之前，將滿足全部約束的某一個解稱之為可行解，基于上述的問題模型來進行判斷并明確在該問題模型中是否存在這一可行解。因P1中可行解的尋找較為困難，在此，文章就問題P2的判定來進行詳細地論述。

定理一：在這里假設問題P2可行解為強NP-完全的。在證明的過程中，可通過三分劃實例來判定，即該問題模型為3m個元素所組成，總和是mA，基于上述內容，對每個元素ai進行一個信息塊的構造，同時訪問頻率與容量均為ai，在這里假設服務器有m個，總訪問的頻率上限與總容量的上限均是A，給定的下界為LB=mB。通過證明可得知在該實例中，這一問題模型有解，同時其目標值大于LB。

定理二：當固定m為2時，P2問題模型判定問題為NP-完全的。在該實例中，其由n個元素所組成，總和是A，對每個元素ai進行一個信息塊的構造，同時其訪問頻率與容量均為ai，在這里設有兩個服務器，其總的訪問頻率上限以及容量上限均是A，基于給定的下界LB=A，通過證明可得知在該實例中，存在相應的可行解，且其目標值大于LB。

定理三：在m>1的條件下，P2問題模型存在偽多項式時間的最優(yōu)算法。在證明過程中，基于動態(tài)規(guī)劃法，按照信息塊自身容量與訪問頻率之間比值大小來進行順序的排列，用fj（x1、x2 ···，xm；y1，y2….ym）來表示在服務器上的容量分別為x1、x2，….xm，當總訪問頻率的上限是y1，y2….ym的時候，前j個信息塊最優(yōu)解值如下。上述這一算法在時間上，其復雜性是0，因該問題模型輸入長度函數(shù)為n=lgM+lgB，因此可認定該算法為偽多項式的時間算法。

二、近似算法

利用數(shù)值試驗來對上述內容和算法所產(chǎn)生的實際效果進行比較，該試驗在配置是128M和C500計算機中實施，在試驗中，給定了n，m，M，B 這幾個值不同的組合，其中Ci與Sj是[0，M]中隨機數(shù)，而 Bi與Pj是[0，B]中隨機數(shù)，其模擬試驗所得到的部分結果如下：

從上表可以得知，當n，m，M，B的值比較小時，動態(tài)的規(guī)劃法能將最優(yōu)解較快地給出，當n，m，M，B值增大時，其時間也在相應的增長，從總體上來看，近似算法所得到得值是最為理想的。

三、結束語

綜上所述，隨著互聯(lián)網(wǎng)技術的快速發(fā)展，在企業(yè)的內部網(wǎng)中，信息組織和規(guī)劃分布式信息系統(tǒng)已成為一項重要的技術。文章通過對相應數(shù)學模型的闡述，以及其求解方式的論述，并在此基礎上實施了數(shù)值的仿真試驗，通過試驗證明，文章所闡述的數(shù)學模型和理論結果都為解決同類問題提供了相應的借鑒以及思路，為互聯(lián)網(wǎng)通信中的信息選取與分布問題以及求解的深入研究打下了堅實的基礎。

參考文獻：

[1]施佺，陸春龍，陳建平等.RIA技術在海洋環(huán)境監(jiān)測信息平臺中的應用[J].計算機工程與設計，2011，32（8）：2684-2688.

[2]王曉喃，唐振民，錢煥延等.IPv6中k-Anycast通信模型的分析與研究[J].南京理工大學學報（自然科學版），2009，33（3）：399-404.