使用自定义边缘权重惩罚来提升A*访客?

你所尝试的与启发式无关。A*搜索算法是广度优先搜索,具有优势。启发式方法是添加 下限 最终成本是多少。对于绘制街道方向的地图来说,直线距离是完美的启发式方法。启发式的目的是确保在最有可能的候选人之前扩展最可能的候选人。同样,在地图意义上,广度优先搜索基本上会向外循环,直到你找到你的目的地——而启发式搜索使你可以直接向目的地渗透,并且有更少值得考虑的路径。从另一个角度来看,启发式是一个函数,它获取路径中的当前最后一个点和目标点,并返回成本。不能使用它排除边,因为它不知道路径。它只知道两点。

回到你的问题。您需要:

我希望算法不选择边缘城市,如果旅行时间(边缘权重)大于X,例如100分钟。(只有在可能的情况下,如果没有找到其他路径,则应选择该城市而不是未找到路径)

启发式有 没有什么 以处理特定的图形节点或边。这只是对最终成本的估计,可能不应该依赖于图表本身。你的要求与体重有关。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重量边缘,它的总成本肯定比这条新路径低。我们使用的具体新权重并不重要,它只需要足够大,以保证前面陈述的真实性。

我们不需要改变启发式。只是重量。

我想你只是想要这里的最短路径(dijkstra就可以了)。

关键是要认识到,您可以使用自定义 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的边缘权重都将增加10倍。

然后,你基本上已经完成了:

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