社交網絡論文翻譯

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

2、解決問題的價值就不如現有的解決方案。在這一點上，現有的解決方法是最優(yōu)的。使用這種策略很容易在一個任意時間算法內，發(fā)現搜索樹節(jié)點上的最優(yōu)的解決方法。分塊解決方法有兩個比較好的優(yōu)勢。因為沒有分支，所以在搜索樹之中不會出現錯誤的分支樹，這種錯誤的分支樹會在進行搜索時，使得搜索路徑丟失，找不到正確的解決方法。因為這些原因，所以這種方法可以用來很好的解決使用深度優(yōu)先算法和最優(yōu)算法無法解決的難題。在本文中，我們證明了分塊解決方法對于解決非對稱旅行問

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

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

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

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

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

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