Повысьте Graph Алгоритм - Добавление ограничения

Question

Проблема

У меня есть множество вершин, которые распределены равномерно (а сетки). Расстояние между соседними вершинами равно 1 (нормальная единица сетки) при движении по вертикали или по горизонтали. В принципе нормальная сетка:

Вот ограничения у меня до сих пор в моем коде:

• Посетите каждую вершину
• Move только по вертикали или по горизонтали (не по диагонали)

Мне просто нужно добавить еще одно ограничение. Мне нужно свести к минимуму число оборотов. То есть, свести к минимуму количество раз, когда «продавцу» потребуется изменить направления (примеры ниже). Как я могу это достичь?

Примеры

В этих двух изображениях, хотя все вершины посещаются, число витков потребовалось, чтобы получить там разные. Я хочу свести к минимуму эти повороты.

Как бы я этого добиться?

Мой код

Я упростил свой код ниже (это просто 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