アルゴリズム - 安定結婚問題

Question

ゲームTiny Tower 0-9異なる属性に熟練している様々な「Bitizens」は：

Michael: 
a) retail: 9 
b) creative: 2 
c) service: 7 
d) recreational: 4 
e) food: 6 

そして、それは、ここでのビジネスを持っています3人のBitizensが働くことができます。各事業は、小売り、創造的、サービス、レクリエーション、食品のいずれかのカテゴリーに分類されます。企業の規模とBitizensの間には決して一致はありませんが、ポジションの数が噛み付きの数と一致すると仮定することが容易になります。

たとえば、小売業のハットショップがある可能性があります。そのため、BitZensはretailという値が高くなります。上記の例では、Michealは小売業に適しています。

私はアルゴリズム的に、最も関連性の高いBitizensでポジションを埋めることができますか？私は問題を解決しようとしましたが、実際に問題を効果的に解決する方法で私の周りを包み込むのに問題がありました。

Answer 1

どこに置いても、特別な「ポイント」は同じ価値があるとしましょう。たとえば、クリエイティブとフードの2つのビジネスがある場合、創造力と創造力にそれぞれ20と20を持つことが、それぞれに11を持つよりも常に良いと想定しています。

この場合、問題はAssignment problemの例です。これは、多項式時間、特に時刻O（n^3）において解くことができるという点で「容易」であることが知られている。この問題を解決するための標準的な方法はHungarian algorithmです。私はウィキペディアのページよりもはるかに説明することはできませんが、これは非常に詳細ですが、あなたが何かそこにこだわっている場合は、ただ質問してください。あなたはbitizensや企業の膨大な数を持っている場合は、このアルゴリズムが実行不可能であるように

は、私はこの問題はsimulated annealingかevolutionary algorithmsなどのおおよその方法で攻撃するのは非常に従順になると思います。

私の元々の仮定が間違っている場合（たとえば、少なくとも1つのタイプの企業があるとよい場合など）、これらの不正確な方法を試してください。任意の与えられた作業者 - 業務割当順列の価値を反映する目的関数を設計することに集中する。

Answer 2

属性をすべて一括して最小化する目的が1つしかない場合は、assignment problemで問題を解決できます。そうでなければ、問題はmulti-index assignment problemのようなものです。これはNP困難です。

したがって、合理的な解決方法を理解するために、具体的なケースについて詳しく説明してください。