社交網(wǎng)絡(luò)論文翻譯

1、分塊解決分塊解決:迭代搜索策略組合優(yōu)化問(wèn)題迭代搜索策略組合優(yōu)化問(wèn)題摘要：摘要：分支定界和分支切割使用搜索樹(shù)來(lái)確定組合優(yōu)化問(wèn)題的最優(yōu)解。在本文中，我們介紹一種迭代搜索策略，我們稱(chēng)這種方法為分塊解決的最優(yōu)性以及終止證明。這是一種不同于傳統(tǒng)的沒(méi)有分支的搜索樹(shù)的搜索方法。在每個(gè)節(jié)點(diǎn)的搜索路徑中，一個(gè)容易解決的問(wèn)題和一個(gè)稀疏的問(wèn)題將被解決，并且會(huì)向易解決的問(wèn)題附加一個(gè)約束條件。會(huì)向稀疏的問(wèn)題提供一個(gè)現(xiàn)有的解決方案。當(dāng)約束條件變得十分的緊湊，那么它

2、解決問(wèn)題的價(jià)值就不如現(xiàn)有的解決方案。在這一點(diǎn)上，現(xiàn)有的解決方法是最優(yōu)的。使用這種策略很容易在一個(gè)任意時(shí)間算法內(nèi)，發(fā)現(xiàn)搜索樹(shù)節(jié)點(diǎn)上的最優(yōu)的解決方法。分塊解決方法有兩個(gè)比較好的優(yōu)勢(shì)。因?yàn)闆](méi)有分支，所以在搜索樹(shù)之中不會(huì)出現(xiàn)錯(cuò)誤的分支樹(shù)，這種錯(cuò)誤的分支樹(shù)會(huì)在進(jìn)行搜索時(shí)，使得搜索路徑丟失，找不到正確的解決方法。因?yàn)檫@些原因，所以這種方法可以用來(lái)很好的解決使用深度優(yōu)先算法和最優(yōu)算法無(wú)法解決的難題。在本文中，我們證明了分塊解決方法對(duì)于解決非對(duì)稱(chēng)旅行問(wèn)

3、題與策略推銷(xiāo)員問(wèn)題（ATSP）是可行的。我們的最優(yōu)算法，在用于解決ATSP問(wèn)題時(shí)，優(yōu)于國(guó)家最先進(jìn)的分析儀器。這個(gè)沒(méi)有經(jīng)過(guò)優(yōu)化的算法對(duì)于解決一些還沒(méi)有被解決的難題有十分好的效果，就像ASTP問(wèn)題中的“七橋問(wèn)題”這類(lèi)問(wèn)題延展出的五類(lèi)實(shí)際問(wèn)題。對(duì)于現(xiàn)在存在的四個(gè)類(lèi)似的問(wèn)題，使用分塊解決方法是十分有可能解決的。我們的代碼都已經(jīng)發(fā)布到我們的網(wǎng)站上了。關(guān)鍵字關(guān)鍵字：搜索策略；分支定界；分支切割；任意時(shí)間算法；線(xiàn)性規(guī)劃；旅行商問(wèn)題。解決方案是在發(fā)現(xiàn)的

4、第一個(gè)節(jié)點(diǎn)之后，對(duì)后續(xù)發(fā)現(xiàn)的節(jié)點(diǎn)進(jìn)行持續(xù)的更新。當(dāng)搜索終止后，當(dāng)前的解決方法可以保證得到的是最佳的解決方案。在本文中，我們證明了最優(yōu)性和終止的分塊解決策略。本文的結(jié)構(gòu)如下。在下一節(jié)中，會(huì)詳細(xì)的討論分支定界和分支切割問(wèn)題。接下來(lái)的章節(jié)中，會(huì)介紹分塊解決策略的掃描方法，并將它與其他的解決方法進(jìn)行比較。接下來(lái)，我們會(huì)舉例說(shuō)明分塊解決策略在一個(gè)簡(jiǎn)單的線(xiàn)性規(guī)劃問(wèn)題中的應(yīng)用。然后，介紹一個(gè)已經(jīng)實(shí)現(xiàn)的切割算法。這個(gè)算法對(duì)于非對(duì)稱(chēng)旅行商問(wèn)題（ATSP）

5、的證明有很好的實(shí)現(xiàn)。我們已經(jīng)測(cè)試了一個(gè)初步的，未經(jīng)優(yōu)化的算法，并比較它與分支定界和分支切割法的性能的差異。我們的測(cè)試表明，對(duì)于一些簡(jiǎn)單的問(wèn)題，分塊解決策略的速度不一定總是比國(guó)家最先進(jìn)的求解儀器計(jì)算的速度快一些。然而，對(duì)于“七橋問(wèn)題“的五個(gè)實(shí)例，這種策略能夠更好的解決，它的解決方案比其他的都要更加的優(yōu)越。在本文的以下內(nèi)容中我們將會(huì)對(duì)它進(jìn)行詳細(xì)的介紹。2.2.背景介紹背景介紹在本節(jié)中，我們定義了一些術(shù)語(yǔ)，用于更詳細(xì)的描述分支定界和分支切割。

6、并且使用非對(duì)稱(chēng)旅行商問(wèn)題（ATSP）為例，對(duì)這些術(shù)語(yǔ)加以說(shuō)明。分支定界和分支切割已被用來(lái)解決各種優(yōu)化問(wèn)題。在本文中，我們已經(jīng)將這種方法運(yùn)用到任何一種實(shí)例之中。但是，為了讓我們的討論更具體一些，所以，在本文中我們將會(huì)專(zhuān)注于介紹整數(shù)線(xiàn)性規(guī)劃（IPS）問(wèn)題。一個(gè)IP既是一個(gè)優(yōu)化問(wèn)題，受到一組線(xiàn)性條件的約束。IP地址已被用于模擬各種各樣的問(wèn)題，如旅行商問(wèn)題（TSP）[2236]，約束滿(mǎn)足問(wèn)題（CSP）[15]，以及網(wǎng)絡(luò)優(yōu)化問(wèn)題[45]等。此外，

7、許多問(wèn)題都可以擴(kuò)展出一個(gè)更一般的問(wèn)題。TSP的應(yīng)用包括大量的調(diào)度，選擇，和規(guī)劃問(wèn)題，如無(wú)等待流水作業(yè)，堆垛機(jī)，傾斜鉆孔機(jī)，電腦磁盤(pán)的讀取頭，機(jī)器人的運(yùn)動(dòng)，以及公用電話(huà)錢(qián)幣收藏的問(wèn)題[30]。此外，TSP問(wèn)題可以為各種各樣的難以解決的問(wèn)題建立模型，如最短的超弦問(wèn)題，這是遺傳學(xué)的研究方向；CSP是否用于模型配置，設(shè)計(jì)，診斷，時(shí)空推理，資源分配，圖形界面之間的調(diào)度問(wèn)題[15]。最后，網(wǎng)絡(luò)優(yōu)化問(wèn)題的例子包括：延遲容忍網(wǎng)絡(luò)，蜂窩無(wú)線(xiàn)網(wǎng)絡(luò)基站的位置

8、，和在無(wú)線(xiàn)adhoc網(wǎng)絡(luò)中最小組播的問(wèn)題。存在可以轉(zhuǎn)換為IP地址的計(jì)算機(jī)科學(xué)，幾乎可以應(yīng)用于各個(gè)領(lǐng)域研究的問(wèn)題。此外，還有一些商業(yè)應(yīng)用程序，也可以轉(zhuǎn)換為IP。一般的IP可以寫(xiě)成以下形式：Z=min(max)∑cixi(1)subjectto:asetoflinearconstraints(2)xi∈I(3)在上面的公式中，Ci值代表特定的常數(shù)，集合Xi代表決策變量。約束條件（2）是常數(shù)，決策變量，可能還有一些輔助變量組成的線(xiàn)性等式或不等