旅行推銷員問題
關(guān)注創(chuàng)建者：320科技工作室 創(chuàng)建時間：2020-02-25
旅行推銷員問題的實例教程
旅行推銷員問題 (英語：travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個NP困難問題，在運籌學(xué)和理論計算機科學(xué)中非常重要。
一個判定問題（答案只有是或者否）屬于NP 當且僅當這個問題是非確定型多項式時間可計算的。若NP問題類任何一個問題均可在多項式時間內(nèi)轉(zhuǎn)成問題A, 稱 問題A 是NP 困難問題。說句人話就是這個問題本身比較復(fù)雜，隨著問題規(guī)模越大，即使再強大的計算機也幾乎無法求解。這時候規(guī)模大時候往往尋求近似解。
旅行推銷員問題在圖論中的一個等價形式是：給定一個加權(quán)完全圖（頂點表示城市，邊表示道路，權(quán)重就會是道路的成本或距離）, 求一權(quán)值最小的哈密爾頓回路。
下面舉一個現(xiàn)在看起來瘋狂的例子。
大學(xué)畢業(yè)生小張準備騎自行車進行畢業(yè)旅行，出發(fā)地武漢，到南京，成都，合肥，西安，四個城市旅游，最后回到武漢。模型假設(shè)我們將五個城市視為圖的5個定點，他們的直接距離是圖的權(quán)重。上面城市分別記為1，2，3，4，5.
首先我們可以利用Wolfram Mathematica 聯(lián)網(wǎng)功能一次性求出它們之間的距離。
我們利用上面的距離數(shù)據(jù)在 Maple 里通過下列方式構(gòu)建下面的圖：
restart;
with(GraphTheory):
# 5個城市, 問題歸結(jié)于在一個完全賦權(quán)圖找一個最優(yōu)Hamilton 圈.
展開 </div><div contenteditable="false" width="100%">
以下是旅行推銷員問題 （TSP） 的 ACO 的基本實現(xiàn)：
</div><div contenteditable="false" width="100%">
<br>
</div><p><br></p>
06
travel 旅行商問題的求解
在命令欄窗口輸入“travel”，可觀看旅行推銷員問題演示。
此演示將動畫化所謂的“旅行推銷員”問題。
問題是形成一個旅行時間最短的城市數(shù)量一路上的總距離。
07
truss 桁架結(jié)構(gòu)求解振型
在命令欄窗口輸入“truss”，你可以得到彎曲橋桁架的桁架動畫。這個演示動畫一個二維桁架的12個自然彎曲模式。這些彎曲模態(tài)是特征值分析的結(jié)果。它們是按自然頻率排列的，其中一個是最慢（最容易激發(fā)）模式，12個是最快模式。
旅行推銷員問題的相關(guān)專題、標簽、搜索
旅行推銷員問題的最新內(nèi)容
</div><div contenteditable="false" width="100%">
以下是旅行推銷員問題 （TSP） 的 ACO 的基本實現(xiàn)：
</div><div contenteditable="false" width="100%">
<br>
</div><p><br></p>
06
travel 旅行商問題的求解
在命令欄窗口輸入“travel”，可觀看旅行推銷員問題演示。
此演示將動畫化所謂的“旅行推銷員”問題。
旅行推銷員問題 (英語：travelling salesman problem, TSP）是這樣一個問題：給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。它是組合優(yōu)化中的一個NP困難問題，在運籌學(xué)和理論計算機科學(xué)中非常重要。
一個判定問題（答案只有是或者否）屬于NP 當且僅當這個問題是非確定型多項式時間可計算的。
