Boost Graph Algorithm - Ajout d'une contrainte

Question

Le problème

je un ensemble de sommets qui sont distribués de manière uniforme (une grille ). La distance entre sommets voisins est 1 (une unité de grille normale) en allant verticalement ou horizontalement. Fondamentalement, une grille normale:

Voici les contraintes que j'ai jusqu'à présent dans mon code:

• Visiter tous les sommets
• Déplacer uniquement verticalement ou horizontalement (non diagonale)

J'ai juste besoin d'ajouter une contrainte supplémentaire. J'ai besoin de minimiser le nombre de tourne. C'est-à-dire, minimiser le nombre de fois que le «vendeur» aura besoin de changer de direction (exemples ci-dessous). Comment pourrais-je y parvenir?

Exemples

Dans ces deux images, bien que tous les sommets sont visités, le nombre de tours qu'il a fallu pour y arriver est différent. Je veux minimiser ces virages.

Comment puis-je atteindre cet objectif?

Mon code

J'ai simplifié mon code ci-dessous (il est juste une grille de 4x4 par souci de simplicité).

#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

Vous devez ajouter une pénalité au coût calculé chaque fois que vous changez de direction (ce qui doit être calculé à la volée). Vous pouvez faire le calcul des coûts dynamiques en BGL utilisant:

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

Il a été un moment que je l'ai utilisé cela pour avoir un regard sur la façon d'utiliser des cartes de propriété http://www.boost.org/doc/libs/1_54_0/libs/graph/doc/using_property_maps.html et propriété particulière de la fonction mappes http://www.boost.org/doc/libs/1_54_0/libs/property_map/doc/function_property_map.html