2

http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cppにある例から始めて、ブーストA *アルゴリズムで遊んでいます。

そのヒューリスティックとビジターをオーバーライドして、ある種のカスタム調整を行うことができることがわかりましたが、学習例として、次のようなことの概念はまだよくわかりません。アルゴリズムに移動時間 (エッジの重み) が 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* 検索アルゴリズムは、メリットのある幅優先検索です。ヒューリスティックは、下限を追加するためにあります最終的な費用がどうなるか。道路案内を行う地図の場合、直線距離は完璧なヒューリスティックです。ヒューリスティックのポイントは、最も可能性の高い候補を最も可能性の低い候補の前に拡張することを保証することです。繰り返しになりますが、マップの意味では、幅優先検索は基本的に目的地が見つかるまで外側に回りますが、ヒューリスティックは目的地に向かって直接にじみ出て、検討する価値のあるパスがはるかに少なくなるようにします. 別の観点から見ると、ヒューリスティックは、パスの現在の最後のポイントと目的のポイントを取り、コストを返す関数です。パスを認識しないため、エッジを除外するために使用することはできません。2点くらいしかわかりません。

あなたの問題に戻ります。あなたがしたい：

移動時間 (エッジの重み) が 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 に答える