Boost图形算法-添加约束

Question

问题

我有一组均匀分布的顶点（一个 网格）。当垂直或水平移动时，相邻顶点之间的距离为1（普通网格单位）。基本上是一个普通的网格：

以下是我代码中的约束条件：

• 访问每个顶点
• 只能垂直或水平移动（不是对角线）

我只需要添加一个约束条件。我需要最小化转弯次数。也就是说，最小化 “推销员” 需要改变方向的次数 (如下面的例子所示)。如何实现这个目标呢？

例子

在这两张图像中，虽然所有的顶点都被访问了，但到达那里所需的转弯次数是不同的。我想要尽量减少这些转弯次数。

如何实现这个目标呢？

我的代码

为了简化，以下是我的代码（只有一个4x4的网格）。

#include <boost/config.hpp>
#include <iostream>
#include <fstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;

int main(int, char *[])
{
    typedef adjacency_list < listS, vecS, directedS, no_property, property < edge_weight_t, int > > graph_t;
    typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
    typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
    typedef std::pair<int, int> Edge;

    // This just creates a 4x4 vertex grid like in the examples above
    const int num_nodes = 16;
    enum nodes { A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P };
    char name[] = "ABCDEFGHIJKLMNOP";
    Edge edge_array[] =
    {
        Edge(A, B), Edge(B, C), Edge(C, D),
        Edge(A, E), Edge(B, F), Edge(C, G), Edge(D, H),
        Edge(E, F), Edge(F, G), Edge(G, H),
        Edge(E, I), Edge(F, J), Edge(G, K), Edge(K, L),
        Edge(I, J), Edge(J, K), Edge(K, L),
        Edge(I, M), Edge(J, N), Edge(K, O), Edge(L, P),
        Edge(M, N), Edge(N, O), Edge(O, P),
    };

    int weights[num_nodes];
    std::fill_n(weights, num_nodes, 1); // set all edge weights to 1

    int num_arcs = sizeof(edge_array) / sizeof(Edge);

    graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
    property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

    std::vector<vertex_descriptor> p(num_vertices(g));
    std::vector<int> d(num_vertices(g));
    vertex_descriptor s = vertex(A, g);

    dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

    return EXIT_SUCCESS;
}

- arao6

Answer 1

您需要在改变方向时为计算出的成本添加惩罚 (这需要实时计算)。您可以在 bgl 中使用动态成本计算：

boost::function_property_map<MyDynamicWeightFunctor, edge_t, float> weight_map(weight_functor);
dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]).weight_map(weight_map));

struct MyDynamicWeightFunctor : public std::unary_function<edge_t, float> {
    MyDynamicWeightFunctor(const GRAPH_TYPE &g)
        : mGraph(g) {
    }
    float operator()(edge_t e) const {
        // You will need to do something more complicated here
        // You will need to look up where you came from. You can accomplish this
        // by passing some structure in the constructor of this functor that keeps
        // track of you previous location(s)
        return mGraph[e].weight * 2;
    }
    const GRAPH_TYPE &mGraph;
};

我已经有一段时间没有使用它了，请查看如何使用属性映射http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/using_property_maps.html，特别是函数属性映射http://www.boost.org/doc/libs/1_54_0/libs/property_map/doc/function_property_map.html

- gvd