0

问题陈述：

我们的男女人数相等。每个男人对每个女人都有一个偏好分数。每个男人的女人也是如此。每个男人和女人都有一定的兴趣。根据兴趣，我们计算偏好分数。

x所以最初，我们在一个有列的文件中有一个输入。第一列是人（男人/女人）ID。ID 只不过是来自0...的数字n。（上半场是男性，下半场是女性）。其余x-1列将有兴趣。这些也是整数。

现在，使用这个n by x-1矩阵，我们想出了一个n by n/2矩阵。新矩阵将所有男性和女性作为他们的行，并将异性的分数作为列。

我们必须对分数进行降序排序，还需要知道排序后与分数相关的人的id。

所以，在这里我想使用哈希表。

一旦我们得到分数，我们需要组成对，为此我们需要遵循一些规则。

我的麻烦在于第二个矩阵n by n/2需要提供关于哪个男人/女人对女人/男人有多少偏好的信息。我需要对这些分数进行排序，以便我知道谁是第一个喜欢的女人/男人，第二个喜欢男人/女人，依此类推。

我希望对我使用的数据结构有好的建议。我更喜欢 PHP 或 Perl。

注意：

这不是家庭作业。这是稳定婚姻算法的一个小修改版本。我有一个可行的解决方案。我只致力于优化我的代码。

它与稳定的婚姻问题非常相似，但在这里我们需要根据他们共同的兴趣来计算分数。所以，我已经按照您在 wiki 页面http://en.wikipedia.org/wiki/Stable_marriage_problem中看到的方式实现了它。

我的问题不是解决问题。我解决了它并且可以运行它。我只是想有一个更好的解决方案。所以我在询问要使用的数据结构类型的建议。

从概念上讲，我尝试使用哈希数组。其中数组索引给出人员 ID，其中的哈希给出ids <=> scores排序方式。我最初从一个哈希数组开始。现在，我对值的哈希值进行排序，但我无法将排序后的哈希值存储回数组中。因此，只需在排序后存储键并使用它们从我最初的未排序哈希中获取值。

我们可以在排序后存储哈希吗？你能推荐一个更好的结构吗？

4

1 回答 1

1

我认为以下实现了Gale-Shapley 算法，其中每个人的偏好排序作为对异性成员的分数数组给出。

顺便说一句，我刚刚发现大卫盖尔去世了（见他的维基百科条目——他会被想念的）。

代码很冗长，我只是按照维基百科的描述快速转录算法，并没有检查原始来源，但它应该让您了解如何使用适当的 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 回答