1

アリス、ボブ、チャーリーの3人がいるとしましょう。

それぞれにリソース、Aplles、Bannanas、Coconutsがあるとしましょう。

それぞれにこのリソースが3つあります。

アルゴリズムの目標は、1対1の取引を行い、それぞれが3つのリソースのそれぞれの1つになるようにすることです。それらの取引のリストは私が入手したいものです。

理想的には、これを解決する方法を知りたいです。しかし、私はこの種の問題、または私が調査してアイデアを得ることができるそれに類似した問題の名前を喜んで解決します。

私が取り組んでいる問題には約600のオブジェクトがあり、それぞれがランダムな量/タイプの開始リソースを持つ約1000人です（最終結果を満たすのに十分なリソースがあると仮定して）。したがって、理想的には、提供されるソリューションは次のようになります。そのような規模で実行可能です。しかし、私は私が得ることができるものは何でも取ります、私はただある種の出発点が必要です。

4

3 に答える 3

1

種類1、...、種類nのxnリソースの合計数がx1リソースであると想定します。

k人がいて、それぞれがy1、y2、...、ykリソースを持っていると仮定します。

次に、人iを選び、最も普及しているリソースを割り当てます。割り当てが完了したら、対応するxjをデクリメントします（つまり、リソースjがiに割り当てられている場合は、xjをデクリメントします）。

すべてのリソースが割り当てられるまで繰り返します。

これは、ものを最も均等に割り当てる方法です。それはあなたが一連の取引を気にしないことを前提としていますが、最終結果自体です。

于 2013-03-06T01:29:32.837 に答える
1

ElKaminaとTylerDurdenの答えはまともですが、栗曽が1対1の取引をしたい、人々が複数の商品や複数の商品を持っている可能性があることを考慮していないようです。私にはそうする素朴な解決策があります。

元の例は少し単純化されすぎたと思うので、別の例を見てみましょう。

  c1 c2 c3 c4
A 5  0  1  0
B 0  1  0  1
C 0  6  2  0

ここで、A、B、Cは人であり、c1、c2、c3、c4は商品です。

まず、簡単に実行できる理想的な分布を計算しましょう。商品ごとに、合計を人数で割って切り捨てると、全員が次のようになります。

  c1 c2 c3 c4
A 1  2  1  0
B 1  2  1  0
C 1  2  1  0

ここで、人Xが理想的な位置に到達するために必要なものの量を示すWANT関数を定義しましょう：WANT（X、c）= IDEAL（c）-Xc。

  c1  c2  c3  c4 sum
A -4  2   0   0  -2
B  1  1   1   0   3
C  1 -4  -1   0  -4

欲求の合計で並べ替えた人のリストを作りましょう。最も裕福な人、この場合は最も欲求が低い人、この場合はCを取り上げ、彼が最も欲しがっている商品を最も提供している人と彼を一致させることによって、彼の欲求を満たすようにしましょう。彼らが取引を行うことができれば、素晴らしいですが、そうでない場合は、一致するものが見つかるまで続けます（最終的には一致が保証されます）。この例では、Cにはc1が必要です。最も多くのc1を提供するのはAであり、商品を繰り返し処理します。Aにはc2が必要であり、Cには余剰のc2があるため、それらを交換します。リスト内の位置を更新するか、必要がなくなった場合は削除します。誰も欲しがらなくなるまでこれを繰り返します。これは適切に均等な分配を生成しませんが、1回の取引で1ずつ到達できる限り均等になります。

これは確かに素朴な解決策であり、最も裕福な人が必要な商品の見返りに物を提供する可能性が最も高いというヒューリスティックを備えています。複雑さは高いですが、順序付きリストを使用すると、指定した数に対して管理可能である必要があります。

于 2013-03-06T13:42:58.170 に答える
0

これを言い換えると、次のようなリストのセットがあるとしましょう。

{1、1、1}
​​{2、2、2}
{3、3、3}

そして、次のようなセットができるまで、異なるセットの要素を交換したいとします。

{1、2、3}
{1、2、3}
{1、2、3}

ここで、これらのリストを単一の行列と見なすと、一方の行列がもう一方の行列の逆であることに気付くかもしれません。この反転は、1-2-3の対角線を入れ替えることで実行できます。

したがって、リスト1のアイテム2は行2のアイテム2と交換され、リスト1のアイテム3はリスト3のアイテム1と交換され、最後にリスト2のアイテム3はリスト3のアイテム2と交換されます。

要約すると、対角線を入れ替えて行列の反転を行います。

于 2013-03-05T23:36:52.943 に答える