c++ - Boost Graph 算法 - 添加约束

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;
}

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