0

問題文：

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

したがって、最初は、列を持つファイルに入力があり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ソートされた方法で提供します。最初に、ハッシュの配列から始めます。ここで、ハッシュを値で並べ替えましたが、並べ替えられたハッシュを配列に格納できませんでした。したがって、ソート後にキーを保存し、これらを使用して最初のソートされていないハッシュから値を取得しました。

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

4

1 に答える 1

1

以下は、ゲール・シャープレーアルゴリズムを実装していると思います。このアルゴリズムでは、各人の好みの順序が、異性のメンバーに対するスコアの配列として与えられます。

余談ですが、私はデビッド・ゲイルが亡くなったことを知りました（彼のウィキペディアのエントリを参照してください-彼は見逃されるでしょう）。

コードは言葉で表現されています。ウィキペディアで説明されているようにアルゴリズムをすばやく書き起こし、元のソースをチェックしませんでしたが、適切なPerlデータ構造を使用する方法がわかるはずです。問題の次元が大きくなる場合は、最適化を試みる前に、まずプロファイルを作成してください。

私はあなたの問題の特定の問題に対処しようとはしません。特に、興味に基づいて一致スコアを計算するという考えを完全に具体化しておらず、推測しようとするとイライラすることになります。

#!/usr/bin/perl

use strict; use warnings;
use YAML;

my (%pref, %people, %proposed_by);

while ( my $line = <DATA> ) {
    my ($sex, $id, @pref) = split ' ', $line;
    last unless $sex and ($sex) =~ /^(m|w)\z/;
    $pref{$sex}{$id} = [ map 0 + $_, @pref ];
    $people{$sex}{$id} = undef;
}

while ( defined( my $man = bachelor($people{m}) ) ) {
    my @women = eligible_women($people{w}, $proposed_by{$man});
    next unless @women;

    my $woman = argmax($pref{m}{$man}, \@women);
    $proposed_by{$man}{$woman} = 1;

    if ( defined ( my $jilted = $people{w}{$woman}{m} ) ) {
        my $proposal_score =  $pref{w}{$woman}[$man];
        my $jilted_score = $pref{w}{$woman}[$jilted];
        next if $proposal_score < $jilted_score;
        $people{m}{$jilted}{w} = undef;
    }
    $people{m}{$man}{w} = $woman;
    $people{w}{$woman}{m} = $man;
}

print Dump \%people;

sub argmax {
    my ($pref, $candidates) = @_;
    my ($ret) = sort { $pref->[$b] <=> $pref->[$a] } @$candidates;
    return $ret;
}

sub bachelor {
    my ($men) = @_;
    my ($bachelor) = grep { not defined $men->{$_}{w} } keys %$men;
    return $bachelor;
}

sub eligible_women {
    my ($women, $proposed_to) = @_;
    return grep { not defined $proposed_to->{$_} } keys %$women;
}

__DATA__
m 0 10 20 30 40 50
m 1 50 30 40 20 10
m 2 30 40 50 10 20
m 3 10 10 10 10 10
m 4 50 40 30 20 10
w 0 50 40 30 20 10
w 1 40 30 20 10 50
w 2 30 20 10 50 40
w 3 20 10 50 40 30
w 4 10 50 40 30 20
于 2010-03-27T13:20:43.930 に答える