7

次の問題に直面しています。

与えられた

  • ユークリッド平面上の一連の点。各点 P(x,y,w) には、座標と関連する正の重みがあります。
  • すべて同じサイズの長さ L を持つ U 正方形のセット。

ゴール：

  • すべての正方形に囲まれた合計ポイントの重みが最大になるように、正方形を割り当てます (位置を見つけます)。

ノート：

  • 正方形は軸平行でなければなりません
  • 四角形は重なる場合がありますが、囲まれた重みは 2 回以上カウントされません。

最適な割り当てを探しています。

私の質問:

  • これは既知の問題ですか (名前はありますか? 以前に調査されたことがありますか?)。
  • それにアプローチする方法はありますか？

（私が試したことについて言及することが期待されるかもしれません。最適な割り当てを探しているので、私のヒューリスティックなアイデアは実際には関係ありません。この時点では、最適な割り当てを見つける方法がわかりません）。

4

1 に答える 1

2

これは、加重最大カバレッジ問題の幾何学的な特殊なケースです。一般的な MCP は NP 困難であり、この特殊なケースも同様であると思いますが、一般的なケースとは異なり、おそらく効率的な多項式時間近似スキームを持っています。ただし、最適な解が必要な場合は、リンクされたウィキペディアの記事にある整数線形計画法の定式化を LP ソルバーに入力することをお勧めします。

maximize sum_j (w_j * y_j)
subject to
for all i, sum_i x_i <= U
for all j, sum_{i : j in S_i} x_i - y_j >= 0
for all i, x_i in {0, 1}
for all j, 0 <= y_j <= 1

w_j各ポイントの重みjが与えられ、セットは幅の正方形S_iでポイントをカバーするすべての可能性です。Lの意味は、x_iセットS_iが選択されているかどうかです。の意味は、y_jポイントjがカバーされているかどうかです。sを構成するための最も単純な 3 次アルゴリズムはS_i、左下の頂点がある点の座標に等しい x 座標と、ある点の座標に等しい y 座標を持つすべての正方形を列挙することです。またはカバレッジを犠牲にすることなく右に。

于 2013-08-27T13:31:16.810 に答える