2016-07-29 7 views
1

私はルートネットワークを表すグラフを持っています - ウェイポイントは頂点であり、ルートはエッジです。問題は、特定の期間中に交差できない中間地点の間に領域が存在する可能性があることです。しかし、これらの領域は必ずしも頂点に影響を及ぼすわけではなく、エッジにのみ影響します。時間依存グラフ付きAstar

時間をコスト関数として使用するので、各頂点(したがってエッジ)について、訪問者および/またはヒューリスティック内の到着時間を得ることができます。しかし、ウェイトマップは読み込み可能なので、エッジを「長すぎる」ように変更することはできません。

一方、経路に依存するため、到着時刻がわからないためカスタムウェイトマップを作成できません。

フォーラムで知っておいたのは、ヒューリスティックを使用して、「悪い」頂点の場合にinfに設定することです。しかし、私が必要とするのは、「悪い」エッジを選択することです。

ヒューリスティック内で現在検査されているエッジにアクセスする方法について考えていますか(デフォルトでは入力は頂点ディスクリプタのみです)。

私はexamine_edge訪問者で意思決定を行うことができると知っていますが、astarにこのエッジが悪いことを知らせるためにはどうしたらいいですか?たぶん私は外部ブールの "不良エッジ"プロパティマップ(すべての頂点)を作成することができ、現在のエッジが "悪い"場合は、examine_edgeビジター内のターゲット頂点をtrueに設定しますか?この「不良エッジ」プロパティマップはヒューリスティックによってアクセスできます。 しかし、これは最善の解決策ではないようです。

他のアイデアはありますか?

ありがとうございます!

答えて

1

これらの問題を解決するための一般的なアプローチは、ノードが元のノードよりも多くの情報を含む新しいグラフを作成することです。あなたのケースでは、可能な異なる時間インスタントごとに、各ノードの複数のコピーを持つグラフを作成することを検討してください。次に、適切な時点で対応するノード間にエッジがある場合、各エッジを一対のノードの間に移動させます。たとえば、常に開いているエッジは、ある時点のノードから、後の時点で対応するノードに移動し、特定の時点でのみアクティブなエッジは、その時点でグラフに表示されます。

これはグラフのサイズを吹き飛ばすという欠点がありますが、グラフをゆっくりと評価するという選択肢がある場合、このアプローチはかなり妥当かもしれません。