通过自定义边缘权重惩罚来提升 A* 访问者？

Question

我正在玩 boost A* 算法，从在以下位置找到的示例开始：http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cpp

我看到您可以覆盖它的启发式方法和它的访问者以进行某种自定义调整，只是我还不太了解像下面这样的东西的概念，作为一个学习示例，我'如果旅行时间（边缘权重）大于 X，例如 100 分钟，d 喜欢算法不选择边缘城市 - 城市。（仅在可能的情况下，如果没有找到其他路径，则应选择该城市而不是未找到路径）

我尝试了一种自定义启发式 class 比实际情况 returns 更长的时间，以“欺骗”它不要选择那个城市，但问题是使用这个技巧，被惩罚的城市被丢弃，即使是为了进一步的交互。（以下示例对此进行了解释：B->D 被丢弃，因为找到了更好的路径，但城市 D 未被丢弃（您会看到它在随后的迭代中被选中）

所以我进一步简化了问题：

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

通过这个例子（以原始代码为基础），我得到了一条路线：

Start vertex: A

Goal vertex: E

Shortest path from A to E: A -> B -> D -> E

Total travel time: 204.5

问题出在 B -> D 路径，它的距离太长（例如，假设阈值为 100，则最好使用如下路径：A -> B -> C -> D - > E，这样2个城市之间的距离不超过100（当然只有在可能的情况下，如果没有其他路径，就得选any）

我以次优的方式解决了它：一个自定义函数，一旦添加边，即（或手动设置权重）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，但是这种方法只是 hack/workaround 的问题并且在内部修改了输入数据，我认为这不是最好的解决方案。

有没有更好的方法来实现这个而无需手动更改 distances/travel 时间？

Answer 1

您尝试的内容与启发式算法无关。 A*搜索算法是广度优先搜索，有好处。启发式是为最终成本添加下限。对于街道方向的地图，直线距离是完美的启发式方法。启发式的要点是确保您在最不可能的候选人之前扩展最有可能的候选人。同样，在地图意义上，广度优先搜索基本上会向外盘旋，直到您找到目的地——而启发式搜索则使您可以直接向目的地渗出，并且值得考虑的路径更少。从不同的角度来看 - 启发式是一个函数，它采用路径中的当前最后一个点和目标点以及 returns 成本。您不能使用它来排除边缘，因为它不知道路径。它只知道两点。

回到你的问题。你想要：

I'd like the algorithm to NOT pick a edge city - city, if travel time (edge weight) is greater than X, for example 100 minutes. (only if possible, if no other path is found, then that city should be chosed instead of not path found)

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

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

Answer 2

我想你只是想要这里的最短路径（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 的边权重都会增加十倍。

那么，你基本上已经完成了：

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

通过自定义边缘权重惩罚来提升 A* 访问者？

boost A* visitor with a custom edge weight penalty?

c++

boost

a-star

boost-graph

boost-property-map