我遇到了一个使用Matlab脚本的旅行推销员解决方案,在其代码中,我发现它使用了一个名为City Coordinates的表示,它看起来像:
CityCood = [0.4000,0.2439,0.1707,0.2239,0.5171;0.4439,0.1463,0.2293,0.7610,0.9414]
适用于5个城市.
在这一点上,我对作者是如何获得这种表示一无所知,因为从我到目前为止所看到的,手头的信息应该是一个5*5对称矩阵,表示这五个城市中任意两个之间的距离.
如果有人能够让我了解基于坐标的表示如何工作,我将不胜感激.提前致谢.
algorithm matlab traveling-salesman neural-network data-structures
我有兴趣为(小)网格图解决TSP.任何类型的库都可以为我做,但这似乎比预期更难.我尝试了几个我在那里找到的解算器(包括协调器),但是当三角形不等式不成立时,它们似乎都有问题.
例如,我希望求解器为图形输出(0,1,2,1,4,3)(具有单位边缘权重),如下所示:
0-1-2
| |
3-4
在这个特殊情况下,我告诉concorde边缘(2,4)的重量为1000,并且concorde迅速产生了成本1004的巡回赛(0,1,2,4,3).这显然不是我想要的.
理想情况下,Java中会有一些简单的(可能是暴力)实现,但实际上可行的任何东西都可以.任何人都可以指向我一些代码或者我真的必须自己去实现吗？
编辑:同样,重要的是我得到一个精确的解决方案,而不是一些近似.
Edit2:的确,这似乎不是TSP.我想要找到的是一个访问所有顶点的最短的闭路.
我正在尝试使用concorde以下格式在文件中使用TSP求解器：
NAME : p5
COMMENT : Nada
TYPE : TSP
DIMENSION : 20
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
0 0.329733 0.67714
1 0.823944 0.035369
2 0.002488 0.866692
3 0.241964 0.671822
4 0.98876 0.134457
5 0.879147 0.457779
6 0.021017 0.271951
7 0.221737 0.367143
8 0.549802 0.523319
9 0.363839 0.22359
10 0.696631 0.495935
11 0.279072 0.100501
12 0.660156 0.860675
13 0.251769 0.029172
14 0.32112 0.207704
15 0.821433 0.507387
16 0.095411 0.953448
17 0.115897 0.269363
18 0.704484 0.411328
19 0.705198 0.795917
由于找不到有关格式的指南，因此我只修改了我下载的示例文件。我正在运行以下命令： …
我有一个数据框,其X和Y坐标点如下:
structure(list(X = c(666L, 779L, 176L, 272L, 232L, 74L, 928L,
667L, 1126L, 919L), Y = c(807, 518, 724, 221, 182, 807, 604,
384, 142, 728)), .Names = c("X", "Y"), row.names = c(NA, 10L), class = "data.frame")
我只是想找出连接所有这些点的最短路径,并返回它的总距离.没有其他条件:每个点都可以连接到任何其他点,没有特定的点开始或结束,没有权重等...我发现了很多关于igraph包的主题但我无法弄清楚如何提供我的数据进去.发现这个但不是R语言.也许一个"蛮力"剧本会很好,因为我得到的分数不超过20分..谢谢
我正在尝试使用 OpenMP 并行化我自己的 C++ 实现的旅行商问题。
我有一个函数来计算道路cost()和向量 [0,1,2,...,N] 的成本，其中 N 是道路的节点数。
在main()，我试图找到最好的道路：
do
{
cost();
} while (std::next_permutation(permutation_base, permutation_base + operations_number));
我试图用来#pragma omp parallel并行化该代码，但它只会让它更耗时。有没有办法并行化该代码？
我正在尝试为旅行商问题(TSP)编写遗传算法.如需选择我正在实施轮盘赌选择:http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php/
它基本上意味着被选择用于交配的概率与适应度函数的值成比例.
TSP最常见的适应性功能是路线的长度.然而,路线越"越短"越好.
如何编写描述路线短缺的适应度函数？
或者我如何将每条路线的真实长度转换为概率？
我正在寻找以下问题的名称:旅行推销员问题(访问每个城市一次)但没有返回到开始城市和最后访问一个给定的城市.换句话说,我想指定起点和终点城市,我不想回到起点城市.谢谢!!!
我试图通过检查所有可能的排列来解决使用Brute Force程序的旅行商问题.我用c ++完成了.
主要问题是:代码适用于小输入大小.但是当我给出包含16个笛卡尔坐标的文件作为输入并运行程序时,控制台会挂起.它没有显示任何东西.好像它会永远运行.这是什么主要原因？我正在使用Code Blocks编译器.
我正在学习TSP并发现了TSP的这种递归解决方案
int compute(int start,int set)
{ int masked,mask,result=INT_MAX,temp,i;//result stores the minimum
if(g[start][set]!=-1)//memoization DP top-down,check for repeated subproblem
return g[start][set];
for(i=0;i<n;i++)
{ //npow-1 because we always exclude "home" vertex from our set
mask=(npow-1)-(1<<i);//remove ith vertex from this set
masked=set&mask;
if(masked!=set)//in case same set is generated(because ith vertex was not present in the set hence we get the same set on removal) eg 12&13=12
{
temp=adj[start][i]+compute(i,masked);//compute the removed set
if(temp<result)
result=temp,p[start][set]=i;//removing ith vertex gave us minimum
}
}
return g[start][set]=result;//return minimum
} …有没有人在标准ML中有旅行商问题解决方案,请告诉我.
我已经尝试了很多,但没有成功.
编辑:找到了对此算法的改进.欢迎您来看看.
这个问题是我老问题的改进.现在我想向您展示Java代码示例,并更详细地解释我的算法.
我认为我找到了一个多项式算法来获得旅行商问题的精确解.我的实现是从5个步骤构建的:
我想从第2步和第3步开始,如果我没有错,我会告诉你其余部分.
所以我现在要向您展示的不是多项式算法,而是对Held-Karp算法的改进,它解决了时间问题O(n ^ 2 2 ^ n)
让我们说我们想用brout算法解决6个城市的路线.有(6-1)!= 120选项,我们需要测试它们并返回最短的路线.所以它看起来像那样(城市名称是:A,B,C,D,E,F):