11

環境

手続き型生成を使用して 3D ゲームを作成しています。私は、プレイヤーがマップ内の他の部屋にいつでも到達できるように、多数の事前生成された部屋を接続しようとしています。部屋には、接続する廊下を接続する必要がある「可能なエントリ ポイント」があります。ただし、部屋内の他のすべてのエントリ ポイントからすべてのエントリ ポイントに到達できるわけではありません。たとえば、ピット トラップがある場合、一番下のプレイヤーは部屋を通って一番上に移動できず、別の方法を見つける必要があります。

問題

3D 空間に埋め込まれた既存の一連の有向グラフが与えられた場合、サブグラフをより大きなグラフに接続する最小の合計長の一連の (双方向) パスを追加します。それができない場合 (一部の調査ではこれが NP 困難であることが示されているため)、短い時間で計算できるようにパスをできるだけ短くします。

これまでの作業

私の最善の解決策は、すべてのノードの Delaney Triangulation を作成するこの手続き型生成の投稿に基づいています。部屋の強く接続された各コンポーネント (たとえば、ピット トラップの最上階と最下階) を個別のノードとして扱い、そこから MST を構築しますが、これにより興味深い可能性のいくつかが制限されます (たとえば、開始した場所に戻るための 2 つの一方向パス)。

この問題を解決するためのより良い方法を知っている人はいますか?

4

2 に答える 2

0

この問題の埋め込み部分は非常に混乱するので、有向グラフを取得するための接続コストを見積もると仮定します。有向グラフには、最小コストの強く接続されたアークサブグラフが必要です。次に、貪欲なアルゴリズムを使用して埋め込みを見つけます。

多項式時間での 2 近似解の場合: 任意のルート頂点を選択し、Chu--Liu および Edmonds によるアルゴリズムを使用して、最小コストのルート方向および葉方向にまたがる樹木を計算します。これらの結合を返します。すべての強く接続されたアーク サブグラフには、ルート方向とリーフ方向にまたがる樹枝状突起が含まれているため、これは 2 近似です (ただし、最小コストである必要はありません)。あなたのリンクの 1 つから、Keith Randall もこのアイデアを持っていたことがわかりました。

実装できるヒューリスティックはいくつもあります。それらは非常にうまく機能するかもしれませんが、私にとってはあまり興味がありません。それらの振る舞いが悪いことを懸念している場合は、前述の 2 近似でそれらを「バックストップ」できます。

本当に最適なソリューションが必要な場合は、おそらく整数計画法が最善の策です。整数プログラムとして定式化されたこの問題は、TSP に似ています。TSPのプログラムはこんな感じ。

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
(-) for all v, sum_{v -> w} x(v -> w) = 1
(-) for all w, sum_{v -> w} x(v -> w) = 1
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

あなたの問題のプログラムでは、マークされた制約を削除します(-)。これにより、選択されたアークが強制的にツアーになります。

minimize sum_{v -> w} cost(v -> w) x(v -> w)
subject to
for all subsets S of vertices, sum_{v -> w, v in S, w not in S} x(v -> w) >= 1
for all v -> w, x(v -> w) >= 0

このプログラムのデュアルは次のとおりです。

maximize sum_{subsets S of vertices} y(S)
subject to
for all v -> w, sum_{subsets S of vertices, v in S, w not in S} y(S) <= cost(v -> w)
for all subsets S of vertices, y(S) >= 0

これで、分岐限定ソリューションを TSP に適応させることができます。TSP には、チュートリアル資料がたくさんあるはずです。根本的に新しいことをする必要はありません。実際、櫛の不等式などはこの問題には当てはまらないため、サブツアーの制約/変数の生成に集中できます。

于 2014-03-26T16:58:39.343 に答える