4

问题

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

网格是什么样子的

以下是我的代码中到目前为止的约束：

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

我只需要再添加一个约束。我需要尽量减少转数。也就是说，尽量减少“推销员”需要改变方向的次数（以下示例）。我将如何实现这一目标？

例子

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

有 6 个转弯的路径 11 转的路径

我将如何实现这一目标？

我的代码

我在下面简化了我的代码（为简单起见，它只是一个 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;
}
4

1 回答 1

3

每当您改变方向（需要即时计算）时，您都需要对计算的成本添加惩罚。您可以使用以下方法在 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

于 2013-09-11T06:11:38.170 回答