旅行商問題貪心演算法

① 用動態規劃求旅行商問題是不是一個有效的演算法為什麼

實際工程中動態規劃往往很難實現，但是求解能得到全局最優。 但是貪心演算法雖然較易陷入局部最優，但是求解效率極高。 若是決策量前後之間影響不是很大，且較大規模問題貪心法較好。

② 對於大規模TSP問題，為什麼遍歷演算法不可行而貪心演算法可行

TSP屬於NPC問題，一般只能靠近似演算法求出近似解，問題規模小的時候，可以直接窮舉問題空間，得出最優解，不過問題規模一大就不行了，問題空間是指數暴漲的，這時候只能退而求其次，求近似最優解，而對應的近似演算法中會大量使用貪心策略，所以其實不是可不可行的問題，貪心犧牲了 解的精度（求得的不一定是最優解），但換來了時間上可觀的節約（直接降到多項式）。

③ 對於大規模的TSP問題，為何遍歷演算法是不可行的，而貪心演算法則是一種可

貪心自然也是不行的，這是NPC問題。
你說的應該是剪枝，剪枝並不改變時間復雜度，規模大之後剪枝也不可行，一般只能用近似演算法。

④ 1.簡述一下：兩軍問題及其引申的含義。2.生產者與消費者問題，反映了計算機學科的說沒問題

5 貪心演算法的核心思想是找出整體當中每個小的局部的最優解，並且將所有的這些局部最優解合起來形成整體上的一個最優解。因此能夠使用貪心演算法的問題必須滿足下面的兩個性質：1.整體的最優解可以通過局部的最優解來求出；2.一個整體能夠被分為多個局部，並且這些局部都能夠求出最優解
6 程序調用自身的編程技巧稱為遞歸,是函數自己調用自己。
迭代:利用變數的原值推算出變數的一個新值.如果遞歸是自己調用自己的話,迭代就是A不停的調用B。
7 回溯法(探索與回溯法)是一種選優搜索法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」

哎，太多了。寫不完了。。。。
盡量幫你一點吧

⑤ 最短哈密頓迴路！！！！！！！！！

你這個問題是NPC問題，不存在多項式時間的演算法。

只有兩種方法：
1，搜索：O(n!)
2，狀態壓縮的動態規劃：O(n^2*2^n)

⑥ tsp問題的貪心演算法，分析時間復雜度，試分析是否存在o的有效演算法

貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產

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

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

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

⑧ tsp貪心演算法旅行商問題怎麼判斷是否到過某個城市

用vis[]數組標記。。。

⑨ 假設哈密頓問題是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問題