boost A * посетитель с пользовательским ограничением веса края?

Question

Я играю с повышающим A * алгоритм, начали с примером, приведенным на: http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cpp

Я вижу, что вы можете изменить его эвристику и его посетитель, чтобы иметь какое-то пользовательские настройки, так что я не совсем понимаю Концепция еще для такой вещи, как следующая, в качестве примера обучения, я бы хотел, чтобы алгоритм НЕ выбирал крайний город-город, если время в пути (вес края) больше, чем X, например 100 минут. (только если это возможно, если не найдено другого пути, то этот город должен быть заблокирован, а не путь)

Я пробовал собственный эвристический класс, который возвращает больше времени, чем реальность, чтобы «обмануть» его, чтобы не выбирать этот город, однако проблема в том, что с помощью этого трюка штрафный город отбрасывается, даже для дальнейших взаимодействий. (Следующий пример объясняет это: B-> D отбрасывается как лучший путь найден, но город D не отбрасываются (вы видите это выбрали в следующей итерации)

Так что упростило задачу Furter:

enum nodes { 
    A, B, C, D, E, N 
    }; 
    const char *name[] = { 
    "A", "B", "C", "D", "E", "F" 
    }; 
edge edge_array[] = { 
    edge(A,B), edge(B,C), 
    edge(C,D), edge(D,E), 
    edge(B,D) // B to D is the problem here, it should be excluded 
    }; 
cost weights[] = { // estimated travel time (mins) 
    // 107, 174, 283, 71, 436 
    35, 58, 94, 23, 145 
    }; 

в этом примере (принимая код от оригинала в качестве основы), я получаю маршрут:

Начало вершины: A

Гол вершину: E

Кратчайший путь от А до Е: А -> В -> D -> Е

Общее время в пути: 204,5

Проблема заключается в В -> D путь, который является таким большим расстоянием (допустим, например, порог 100, что было бы предпочтительнее: A -> B -> C -> D -> E. Таким образом, расстояние между 2 городами не превышает 100 (конечно, только если возможно, если нет другого пути, любой из них должен быть выбран)

Я решил его неоптимальным способом: пользовательская функция после добавления кромки, которая (или установка веса вручную) return travelTime > 100 ? travelTime * 2 : travelTime, которая может быть ахи эвед для тестирования с:

cost weights[] = { // estimated travel time (mins) 
    // 107, 174, 283, 71, 436 
    (35 > 100) ? 35*2 : 35, (58 > 100) ? 58*2 : 58, (94>100) ? 94*2 : 94, 23, (145 > 100) ? 145*2 : 145 
    }; // The comparisons are not needed, just there to better explain what the custom add_edge function will do. 

С помощью этого метода, я получаю нужный A -> B -> C -> D -> E, но таким образом, это просто хак/обходной путь проблема и изменяет входные данные внутри, что я думаю, что это не самое лучшее решение.

Есть ли лучший способ достичь этого без необходимости вручную изменять расстояния/время в пути?

Answer 1

Я думаю, что вам нужны только самые короткие пути (дикстра будет в порядке).

Ключ должен понимать, что вы можете использовать карту недвижимости edge_weight. Это может быть, например, boost::property_map::transform_value_property_map<> так:

auto my_custom_weight_map = 
    boost::make_transform_value_property_map(
      [](float w) { return w>100? 10*w : w; }, 
      boost::get(boost::edge_weight, g)); 

Вы видите, что любой вес края выше 100 будет увеличена в десять раз.

Тогда вы в основном уже сделано:

astar_search_tree(g, start, 
      distance_heuristic<mygraph_t, cost>(goal), 
      boost::weight_map(my_custom_weight_map) // THIS LINE ADDED 
       .predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g))) 
       .distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g))) 
       .visitor(astar_goal_visitor<vertex>(goal)) 
     ); 

И результат:

Start vertex: A 
Goal vertex: E 
Shortest path from A to E: A -> B -> C -> D -> E 
Total travel time: 210 

Live On Coliru

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/astar_search.hpp> 
#include <boost/property_map/transform_value_property_map.hpp> 
#include <iostream> 
#include <list> 

// auxiliary types 
struct location { 
    float y, x; // lat, long 
}; 

typedef float cost; 

// euclidean distance heuristic 
template <class Graph, class CostType> 
class distance_heuristic : public boost::astar_heuristic<Graph, CostType> { 
    public: 
    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; 
    distance_heuristic(Vertex goal) : m_goal(goal) {} 
    CostType operator()(Vertex /*u*/) { 
     return 0; // Not really needed here 
    } 

    private: 
    Vertex m_goal; 
}; 

struct found_goal {}; // exception for termination 

// visitor that terminates when we find the goal 
template <class Vertex> class astar_goal_visitor : public boost::default_astar_visitor { 
    public: 
    astar_goal_visitor(Vertex goal) : m_goal(goal) {} 
    template <class Graph> void examine_vertex(Vertex u, Graph &/*g*/) { 
     if (u == m_goal) 
      throw found_goal(); 
    } 

    private: 
    Vertex m_goal; 
}; 

int main() { 
    // specify some types 
    typedef boost::adjacency_list<boost::listS, boost::vecS, 
      boost::undirectedS, boost::no_property, 
      boost::property<boost::edge_weight_t, cost> 
     > mygraph_t; 

    typedef boost::property_map<mygraph_t, boost::edge_weight_t>::type WeightMap; 
    typedef mygraph_t::vertex_descriptor vertex; 
    typedef mygraph_t::edge_descriptor edge_descriptor; 
    typedef std::pair<int, int> edge; 

    enum nodes { A, B, C, D, E, N }; 
    const char *name[] = { "A", "B", "C", "D", "E", "F" }; 
    edge edge_array[] = { 
     edge(A, B), edge(B, C), edge(C, D), edge(D, E), edge(B, D) // B to D is the problem here, it should be excluded 
    }; 
    cost weights[] = { // estimated travel time (mins) 
         // 107, 174, 283, 71, 436 
         35, 58, 94, 23, 145 
    }; 

    unsigned int num_edges = sizeof(edge_array)/sizeof(edge); 

    // create graph 
    mygraph_t g(N); 
    WeightMap weightmap = get(boost::edge_weight, g); 
    for (std::size_t j = 0; j < num_edges; ++j) { 
     edge_descriptor e; 
     bool inserted; 
     boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g); 
     weightmap[e] = weights[j]; 
    } 

    // pick start/goal 
    vertex start = A; 
    vertex goal = E; 

    std::cout << "Start vertex: " << name[start] << std::endl; 
    std::cout << "Goal vertex: " << name[goal] << std::endl; 

    std::vector<mygraph_t::vertex_descriptor> p(num_vertices(g)); 

    using boost::get; 

    // do a real edit 
    std::vector<cost> d(num_vertices(g)); 

    auto my_custom_weight_map = 
     boost::make_transform_value_property_map(
       [](float w) { return w>100? 10*w : w; }, 
       boost::get(boost::edge_weight, g)); 

    try { 
     // call astar named parameter interface 
     astar_search_tree(g, start, 
       distance_heuristic<mygraph_t, cost>(goal), 
       boost::weight_map(my_custom_weight_map) 
        .predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g))) 
        .distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g))) 
        .visitor(astar_goal_visitor<vertex>(goal)) 
      ); 

    } catch (found_goal fg) { // found a path to the goal 
     std::list<vertex> shortest_path; 
     for (vertex v = goal;; v = p[v]) { 
      shortest_path.push_front(v); 
      if (p[v] == v) 
       break; 
     } 

     std::cout << "Shortest path from " << name[start] << " to " << name[goal] << ": "; 
     std::list<vertex>::iterator spi = shortest_path.begin(); 
     std::cout << name[start]; 

     for (++spi; spi != shortest_path.end(); ++spi) 
      std::cout << " -> " << name[*spi]; 

     std::cout << std::endl << "Total travel time: " << d[goal] << std::endl; 
     return 0; 
    } 

    std::cout << "Didn't find a path from " << name[start] << "to" << name[goal] << "!" << std::endl; 
    return 0; 
} 

Answer 2

Что вы пытаетесь не иметь ничего общего с эвристикой. Алгоритм поиска A * - это поиск по ширине с преимуществами. Эвристика заключается в том, чтобы добавить нижний номер к окончательной стоимости. Для карты, выполняющей уличные направления, прямолинейное расстояние является идеальной эвристикой. Цель эвристики заключается в том, чтобы вы расширили ваши лучшие кандидаты перед вашими худшими кандидатами. Опять же, в смысле карты, поиск по ширине будет в основном кругом наружу, пока вы не найдете свое место назначения, - тогда как эвристика сделает это так, что вы согните прямо к месту назначения и уделите гораздо меньше путей. С другой стороны - эвристика - это функция, которая принимает текущую последнюю точку в пути и точке назначения и возвращает стоимость. Вы не можете использовать его для исключения краев, поскольку он не знает о пути. Он знает только о двух моментах.

Обратно к проблеме.Вы хотите:

Я бы хотел, чтобы алгоритм НЕ выбирал край города - город, если время в пути (вес края) больше X, например 100 минут. (Только если это возможно, если нет другого пути не будет найден, то, что город должен быть chosed вместо не найден пути)

Эвристические не имеет ничего делать с конкретными узлами графа или ребрами. Это просто оценка конечной стоимости и, вероятно, не должна зависеть от самого графика. То, что вы просите, связано с весами. A * - это поиск пути с минимальным весом. Если вы хотите, чтобы край НЕ принимался ... просто поднял вес!

Пример вы связаны с имеет следующие веса:

cost weights[] = { // estimated travel time (mins) 
    96, 134, 143, 65, 115, 133, 117, 116, 74, 56, 
    84, 73, 69, 70, 116, 147, 173, 183, 74, 71, 124 
}; 

Вы хотите новых весов, в основном:

auto new_weights = at_most(weights, 100); // I don't want to use any edges 
              // that take 100 minutes 

Что мы могли бы написать таким образом:

template <size_t N> 
std::array<cost, N> at_most(cost (&old)[N], cost max_cost) { 
    cost total = std::accumulate(old, old+N, 0.0f) * N; 
    std::array<cost, N> new_weights; 
    for (size_t i = 0; i < N; ++i) { 
     new_weights[i] = old[i] < max_cost ? old[i] : old[i] + total; 
    } 
    return new_weights; 
} 

В принципе, мы просто суммируйте ВСЕ веса и замените все ребра, стоимость которых больше, чем вы указали как ваш максимум с новым весом, который больше, чем выбор всех краев. Конечным результатом этого является то, что если существует путь, который не использует ни один из краев> 100 весов, он, безусловно, будет иметь более низкую общую стоимость, чем этот новый путь. Конкретный новый вес, который мы используем, не имеет значения, он просто должен быть достаточно большим, чтобы гарантировать правду предыдущего утверждения.

Нам не нужно менять эвристику. Просто вес.