c++ - TSP解决方案解读

Question

This is mostly a consulting question.

我开发了一种遗传算法来解决 TSP ，长话短说，我写了两个不同的代码，我用了 this作为我的数据集。程序找到的解决方案如下所示。

很明显，第一个程序 ( Prog# 1 ) 的建议解决方案比第二个程序 ( Prog# 2 ) 更有希望被优化；和来自 Prog# 2 的解决方案似乎是最有可能的随机解决方案。

但是 Prog# 1 的成本正如我计算的那样是 97314.36 和 Prog# 2 的成本是 74635.31 这比 Prog# 1 的解决方案成本几乎 20K 小 ，并且由于成本暗示了 Prog# 2 找到的解决方案应该比第一个解决方案优化得多。

问题

1) 为什么Prog# 2 找到解的路径图？不支持(视觉上)计算的成本值？

2) 考虑到打击脚本，有什么我遗漏的吗？

---

为了完整起见，我发布了用于绘制和计算成本值的脚本。

function tsp_plot_output() 
    close all;
    disp('loading data....');
    x=load('out.res'); 
    dist = 0;
    for i=1:2:size(x, 1)-1
        dist = dist + norm(x(i,:) - x(i+1,:), 2);
    end
    dist = dist + norm(x(1,:) - x(end,:), 2);
    fprintf('COST IS: %.2f\n', dist);
    disp('ploting data....');
    xx = x(:,1); xy = x(1:size(xx, 1),2);
    zxx = x(:,1); zxy = x(1:size(zxx),2);
    plot(xx, xy), title('Found TSP solution');
    hold
    plot(zxx, zxy, 'r.');
end

我在 Prog# 1 中使用的代码倒出溶液是

std::ofstream os(outputfile);
BOOST_FOREACH(size_t city, *best->_genes) {
    auto loc = _data->get(city);
    os<<loc.longitude<<" "<<loc.latitude<<endl;
}
os.close(); 

Prog# 2 中的代码相同

ofstream out(jconfig["output-file"].as_string());
for(int i = 0; i < p->lchrom; i++) {
    city c = data.at(best_found->chrom[i]);
    out<<c.x<<" "<<c.y<<endl;
}
out.close();

Answer 1

你在 MATLAB 中的距离计算是错误的。你有:

dist = 0;
for i=1:2:size(x, 1)-1
    dist = dist + norm(x(i,:) - x(i+1,:), 2);
end
dist = dist + norm(x(1,:) - x(end,:), 2);

for i=1:2:size(x,1)-1 你从 i=1 开始，然后添加 2 在每个步骤中，直到达到 size(x,1)-1。因此，您添加从 1-2 到 3-4 的距离，依此类推。当然应该是从1-2开始，然后是2-3等等。这是通过

dist = 0;
for k=1:size(x,1)-1
    dist = dist + norm(x(k+1,:) - x(k,:),2);
end
dist = dist + norm(x(end,:) - x(1,:),2);

举个例子x = [0,0; 1,1; 1,0] 旧例程返回 2.4142，而更正后的例程返回正确的 sqrt(2) + 1 + 1 = 3.4142。

PS:我把运行变量改成了k，因为在MATLAB中i代表虚数单位(详见this question)。我还更改了 norm 中 x 的顺序。当然你的没有错，但是这样很明显你从当前点 k 到下一个点 k+1 而不是另一个方向.