2

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

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

我尝试了一个自定义启发式类，它返回比现实更长的时间，以“欺骗”它不选择那个城市，但问题是通过这个技巧，受惩罚的城市被丢弃，即使是进一步的交互。（下面的例子解释了它：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
  };

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

起始顶点：A

目标顶点：E

从 A 到 E 的最短路径：A -> B -> D -> E

总行程时间：204.5

问题是 B -> 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，但这种方法只是解决问题的一种方法，并在内部修改输入数据，我认为这不是最好的解决方案。

有没有更好的方法来实现这一点而无需手动更改距离/旅行时间？

4

2 回答 2

4

你试图做的与启发式无关。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 权重边的路径，那么它的总成本肯定会低于这条新路径。我们使用的具体新权重并不重要，它只需要足够大以保证前面陈述的真实性。

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

于 2015-09-08T00:02:01.680 回答
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;
}
于 2015-09-08T00:12:09.580 回答