c++ - 通过自定义边缘权重惩罚来 boost A* 访问者？

Question

我正在玩 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
  };

通过这个例子(以原始代码为基础)，我得到了一条路线:

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(当然只有在可能的情况下，如果没有其他路径，则必须选择任何路径)

我以一种次优的方式解决了它:一个自定义函数一旦添加了边缘，即(或手动设置权重)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 问题并在内部修改输入数据，我认为这不是最佳解决方案。

有没有更好的方法可以在无需手动更改距离/行程时间的情况下实现这一目标？

Answer 1

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

回到你的问题。你想要:

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 权重的边的路径，则它的总成本肯定会低于这条新路径。我们使用的具体新权重并不重要，它只需要足够大以保证前面陈述的真实性即可。

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