0

N 個の長方形のボックスとそれらの間の M 個の接続が与えられた場合、すべての接続の長さの合計が最小になるように、それらを平面に効率的に配置したいと考えています。

私が経験した唯一のプロセスは、平面を N 個以上のスペースを持つグリッドに分割し、最大数の接続を持つボックスを、対角線上にあるコーナー スペースから始めて、グリッド内でさらに離して配置することです。

1 つのボックスがすべての N-1 ボックスに接続されていて、それらが唯一の接続である場合、これは効率的ではない可能性があります。1 つのボックスが中央にあり、他のすべてのボックスがその周りにあると予想されます。

そのような問題の標準的な解決策はありますか? そのような問題にアプローチする方法についての指針を得ることができますか?

4

1 に答える 1

1

これは非線形最適化問題であり、たとえばシミュレーテッド アニーリングや勾配降下法などの一般的な目的関数の最小化を使用して解決できます。

ボックスの任意のレイアウトが与えられた場合、L は、そのレイアウトが与えられたすべての接続の長さの合計を示します。L を最小限に抑えたいとします。単純なシミュレーテッド アニーリング スキームは次のように機能します。

layout = random_layout()
t = 1.0
While(true)
  L = sum_of_lengths(layout)
  layout' = move_one_box(layout)
  L' = sum_of_lengths(layout)
  if (L' < L  or  random(0..1) < t)
    layout = layout'
  t = t * 0.999

最初は、アルゴリズムはボックスをランダムに移動するだけですが、t が減少すると、アルゴリズムは貪欲なオプティマイザーに徐々に変化します。アルゴリズムを複数回実行して、最良の結果を選択できます。これはシミュレーテッド アニーリング スキームです。

于 2013-08-26T08:40:17.247 に答える