tsp1200演算法區塊鏈

㈠ TSP問題的演算法

你是說有10個點，想選4個點么，找4個點+起點的周遊最小值？
點比較少，枚舉4個點，C(10,4) = 210 種情況，然後找所有情況的最小值。那麼最後這4個點就是你要的4個點。

㈡ TSP問題數學模型的簡介

「旅行商問題」常被稱為「旅行推銷員問題」，是指一名推銷員要拜訪多個地點時，如何找到在拜訪每個地點一次後再回到起點的最短路徑。規則雖然簡單，但在地點數目增多後求解卻極為復雜。以42個地點為例，如果要列舉所有路徑後再確定最佳行程，那麼總路徑數量之大，幾乎難以計算出來。多年來全球數學家絞盡腦汁，試圖找到一個高效的演算法，在大型計算機的幫助下才取得了一些進展 。
TSP問題在物流中的描述是對應一個物流配送公司，欲將n個客戶的訂貨沿最短路線全部送到。如何確定最短路線。
TSP問題最簡單的求解方法是枚舉法。它的解是多維的、多局部極值的、趨於無窮大的復雜解的空間，搜索空間是n個點的所有排列的集合，大小為（n-1）。可以形象地把解空間看成是一個無窮大的丘陵地帶，各山峰或山谷的高度即是問題的極值。求解TSP，則是在此不能窮盡的丘陵地帶中攀登以達到山頂或谷底的過程。

㈢ 假設哈密頓問題是NPC,證明:TSP（旅行商問題）屬於NP-hard問題（現代優化計算方法 邢文旬主編 P50第11題）

首先HC是一個npc問題且是一個搜索問題，假設使用貪心策略的演算法A（·）可解HC得到一條哈密頓迴路。
再利用無向圖G構造tsp的圖G'，圖G中存在的邊權值設為1，圖G中不存在的邊權值設為X（X>1的整數）。
這樣得到的一個TSP問題可使用演算法A（·）來解。
圖靈規約條件：（1）問題1，問題2都是搜索問題；
（2）求解問題1的演算法A（·）可求解問題2；

（3）演算法A（問題1）時間復雜度是多項式時間，則演算法A(問題2)也是多項式時間；
所以HC可以圖靈規約到這樣一個TSP問題實例。
又因為HC是NPC類問題，可以圖靈規約到TSP，所以TSP是NP-hard問題

㈣ TSP中用蟻群演算法和遺傳演算法有區別么

TSP,只是一個普通但很經典的NP-C問題。具有大的難以想像的解空間。一般的branch-and-bound演算法是很難搞定的。於是,人們嘗試智能演算法,包括遺傳演算法,蟻群演算法,粒子群演算法等。遺傳演算法和蟻群演算法都是基於種群的。但是這兩個演算法有著本質區別。遺傳演算法的進化機制是基於個體競爭,而蟻群演算法的搜索機制則是螞蟻之間的信息素傳導機制下的群體合作。因此,蟻群演算法,粒子群演算法,人工魚群演算法等,被歸納為群智能演算法,成為了一個有別於遺傳演算法的另一個進化計算領域的分支。由於搜索機制的不同,這兩種演算法對於不同的問題,具有不同的效率。就拿標准遺傳演算法和標准蟻群演算法來說,應該是蟻群演算法更適合求解TSP。然而,無論是遺傳演算法還是蟻群演算法,都有大量的變種演算法或者稱為改進演算法,所以很難簡單的說誰更適合TSP。
記得採納啊

㈤ TSP演算法在實際中有什麼意義

不要問解決數學問題有什麼用，總會有用的，數學是自然科學的基礎。

TSP問題的概述
旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值，這是一個NP難問題。
TSP問題的由來
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線形規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
TSP在中國的研究
同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應該如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題（Chinese Postman Problem CPP）因為是我國學者管梅古教授於1962年提出的這個問題並且給出了一個解法。

㈥ 已知TSP是NP難的 證明WTSP是NP難的 是一道數模題 這個要怎麼證明

由哈密頓路構造，設原來求哈密頓路的圖1中每條邊權值都為1，總邊數為n,由於求哈密頓路的圖1不是完全圖，故新增加權值為n的邊使之變為完全圖2，假若WTSP會解，我們用WTSP的演算法在圖2中找出WTSP的路徑。若總權值<n,則此路徑不包含原圖1中新增加的權值為n的邊，此路徑就是原圖哈密頓路徑；若總權值>n，則此路徑必包含原圖1中新增加的權值為n的邊，原圖中無哈密頓路。由此推出，若WTSP會解，那麼我們可以在多項式時間內轉化為哈密頓路，而已知哈密頓路是NP難的，所以WTSP是NP難的。

㈦ tsp是什麼啊

TSP是英文"Total Suspended Particulate"的縮寫，其中文含義可譯為"總懸浮顆粒物"。

㈧ tSp Concorder演算法原理

tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標，然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重，f_k表示歸一化之後的第i個目標值。我們很容易知道，這類方法的關鍵是怎麼設計權重。比如，Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式，每次計算適應度都對所有個體隨機地產生不同目標的權重，然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標，VEGA 會隨機地將種群分為K個同等大小子種群，在不同的子種群按照不同的目標函數設定目標值，然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法，開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題，即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為：一個商品推銷員要去若干個城市推銷商品，該推銷員從一個城市出發，需要經過所有城市後，回到出發地。應如何選擇行進路線，以使總的行程最短。從圖論的角度來看，該問題實質是在一個帶權完全無向圖中，找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖，而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據，可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法，它不是一個具體的演算法，而是一個演算法簇。遺傳演算法是演化演算法的一個分支，由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息，所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法（用MATLAB編寫）來解決TSP問題。

㈨ TSP是什麼意思啊

TSP即旅行商問題，即TSP問題（Traveling Salesman Problem）又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。

假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市，路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。

TSP問題是一個組合優化問題。該問題可以被證明具有NPC計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。

(9)tsp1200演算法區塊鏈擴展閱讀：

描述

TSP問題作為圖論問題可以用無向加權圖來對TSP建模，則城市是圖的頂點，道路是圖的邊，道路的距離就是該邊的長度。它是起點和終點都在一個特定頂點，訪問每個頂點恰好一次的最小化問題。通常，該模型是一個完全圖（即每對頂點由一條邊連接）。

如果兩個城市之間不存在路徑，則增加一條非常長的邊就可以完成圖，而不影響計算最優迴路。

TSP問題非對稱和對稱，在對稱TSP問題中，兩座城市之間來回的距離是相等的，形成一個無向圖。這種對稱性將解的數量減少了一半。

㈩ TSP問題的簡介

TSP問題是一個組合優化問題。該問題可以被證明具有NP計算復雜性。因此，任何能使該問題的求解得以簡化的方法，都將受到高度的評價和關注。
旅行推銷員問題是圖論中最著名的問題之一，即「已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉迴路」。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效演算法時，每個問題都會有有效演算法。
迄今為止，這類問題中沒有一個找到有效演算法。傾向於接受NP完全問題（NP-Complete或NPC）和NP難題（NP-Hard或NPH）不存在有效演算法這一猜想，認為這類問題的大型實例不能用精確演算法求解，必須尋求這類問題的有效的近似演算法。
此類問題中，經典的還有 子集和問題； Hamilton迴路問題；最大團問題。