情報処理学会 第83回全国大会 会期:2021年3月18日~20日 会場:オンライン開催 情報処理学会 第83回全国大会 会期:2021年3月18日~20日 会場:オンライン開催

1J-03
サイズ5安定結婚問題の安定マッチング数の上限についての考察
○佐藤 陸(豊橋技科大)
安定結婚問題(SMP)は同数存在する男女がそれぞれ異性に対する好みの順序を持つときに、「駆け落ち」が存在しないような(安定な)マッチングを求める問題を指す。
SMPの研究の一分野として「安定マッチングの数」を考察が行われており、これまでに男女が4人ずつ存在する場合(サイズ4)の安定マッチングの数の上限および具体的なインスタンスが発見されている。
本研究ではサイズ5の場合を考え、安定マッチングがより多くなるようなインスタンスの構造について検討を行い、それに基づいて実際にこれまで発見されていなかった安定マッチング数を持つインスタンスを発見した。