boost图metric_tsp_approximate解决方案不遵循图边

Question

我正试图在使用boost:：adjacety_list创建的图上解决旅行推销员的问题。我正在使用metric_tsp_approx来求解tsp。我面临的问题是，解决方案不遵循图的边。该解决方案连接图形中未直接连接的顶点。我想知道图书馆是这样运作的，还是我做错了什么。这个解决方案看起来也不正确。我有4个顶点组成一个正方形，解决方案应该沿着周长，但它是沿着对角线。对角线上没有边。

这是我的邻接列表：

boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, int>,
boost::property<boost::edge_weight_t, double>,
boost::no_property>

添加顶点和添加边函数：

boost::add_vertex(id, graph);
boost::add_edge(id1, id2, weight, graph);  // weight is euclidean distance

TSP求解器：

std::vector<VertexDescriptor> tsp_path;  //VertexDescriptor is adjacency_list::vertex_descriptor
metric_tsp_approx_tour(graph, back_inserter(tsp_path));

我还尝试将权重映射传递给metric_tsp_approx_tour，但同样的问题仍然存在。

有人能帮我解决这个问题吗？如果boost metric_tsp_approx_tour不考虑图的边，有没有办法让它考虑它们？

Answer 1

文档：https://www.boost.org/doc/libs/1_74_0/libs/graph/doc/metric_tsp_approx.html

这是一个旅行销售人员启发式方法，用于为具有服从三角形不等式的加权边的全连通无向图生成顶点巡回。

(强调矿(

"；全连通图"；子句确实声明所有顶点都被假定为连接的。

同样需要注意的是，假设顶点索引映射到[0，num_vertices(图((

奖金

作为奖励，我试图为算法找出一个最小的工作示例。它似乎确实像广告宣传的那样起作用：

在Coliru上直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/metric_tsp_approx.hpp>
using Graph = 
boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, int>,
boost::property<boost::edge_weight_t, double>,
boost::no_property>;
using VertexDescriptor = Graph::vertex_descriptor;
int main() {
std::vector const points { std::pair
{ 4., 9. }, // these can be randomized
{ 2., 6. },
{ 4., 1. },
{ 1., 1. },
};
Graph graph;
for (auto i = 0u; i < points.size(); ++i) {
add_vertex(i, graph);
}
for (auto i = 0u; i < points.size(); ++i) {
auto va = vertex(i, graph);
// undirected, so only need traverse higher vertices for connections
for (auto j = i+1; j < points.size(); ++j) {
auto vb = vertex(j, graph);
auto const [ax, ay] = points.at(i);
auto const [bx, by] = points.at(j);
auto const dx = bx - ax;
auto const dy = by - ay;
add_edge(va, vb, sqrt(dx*dx + dy*dy), graph); // weight is euclidean distance
}
}
print_graph(graph);
std::vector<VertexDescriptor> tsp_path(num_vertices(graph));  //VertexDescriptor is adjacency_list::vertex_descriptor
metric_tsp_approx_tour(graph, back_inserter(tsp_path));
auto idmap = get(boost::vertex_index, graph);
for (auto vd : tsp_path) {
if (vd != graph.null_vertex()) {
auto [x,y] = points.at(idmap[vd]); 
std::cout << " {" << x << "," << y << "}";
}
}
}

打印

0 <--> 1 2 3 
1 <--> 0 2 3 
2 <--> 0 1 3 
3 <--> 0 1 2 
{4,9} {2,6} {1,1} {4,1} {4,9}