tsp演算法
『壹』 TSP問題的演算法
你是說有10個點，想選4個點么，找4個點+起點的周遊最小值？
點比較少，枚舉4個點，C(10,4) = 210 種情況，然後找所有情況的最小值。那麼最後這4個點就是你要的4個點。
『貳』 蟻群演算法求解TSP問題的源程序及簡要說明
簡單蟻群演算法求解TSP的源程序(我幫你找的)
蟻群演算法是新興的仿生演算法，最初是由義大利學者Dorigo M於1991年首次提出，由於具有較強的魯棒性，優良的分布式計算機制和易於與其它方法結合等優點，成為人工智慧領域的一個研究熱點。本程序是實現簡單的蟻群演算法，TSP問題取的是att48，可從http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95獲取，程序運行時間可能會比較長，在我的這台CPU 1.6G+內存256M的機器上運行時間大概是13分鍾左右。我用的語言是MATLAB 7.1。此程序僅供學習所用，如有問題請反饋。謝謝。（註：程序沒有計算最後一個城市回來起點城市的距離）
function [y,val]=QACS
tic
load att48 att48;
MAXIT=300; % 最大循環次數
NC=48; % 城市個數
tao=ones(48,48);% 初始時刻各邊上的信息最為1
rho=0.2; % 揮發系數
alpha=1;
beta=2;
Q=100;
mant=20; % 螞蟻數量
iter=0; % 記錄迭代次數
for i=1:NC % 計算各城市間的距離
for j=1:NC
distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);
end
end
bestroute=zeros(1,48); % 用來記錄最優路徑
routelength=inf; % 用來記錄當前找到的最優路徑長度
% for i=1:mant % 確定各螞蟻初始的位置
% end
for ite=1:MAXIT
for ka=1:mant %考查第K只螞蟻
deltatao=zeros(48,48); % 第K只螞蟻移動前各邊上的信息增量為零
[routek,lengthk]=travel(distance,tao,alpha,beta);
if lengthk<routelength % 找到一條更好的路徑
routelength=lengthk;
bestroute=routek;
end
for i=1:NC-1 % 第K只螞蟻在路徑上釋放的信息量
deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;
end
deltatao(routek(48),1)=deltatao(routek(48),1)+Q/lengthk;
end
for i=1:NC-1
for j=i+1:NC
if deltatao(i,j)==0
deltatao(i,j)=deltatao(j,i);
end
end
end
tao=(1-rho).*tao+deltatao;
end
y=bestroute;
val=routelength;
toc
function [y,val]=travel(distance,tao,alpha,beta) % 某隻螞蟻找到的某條路徑
[m,n]=size(distance);
p=fix(m*rand)+1;
val=0; % 初始路徑長度設為 0
tabuk=[p]; % 假設該螞蟻都是從第 p 個城市出發的
for i=1:m-1
np=tabuk(length(tabuk)); % 螞蟻當前所在的城市號
p_sum=0;
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
p_sum=p_sum+tao(np,j)^alpha*ada^beta;
end
end
cp=zeros(1,m); % 轉移概率
for j=1:m
if isin(j,tabuk)
continue;
else
ada=1/distance(np,j);
cp(j)=tao(np,j)^alpha*ada^beta/p_sum;
end
end
NextCity=pchoice(cp);
tabuk=[tabuk,NextCity];
val=val+distance(np,NextCity);
end
y=tabuk;
function y=isin(x,A) % 判斷數 x 是否在向量 A 中，如在返回 1 ，否則返回 0
y=0;
for i=1:length(A)
if A(i)==x
y=1;
break;
end
end
function y=pchoice(A)
a=rand;
tempA=zeros(1,length(A)+1);
for i=1:length(A)
tempA(i+1)=tempA(i)+A(i);
end
for i=2:length(tempA)
if a<=tempA(i)
y=i-1;
break;
end
end
『叄』 對於大規模TSP問題，為什麼遍歷演算法不可行而貪心演算法可行
TSP屬於NPC問題，一般只能靠近似演算法求出近似解，問題規模小的時候，可以直接窮舉問題空間，得出最優解，不過問題規模一大就不行了，問題空間是指數暴漲的，這時候只能退而求其次，求近似最優解，而對應的近似演算法中會大量使用貪心策略，所以其實不是可不可行的問題，貪心犧牲了 解的精度（求得的不一定是最優解），但換來了時間上可觀的節約（直接降到多項式）。
『肆』 想用動態規劃演算法解決旅行商（TSP）問題，麻煩指點下方法和思路，詳細點，謝謝1
http://hi..com/__%D2%E5__/blog/item/d6326f1fcbdb4eff1ad576d8.html
http://liouwei20051000285.blog.163.com/blog/static/25236742009112242726527/
以上都是動態規劃解決TSP問題的，但是個人覺得不是太好，建議你去了解一下遺傳演算法，很容易懂，網上有很詳細的講解。希望你學到知識
『伍』 跪求用dijkstra演算法解決TSP多旅行商問題的MATLAB程序！
dijkstra演算法是用來求任意兩點間的最短路徑。他求出的路徑並不是歐拉迴路，不滿足TSP的要求
『陸』 tsp問題的貪心演算法，分析時間復雜度，試分析是否存在o的有效演算法
貪心演算法（又稱貪婪演算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。貪心演算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產
『柒』 TSP問題的遍歷演算法和貪心演算法有什麼區別,為什麼不選擇遍歷演算法
所有問題遍歷演算法的時間復雜度是最高的，但是對於TSP問題來說貪心演算法一般是得不到最優解的
『捌』 用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問題的概述
旅行商問題，即TSP問題（Traveling Salesman Problem）是數學領域中著名問題之一。假設有一個旅行商人要拜訪N個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值，這是一個NP難問題。
TSP問題的由來
TSP的歷史很久，最早的描述是1759年歐拉研究的騎士周遊問題，即對於國際象棋棋盤中的64個方格，走訪64個方格一次且僅一次，並且最終返回到起始點。
TSP由美國RAND公司於1948年引入，該公司的聲譽以及線形規劃這一新方法的出現使得TSP成為一個知名且流行的問題。
TSP在中國的研究
同樣的問題，在中國還有另一個描述方法：一個郵遞員從郵局出發，到所轄街道投郵件，最後返回郵局，如果他必須走遍所轄的每條街道至少一次，那麼他應該如何選擇投遞路線，使所走的路程最短？這個描述之所以稱為中國郵遞員問題（Chinese Postman Problem CPP）因為是我國學者管梅古教授於1962年提出的這個問題並且給出了一個解法。