一般的な目標
いくつかの固定ノード @ ランダムな位置に配置された「小さな」10x10 グリッドがあるとします。
. . . . . . . . . .
. . . . . . . . . .
. . . @ . . . . . .
. . . @ . . . . . .
. . . . . . . . . .
. . . . . @ . . . .
. . . . . . . . . .
. . . . . . . @ . .
. . . . . . . . . .
. . . . . . . . . .
そして、値が隣接するノードの関数である最大 30 個のノードがあるとします (隣接は、スポットを囲む 8 つのポイントのいずれかとして定義されます)。つまり、マップ上に配置されたノード A と B を考えると、
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . A @ . . B . . . . . A @ . . . . . .
. . . @ . . . . . . . B . @ . . . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . @ . . . . . . . . . @ . . . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . @ . . . . . . . . . @ . .
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
A と B は 2 番目のマップでは隣接しているが、最初のマップでは隣接していないため、これら 2 つのマップでは A と B の両方の出力が異なる場合があります。
私たちの目標は、すべてのノードの合計が最大になるように (または少なくともかなり良い)、マップ上にすべてのノードを配置することです。
特定の問題に対する追加の制約
- ノードには約 8 つの「クラス」があります。各クラスのすべてのノードは同じように動作するため、これを使用して検索スペースを減らすことができます。
- 特定のノードが全体的な値を支配しているため、これを知っていると、これらのコア ノードを中心に最適化できます。
- 通常、各ノードには 2 つまたは 3 つの他のクラスのノードがあり、それらのクラスのノードに隣接しているときにその値が増加します。
- すべての値が 0 以上です。
- ほんの数秒で適切な適合を見つけたい..計算の余地はありますが、5 秒でかなり優れたソリューションは、2 日で完全なソリューションよりも優れています。
素朴で貪欲なアプローチ
私が今していることは、単純な貪欲なアプローチを取り、結果を微調整することです。
グリッド上のすべての場所を見て、まだ配置していないすべてのノードについて検討し、見つかった最適な配置を選択します。「ベスト」ポジションが複数ある場合は、ランダムに 1 つを選択します。すべてのノードが配置されるまでこれを行います。
この最初のプロセスの後、ランダムにノードを選択し、開いているすべてのスポットを調べて、ノードのより良い場所を見つけようとします。ノードを移動すると、隣接するノードだけでなく、ノード自体に与える影響も考慮されるため、全体的に最適な場所にある場合は移動しません。レイアウトを「微調整」するために、これを数千回行います。
ランダムな要因により、同じ入力に対して非常に異なる出力が得られる可能性があるため、このプロセスを数回実行して最良の結果を取得します。
質問
この素朴で貪欲なアプローチよりもうまくやるにはどうすればよいでしょうか?
アプリオリな隣接情報を考慮した、はるかに優れた解決策があるはずだと思いますが、それは私を避けています。任意の考え、リンク、またはヒントをいただければ幸いです。