掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.24286

安定なお見合い
投稿者---sinobu(2005/11/21 18:52:59)


C++のプログラムを初めてまだまだ日が浅いので,
「こいつ何もわかってない」といった発言があるかもしれませんが,
平にご容赦を。

講師の方が出した,できたら面白プログラムとして
以下のようなものを考えてみよとの事で,

「お見合い」
{N人の男性とN人の女性が集団見合いし,おのおの異性
を好みで順位付けした。この順位を基に,安定な縁結び
の仕方を考えるプログラムを作成する。}
{仮に男性M1と女性F1が結婚し、男性M2と女性F2が結婚したのに、
実はM1はF2の方が好みで、F2はM2よりM1の方が好みだった場合、
将来問題がおきかねない
このようなことがないのがここで言う安定な結婚の定義}

と,このような問題なのですが,
とりあえず,順位付けを二次元配列で行い,それを基に
順位が男女で1位同士を縁結びするところまでは
できたのですが、その先がイマイチ何をもって,実装できるかが
思いつかないのです。環境は使っているソフトはVC++でOSはXPです。
もしお暇なら、考えていただけると幸いです。

下にとりあえずできたと思っている所までのソースを
書いておきます。


#include<iostream>
#include<stdio.h>

using namespace std;

int main()
{
  int N1=0;
  int N2=0;
  int Co=0;
  int M[3][3]={{2,1,3},  //M0のF0,F1,F2に対する順位付け

      {3,1,2},   //M1のF0,F1,F2

      {1,3,2}};  //M2のF0,F1,F2

  int F[3][3]={{1,3,2},  //F0のM0,M1,M2に対する順位付け

      {3,1,2},   //F1のM0,M1,M2

      {1,3,2}};  //F2のM0,M1,M2

    
  /*お互いが1位同士をカップルにする*/
  for(N1=0;N1<=2;N1++){
    if(N2>=2){
      N2=0;
    }
    
    if(M[N1][N2]==1&&F[N2][N1]==1){
      for(Co=0;Co<=2;Co++){
        M[N1][Co]=0;
        F[N2][Co]=0;
      }
      cout<<"M"<<N1<<"と"<<"F"<<N2<<"はカップル\n";
    }
    for(N2=1;N2<=2;N2++){
      if(M[N1][N2]==1&&F[N2][N1]==1){
        for(Co=0;Co<=2;Co++){
          M[N1][Co]=0;
          F[N2][Co]=0;
        }
        cout<<"M"<<N1<<"と"<<"F"<<N2<<"はカップル\n";
        }
    }
  }







この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:安定なお見合い 24288 REE 2005/11/21 19:56:58
<子記事> Re:安定なお見合い 24291 επιστημη 2005/11/21 21:34:16
<子記事> Re:安定なお見合い 24294 たいちう 2005/11/21 22:49:15
<子記事> Re:安定なお見合い 24348 sinobu 2005/11/23 23:46:57


No.24288

Re:安定なお見合い
投稿者---REE(2005/11/21 19:56:58)


>「お見合い」
>{N人の男性とN人の女性が集団見合いし,おのおの異性
>を好みで順位付けした。この順位を基に,安定な縁結び
>の仕方を考えるプログラムを作成する。}
>{仮に男性M1と女性F1が結婚し、男性M2と女性F2が結婚したのに、
>実はM1はF2の方が好みで、F2はM2よりM1の方が好みだった場合、
>将来問題がおきかねない
>このようなことがないのがここで言う安定な結婚の定義}

思いつきですが・・
まず、仮に適当にカップリングします。
そのあと、不安定な部分がないか探してみて、
あったら、そこのカップルを入れ替えます。(例の場合だとM1-F2, M2-F1)
後は、それを繰り返せば、最終的に安定になる(かも?)



この投稿にコメントする

削除パスワード

No.24291

Re:安定なお見合い
投稿者---επιστημη(2005/11/21 21:34:16)


カップルはN!通りの組み合わせだから、全部列挙して安定なのを探す。



この投稿にコメントする

削除パスワード

No.24294

Re:安定なお見合い
投稿者---たいちう(2005/11/21 22:49:15)


Nが小さければ(10程度まで)επιστημηの方法、
大きければREEさんの方法でしょうね。
どっちにしろ、↓のような関数が必要ではないでしょうか。

double Evaluate(int choice[]);
// choice[]は、各男性がどの女性と結婚するか(もちろん逆の表記も可)
// 戻り値は全員の安定度の合計

この実装ですが、問題文の『安定な結婚の定義』は不完全だと思いますので、
適当に補完してやる必要があるでしょう。


この投稿にコメントする

削除パスワード

No.24306

Re:安定なお見合い
投稿者---REE(2005/11/22 10:46:18)


>Nが小さければ(10程度まで)επιστημηの方法、
>大きければREEさんの方法でしょうね。
>どっちにしろ、↓のような関数が必要ではないでしょうか。
>
>double Evaluate(int choice[]);
>// choice[]は、各男性がどの女性と結婚するか(もちろん逆の表記も可)
>// 戻り値は全員の安定度の合計

私の方法では、この関数はあまり役に立ちません。
ところで、安定度ってどういう定義でしょう?
真偽値で充分な気もしますが・・

>この実装ですが、問題文の『安定な結婚の定義』は不完全だと思いますので、
>適当に補完してやる必要があるでしょう。

どの辺が不完全でしょうか?



この投稿にコメントする

削除パスワード

No.24308

Re:安定なお見合い
投稿者---たいちう(2005/11/22 12:33:21)


REEさんの方法で、不安定な部分を入れ替えた場合、
新たな不安定が発生する可能性はないでしょうか?

上の例では、F1の好みがM1, M3, M2の順で、
M3の好みがF1の場合など。

このような評価のためにも、全体を評価する方が簡単だと思いました。

> どの辺が不完全でしょうか?

安定な状態が存在しない場合のことに触れていないため、
不完全な定義と思いました。

『安定な状態が存在しない場合』を思いつかないので、
きっとプログラムを作った方が早いですね。
N=5程度までの全ての好みの前提を試すならば
瞬時に計算できると思いますので、明日にでも作ってみます。

常に安定な状態が存在するのならば、この定義は完全なのでしょう。


この投稿にコメントする

削除パスワード

No.24311

Re:安定なお見合い
投稿者---円零(2005/11/22 15:29:49)


「安定度」の定義って何でしょうか。
この問題において、合計することに意味のある数値が設定できるとは思えません。

例えば、M1の好みの順位がF2, F3, F1として、
F1の好みの順位がM3, M2, M1であったとします。
M1とF1のカップルは、互いに最も嫌いな相手とのカップルですが、
M1とF1が他の全ての人から嫌われていた場合、それでも「安定」なカップルとなります。
重要なのは全体の満足度ではなく、個々の比較において逆転が起きないこと、なんですが。


この投稿にコメントする

削除パスワード

No.24312

Re:安定なお見合い
投稿者---UEC(2005/11/22 15:36:04)


>「安定度」の定義って何でしょうか。
プログラムの具体例は載っていませんが、この問題について、電子情報通信学会誌の2005年3月号にあります。
「解説 安定結婚問題 宮崎修一」

http://www.ieice.org/jpn/books/mokuji/2005/2005_03.html

参考にして下さい。



この投稿にコメントする

削除パスワード

No.24315

Re:安定なお見合い
投稿者---円零(2005/11/22 16:00:34)


そのサイトで読めるのって目次だけですよね?
ちょっと参考にはなりにくい気が。

まあ「安定結婚問題」というキーワードは得られたので、
Googleで検索したら単純な入れ替えアルゴリズムではループする例が見つかったのは参考になりましたが。
http://tnt.math.metro-u.ac.jp/labo/grad/2003/egu/stable_marriage_probrem_1.htm


この投稿にコメントする

削除パスワード

No.24316

Re:安定なお見合い
投稿者---円零(2005/11/22 17:04:18)


っていうかアルゴリズムについてはズバリ解答がありました。
http://www.kt.rim.or.jp/~tfj/mathmate/4
"Gale-Shapley's Algorithm"と言うそうです。


この投稿にコメントする

削除パスワード

No.24320

Re:安定なお見合い
投稿者---ぽへぇ(2005/11/22 22:28:08)


>っていうかアルゴリズムについてはズバリ解答がありました。
>http://www.kt.rim.or.jp/~tfj/mathmate/4
>"Gale-Shapley's Algorithm"と言うそうです。

奥村本にはソースコードまでついています。

http://www.amazon.co.jp/exec/obidos/ASIN/4874084141/250-7157702-4716266




この投稿にコメントする

削除パスワード

No.24313

Re:安定なお見合い
投稿者---REE(2005/11/22 15:36:11)


>REEさんの方法で、不安定な部分を入れ替えた場合、
>新たな不安定が発生する可能性はないでしょうか?

もちろんありますよ
でも、安定かどうかだけの判断はあまり有用ではなく、(不安定な場所が分かるのなら使えます)
不安定があったら、入れ替え、戻り値は入れ替えたかどうかになる関数があれば、それだけで事足ります。
そういう意味で、あまり使えないと判断しました。

>> どの辺が不完全でしょうか?
>
>安定な状態が存在しない場合のことに触れていないため、
>不完全な定義と思いました。

問題としては、不完全かもしれませんが、
『安定な結婚の定義』としては、完全ではないですか?
#まあ、普通は、解がなければその旨を表示するのが自然でしょう。



この投稿にコメントする

削除パスワード

No.24323

Re:安定なお見合い
投稿者---たいちう(2005/11/23 07:43:53)


まとめてレス

> この問題において、合計することに意味のある数値が設定できるとは思えません。

確かに。私の書いた関数宣言でも、戻り値にbool型か、せめて不安定の組数のint型
にすべきでした。


> 奥村本にはソースコードまでついています。

ってことは、Vectorでダウンロードできますね。
marriage.cというファイルでした。

http://www.vector.co.jp/soft/data/prog/se002453.html


> 問題としては、不完全かもしれませんが、
> 『安定な結婚の定義』としては、完全ではないですか?
> #まあ、普通は、解がなければその旨を表示するのが自然でしょう。

解が得られない可能性を憶測し、定義に何かを追加することを
考えていました。私のひとりよがりでした。


この投稿にコメントする

削除パスワード

No.24348

Re:安定なお見合い
投稿者---sinobu(2005/11/23 23:46:57)


皆々様、様々な情報をありがとうございます。
具体的なソースの例も上げていただき、大変参考になりました。
私がこの問題を解ける日も、そう遠くはなくなったようです。

おかげで随分と考え易くなりました。
自分で考えた部分も生かしつつ、この問題に対する自分の
プログラムというものを完成させる所存です。
本当にありがとうございます。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧