多旅行商问题(Multip le Traveling Salesman
Problem, MTSP)是指M 个旅行商从同一个城市(或不同城
市)出发,分别走一条旅行路线,使得每个城市有且仅有一个
旅行商经过(出发城市除外) ,且总路程最短这个问题可以用什么好的算法实现呢，大家给点思路
Problem, MTSP)是指M 个旅行商从同一个城市(或不同城
市)出发,分别走一条旅行路线,使得每个城市有且仅有一个
旅行商经过(出发城市除外) ,且总路程最短这个问题可以用什么好的算法实现呢，大家给点思路
{
static int i;
static int j, k, l, n, m;
static int tmp;
memcpy(gdest.index, gsource.index, sizeof(int) * size);
for(i = 0; i < varate; i++)
{
switch(rand() % 2)
{
case 0:
// 逆序变异
{
j = rand() % size;
k = rand() % size;
if(j == k)
{
k = (k + 1) % size;
}
if(j > k)
{
k += size;
for(l = j; l < j + k - l; l++)
{
n = (j + k - l) % size;
m = l % size;
tmp = gdest.index[m];
gdest.index[m] = gdest.index[n];
gdest.index[n] = tmp;
}
}
else
{
for(l = j; l < j + k - l; l++)
{
tmp = gdest.index[l];
gdest.index[l] = gdest.index[j + k - l];
gdest.index[j + k - l] = tmp;
}
}
}
break;
case 1:
// 转移变异
{
j = rand() % size;
k = 1;//rand() % ((size >> 4) + 1);
if(k == 0)
{
k = 1;
}
l = rand() % (size - k) + 1;
n = (j + k) % size + l > size ? size - (j + k) % size : l;
memcpy(ptemp, gdest.index + (j + k) % size, n * sizeof(int));
if(n < l)
{
memcpy(ptemp + n, gdest.index, (l - n) * sizeof(int));
}
n = j + k > size ? size - j : k;
memcpy(ptemp + l, gdest.index + j, n * sizeof(int));
if(n < k)
{
memcpy(ptemp + l + n, gdest.index, (k - n) * sizeof(int));
}
m = k + l;
n = j + m > size ? size - j :m;
memcpy(gdest.index + j, ptemp, n * sizeof(int));
if(n < m)
{
memcpy(gdest.index, ptemp + n, (m - n) * sizeof(int));
}
}
break;
default:
break;
}
}
}
刚开始是想着动态规划解决，把问题简化了，简化成2个旅行商，5个地区。这样把各个情况罗列出：1.旅行商A经过0个地区时，B经过5个
2.A经过1个时，B经过4个
3.A经过2个时，B经过3个然后解决，但是这个方法太笨。
现在想着能不能这样解决：旅行商1、2、........M，城市：1、2、......N，现实中M>N是没有意义的，因为人不可能比城市数量多
然后根据N解决问题：
1、当N是一个整体时，即只有一个旅行商，他走遍了所有的城市
2、当N是2份时，情况为：1和N-1，2和N-2，3和N-3，这时只有两个旅行商旅行
3、当N是3份时，情况为：1，1，N-2 ； 1，2，N-3； 1，3，N-4。。2，2，N-4； 2，3，N-5
.................
N、当N是N份时，情况为：1，1，1，............
然后针对每一种情况动态规划求解，这样前面N分情况时有点类似于分治，这样得用一个递归实现。
后面就没想好