問題タブ [stable-marriage]

問題文：

男女同数です。各男性は、各女性に対する選好スコアを持っています。女性も男性も同様です。男性も女性もそれぞれに興味があります。関心に基づいて、選好スコアを計算します。

したがって、最初は、列を持つファイルに入力がありxます。最初の列は個人 (男性/女性) ID です。ID は0...からの数字に他なりませんn。（前半は男子、後半は女子）。残りのx-1列には関心があります。これらも整数です。

さて、このn by x-1マトリックスを使用して、マトリックスを考え出しましたn by n/2。新しいマトリックスには、すべての男性と女性が行として含まれ、列には異性のスコアが含まれます。

スコアを降順にソートする必要があります。また、ソート後にスコアに関連する人物の ID を知る必要があります。

だから、ここではハッシュテーブルを使いたかった。

スコアを取得したら、いくつかのルールに従う必要があるペアを作成する必要があります。

n by n/2私の問題は、どの男性/女性が女性/男性をどれだけ好むかという情報を提供する必要がある の 2 番目のマトリックスにあります。これらのスコアを並べ替えて、男性/女性の 1 番目に優先する女性/男性、2 番目に優先する女性/女性などがわかるようにする必要があります。

私が使用しているデータ構造について、良い提案が得られることを願っています。PHPかPerlの方が好きです。

注意:

これは宿題ではありません。これは、安定した結婚アルゴリズムの少し修正されたバージョンです。私は実用的な解決策を持っています。私は自分のコードを最適化することに取り組んでいます。

これは安定した結婚の問題に非常に似ていますが、ここでは、彼らが共有する興味に基づいてスコアを計算する必要があります. それで、wiki ページhttp://en.wikipedia.org/wiki/Stable_marriage_problemで見られるように実装しました。

私の問題は問題を解決していません。私はそれを解決し、それを実行することができます。私はただより良い解決策を見つけようとしています。そこで、使用するデータ構造のタイプについて提案を求めています。

概念的には、ハッシュの配列を使用してみました。配列インデックスは個人IDを提供し、その中のハッシュはids <=> scoresソートされた方法で提供します。最初に、ハッシュの配列から始めます。ここで、ハッシュを値で並べ替えましたが、並べ替えられたハッシュを配列に格納できませんでした。したがって、ソート後にキーを保存し、これらを使用して最初のソートされていないハッシュから値を取得しました。

ソート後にハッシュを保存できますか? より良い構造を提案できますか？

私は現在アルゴリズムの本を読んでいて、安定結婚問題に出くわしました。そして、気になる質問が思い浮かびましたが、本は答えません。すべてのSMPで、それぞれがもう一方を最も優先する1つのペアを常に持つことは可能ですか？古典的な結婚の例のように。1人の女性と1人の男性がいて、どちらも好みの上位にランク付けされているペアは常にありますか？

ゲームTiny Towerには、さまざまな属性でスキル 0 ～ 9 のさまざまな「Bitizens」があります。

そして、3人のビティズンが働けるビジネスがあります。各ビジネスは、小売、クリエイティブ、サービス、レクリエーション、食品のいずれかのカテゴリに分類されます。ビジネスまたは Bitizen の数が一致することは決してありませんが、簡単にするために、ポジションの数が Bitizen の数と一致すると仮定できます。

たとえば、小売業である帽子屋があり、価値の高いビチズンretailが好まれます。上記の例では、Micheal は小売業に非常に適しています。

アルゴリズム的に、最も適切なスキルを持つ Bitizen をポジションに配置するにはどうすればよいですか? 私はその問題に挑戦しようとしましたが、実際に問題を効果的に解決する方法で頭を悩ませました。

経済シミュレーションを再現するための最適なアルゴリズムを見つけたいと思います。

さまざまな顧客グループを作成します。各グループには、顧客が何を購入したいかを決定する特定のパラメーターがあります。それらのパラメータの例：品質、機能、マーケティングなど。

私のゲームの各プレーヤーは、さまざまな製品を作成し、さまざまな顧客グループのニーズを満たそうとします。次に、各製品に価格を設定し、生産量（数量限定）を決定します。

したがって、一方では、顧客の数が限られています。彼らの反対側では、あなたは限られた量の製品を持っています。これらの量は等しい必要はありません（ただし、等しい場合もあります）。したがって、顧客の数に対して製品が多すぎるか、製品の量に対して顧客が多すぎる可能性があります。しかし、確かなことが1つあります。不足がない限り、すべての顧客が製品を購入したいと考えています。

安定した結婚アルゴリズムを見つけましたが、これは私の状況に正確に適合していないようです。これに最適なアルゴリズムは何ですか？

この質問は、同様の主題に関する以前の投稿に関連しています： 経済シミュレーションのアルゴリズム？

好みに基づいて学生のグループを小さなグループに分類するアルゴリズムを見つけようとしています。各生徒は、一緒に働きたい生徒を 3 人、一緒に働きたくない生徒を 3 人選びます。残りは「必要に応じて使用できる」と想定されます。

生徒の好みに最も合う生徒の組み合わせを見つける最善の方法は何ですか?

私は現在アルゴリズムの本を読んでいて、安定したマッチング問題に遭遇しました。そして、気になる疑問が頭に浮かんだのですが、本は答えていません。問題は次のとおりです。
マッチングが安定していない場合は、任意のブロッキング ペア (w、m) を選択し、それらをマッチングします。また、以前のパートナーと一致します。そして繰り返す。これは、安定したマッチングに到達するための正しいアルゴリズムですか?
答えはノーのようです。しかし、反例が思いつきません。助けてくれる人はいますか？

安定した結婚クラスに makeMatches メソッドを実装する必要があります。コードは次のアルゴリズムに従う必要があります。

しかし、私は自分のエラーを見つけることができません。プログラムはカップルを最初の選択に依存させますが、その後は続行せず、カップルを設定します。私のコードを見て、何が問題なのか教えていただけますか?

Person.java はインストラクターから提供されます。

StablaMarriage.java は、コードを実装する必要があるものです。

次の問題は、Jon Kleinberg と Éva Tardos による「アルゴリズム設計」、第 1 章、演習 3 からのものです。説明をできるだけ短くしました (括弧内または引用ブロックの外側の注釈)。

2 つのテレビ ネットワークがあるとAしますB。nゴールデンタイムの番組枠があり、各ネットワークにはテレビn番組があります。各ネットワークは、できるだけ多くの市場シェアを獲得するために、スケジュール (各ショーを個別のスロットに割り当てる) を考案したいと考えています。[...] 各番組には固定の評価があります [...]。まったく同じ評価の番組は 2 つないと仮定します。ネットワークがそのタイムスロットにスケジュールする番組の評価が、他のネットワークがそのタイムスロットにスケジュールする番組よりも高い場合、そのネットワークはそのタイムスロットを獲得します。目標は、できるだけ多くのタイムスロットを獲得することです。

各ネットワークから 1 シーズンのスケジュールを取得するため、最初のネットワークはスケジュールsを提供し、2 番目のネットワークはスケジュールを提供しTます。

[...]どちらのネットワークも自分のスケジュールを一方的に変更できず、より多くのタイムスロットを獲得できない場合、スケジュールのペア (S、T) は安定していると言えます。

つまりS'、最初のネットワークにより多くのタイムスロットを与えるスケジュールはなくT'、2 番目のネットワークにも同様のスケジュールはありません。

[質問です]:テレビ番組と視聴率のすべてのセットについて、常に安定したスケジュールのペアがありますか?

私の直感では NO です。安定したスケジュールを想像できる問題の唯一の例は、最初のネットワークの最高のショーが 2 番目のネットワークの最悪のショーよりもさらに悪い場合です。つまり、1 つのネットワークがすべてのスケジュールに勝つことができる場合です。 . それ以外の場合、1 つのネットワークが 2 つのエントリを交換してより多くのスロットを獲得し、他のネットワークがスケジュールを変更して、常にこれらのスロットを獲得できると思います。

安定した結婚の問題について 2 つの質問があります。

n 人の男性と n 人の女性がいて、各人が異性のすべてのメンバーを好みの順序で 1 から n の間の一意の番号でランク付けした場合、男性と女性を一緒に結婚させて、両方の異性の人がいないようにします。むしろ、現在のパートナーよりもお互いを持っています。そのような人がいなければ、すべての結婚は「安定」しています。

http://en.wikipedia.org/wiki/Stable_marriage_problemの解決策を知っています。wiki ページには解決策が説明されていますが、この解決策がどのように採用されたかについては説明されていません。

Q1:この種のペアリング問題の考え方を説明できる人はいますか? したがって、同様の問題については、考え方があります。

Q2:可能なすべての安定した結婚の組み合わせが必要な場合はどうすればよいですか?