3

ノードが 3x3x1 の部屋を表し、頂点が接近の必要性を表すグラフがあるとします。全体的な近さを最適化するには、3D 空間にどのように配置する必要がありますか?

例 (ランダム) データ構造:

{
    room1: [room2, room3],
    room2: [room1, room4],
    room3: [room5],
    room4: [room2, room5, room1],
    room5: []
}

（スタックオーバーフローで見られるほとんどの質問とは異なるため、どこでこの質問をするべきか正確にはわかりません。ソリューション/ヒューリスティックアルゴリズムのプログラミングに興味があります。）

4

2 に答える 2

2

NP完全である3Dビンパッキング問題の遠い従兄弟のようなにおいがします。構築ヒューリスティック（最初の適合、最適な減少、...）に続いて、メタヒューリスティック（タブーサーチ、シミュレーテッドアニーリング、遺伝的アルゴリズムなど）を試してください。Drools Planner、openTS、jgapなどのオープンソースソフトウェアがあります...

于 2011-07-14T08:43:06.110 に答える
2

隣接性が必要だと思います。

バックトラッキング検索では、グラフ内で接続されている他の部屋の数によって並べ替えられた部屋のキューを維持します (最も制約された変数ヒューリスティック)。次に、キュー内の各部屋について:

  • 可能なグリッド位置を決定し、そのうちの 1 つを選択します。
  • ループ内で、1 つの場所にしか配置できない他の部屋が存在するかどうかを判断し、そこに配置して、キューから削除します (前方チェック)。
  • 前のステップのいずれかが失敗した場合は、最後の選択ポイントに戻ります (グリッドへの変更を元に戻します)。
于 2011-07-13T09:32:24.827 に答える