‘壹’ 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问题的，但是个人觉得不是太好，建议你去了解一下遗传算法，很容易懂，网上有很详细的讲解。希望你学到知识