180個のボールを持っています。
70個のバケツを持っています。
各ボールの値は、ボールが入っているバケットによって異なります。
ball1 = { 1, 14, 2, 3, 4 ... } //70 values in total for each bucket
ball2 = { 24, 2, 23, 2, 5 ... }
...
各バケツには運べるボールの最大数がありますが、70 個のバケツが運べるボールの総数は 180 です。つまり、180 個のボールすべてが正確に収まります。(すべてのバケツは少なくとも 1 つのボールを運ぶ必要があります)
{bucket1, 3} {bucket2, 1} { bucket3, 2} {bucket4, 1} ...
これでボールの配置をどのように最大化しますか?
ブルートフォースを試みましたが、順列の数を数えた後、すぐに後悔しました。
二部グラフの最大重みマッチング問題のようです。トリッキーな部分は、問題を解決するために多項式時間アルゴリズムを適用できるように、2 部グラフを構築する方法です。
問題を簡単にするために、3 つのボールと 2 つのバケツがあるとします。
Ball 1: {1, 10},
Ball 2: {9, 20},
Ball 3: {7, 9};
Bucket 1: 2
Bucket 2: 1
次のようなグラフを作成したいと思います。
主なアイデアは、ノードの左側の部分がボールを表し、残りの部分がバケットのノードになるようにバイグラフを構築することです。そして、各バケットの容量と同じ数のノードを与えたので、最大重みマッチング アルゴリズムを適用して問題を解決できます。
複雑であるため、これは「一定の時間内にどのような最適な結果を達成できるか」というアプローチによって最もよく解決されるタイプの問題です。真のグローバル最大値が必要な場合、これは機能しません。
私の最初のアプローチは、シミュレートされたアニーリングに沿ったものです。
1) ボールをランダムに配置します (各バケットに少なくとも 1 つのボールがあるという制約に従います)。
2）目的関数を計算します（ブルートフォースアプローチからすでにこれを持っている必要があります）
3) 2 つのボールをランダムに交換する、1 つのボールを別のバケットに移動する (制約が許す場合) などの操作を検討してください。
4) 目的関数を再計算する
5) 目的関数が優れている場合は常に変更を受け入れますが (これは重要です)、exp(-constant * time) で減衰する確率で目的関数が悪い場合も変更を受け入れます。（それは温度関数と呼ばれます）。
6) もう一度一周します。
このアプローチにより、良好なバケットがくっつき、初期段階で状態が極大値から跳ね返ることができます。ここでの科学は、「定数」の適切な値を把握することです。