『壹』 C++演算法，動態規劃法實現TSP問題
c++listmatrixiteratoriostream演算法
[cpp] view plainprint?
#include
#include
using namespace std ;
typedef list<</SPAN>int> LISTINT;
LISTINT listAnother;
LISTINT list_result;
int d[4][4]={{-1,3,6,7},{2,-1,8,6},{7,3,-1,5,},{7,3,7,-1}}; //路徑權值
int matrix_length=4;
int getPath(int n,LISTINT list_org)
{
LISTINT::iterator i;
int minValue;
if(n==1)
{
i=list_org.begin();
minValue= d[*i-1][0];
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
}
else
{
int temp;
i=list_org.begin();
temp=*i;
list_org.erase(i);
i=list_org.begin();
minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
for(int j=2;j
{
i=list_org.begin();
for(int k=1;k
{
i++;
}
int tempvalue=*i;
list_org.erase(i);
list_org.push_front(tempvalue);
i=list_org.begin();
tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
if(tempvalue
{
if(list_org.size()==matrix_length-1)
{
list_result=list_org;
}
minValue=tempvalue;
}
}
}
return minValue;
}
int main(int argc, char* argv[])
{
LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout<<"旅行商問題動態規劃演算法"<<endl;
cout<<"路線長度的矩陣表示如下 （-1表示無限大）"<<endl;
for(int j=0;j
cout<<endl;
for(int k=0;k
cout<<" "<<d[j][k];
}
}
cout<<endl;
cout<<"計算結果:"<<getPath(4,list_org)<<endl;
list_result.push_front(1);
list_result.push_back(1);
cout<<"要走的路徑:---->:";
for (h = list_result.begin(); h != list_result.end(); ++h)
cout << *h << " ";
cout << endl;
int i;
cin>>i;
return 0;
}
『貳』 跪求用dijkstra演算法解決TSP多旅行商問題的MATLAB程序！
dijkstra演算法是用來求任意兩點間的最短路徑。他求出的路徑並不是歐拉迴路，不滿足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問題的演算法
你是說有10個點，想選4個點么，找4個點+起點的周遊最小值？
點比較少，枚舉4個點，C(10,4) = 210 種情況，然後找所有情況的最小值。那麼最後這4個點就是你要的4個點。
『伍』 遺傳演算法tsp 城市100個 種群個數應該是多少
個體基因數為100，建議種群數為100*（3~5）
遺傳代數為100*（8~10）
『陸』 tsp問題的貪心演算法，分析時間復雜度，試分析是否存在o的有效演算法
貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產
『柒』 用java解決tsp問題用什麼演算法最簡單
package noah;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
public class TxTsp {
private int cityNum; // 城市數量
private int[][] distance; // 距離矩陣
private int[] colable;//代表列，也表示是否走過，走過置0
private int[] row;//代錶行，選過置0
public TxTsp(int n) {
cityNum = n;
}
private void init(String filename) throws IOException {
// 讀取數據
int[] x;
int[] y;
String strbuff;
BufferedReader data = new BufferedReader(new InputStreamReader(
new FileInputStream(filename)));
distance = new int[cityNum][cityNum];
x = new int[cityNum];
y = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
// 讀取一行數據，數據格式1 6734 1453
strbuff = data.readLine();
// 字元分割
String[] strcol = strbuff.split(" ");
x[i] = Integer.valueOf(strcol[1]);// x坐標
y[i] = Integer.valueOf(strcol[2]);// y坐標
}
data.close();
// 計算距離矩陣
// ，針對具體問題，距離計算方法也不一樣，此處用的是att48作為案例，它有48個城市，距離計算方法為偽歐氏距離，最優值為10628
for (int i = 0; i < cityNum - 1; i++) {
distance[i][i] = 0; // 對角線為0
for (int j = i + 1; j < cityNum; j++) {
double rij = Math
.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])
* (y[i] - y[j])) / 10.0);
// 四捨五入，取整
int tij = (int) Math.round(rij);
if (tij < rij) {
distance[i][j] = tij + 1;
distance[j][i] = distance[i][j];
} else {
distance[i][j] = tij;
distance[j][i] = distance[i][j];
}
}
}
distance[cityNum - 1][cityNum - 1] = 0;
colable = new int[cityNum];
colable[0] = 0;
for (int i = 1; i < cityNum; i++) {
colable[i] = 1;
}
row = new int[cityNum];
for (int i = 0; i < cityNum; i++) {
row[i] = 1;
}
}
public void solve(){
int[] temp = new int[cityNum];
String path="0";
int s=0;//計算距離
int i=0;//當前節點
int j=0;//下一個節點
//默認從0開始
while(row[i]==1){
//復制一行
for (int k = 0; k < cityNum; k++) {
temp[k] = distance[i][k];
//System.out.print(temp[k]+" ");
}
//System.out.println();
//選擇下一個節點，要求不是已經走過，並且與i不同
j = selectmin(temp);
//找出下一節點
row[i] = 0;//行置0，表示已經選過
colable[j] = 0;//列0，表示已經走過
path+="-->" + j;
//System.out.println(i + "-->" + j);
//System.out.println(distance[i][j]);
s = s + distance[i][j];
i = j;//當前節點指向下一節點
}
System.out.println("路徑:" + path);
System.out.println("總距離為:" + s);
}
public int selectmin(int[] p){
int j = 0, m = p[0], k = 0;
//尋找第一個可用節點，注意最後一次尋找，沒有可用節點
while (colable[j] == 0) {
j++;
//System.out.print(j+" ");
if(j>=cityNum){
//沒有可用節點，說明已結束，最後一次為 *-->0
m = p[0];
break;
//或者直接return 0;
}
else{
m = p[j];
}
}
//從可用節點J開始往後掃描，找出距離最小節點
for (; j < cityNum; j++) {
if (colable[j] == 1) {
if (m >= p[j]) {
m = p[j];
k = j;
}
}
}
return k;
}
public void printinit() {
System.out.println("print begin....");
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++) {
System.out.print(distance[i][j] + " ");
}
System.out.println();
}
System.out.println("print end....");
}
public static void main(String[] args) throws IOException {
System.out.println("Start....");
TxTsp ts = new TxTsp(48);
ts.init("c://data.txt");
//ts.printinit();
ts.solve();
}
}
『捌』 對於大規模TSP問題，為什麼遍歷演算法不可行而貪心演算法可行
TSP屬於NPC問題，一般只能靠近似演算法求出近似解，問題規模小的時候，可以直接窮舉問題空間，得出最優解，不過問題規模一大就不行了，問題空間是指數暴漲的，這時候只能退而求其次，求近似最優解，而對應的近似演算法中會大量使用貪心策略，所以其實不是可不可行的問題，貪心犧牲了 解的精度（求得的不一定是最優解），但換來了時間上可觀的節約（直接降到多項式）。
『玖』 想用動態規劃演算法解決旅行商（TSP）問題，麻煩指點下方法和思路，詳細點，謝謝1
http://hi..com/__%D2%E5__/blog/item/d6326f1fcbdb4eff1ad576d8.html
http://liouwei20051000285.blog.163.com/blog/static/25236742009112242726527/
以上都是動態規劃解決TSP問題的，但是個人覺得不是太好，建議你去了解一下遺傳演算法，很容易懂，網上有很詳細的講解。希望你學到知識