Bài toán Hôn Nhân Bền Vững

Những ai đam mê lập trình và thuật toán hẳn có nhiều lúc ngây ngất trước vẻ đẹp của các thuật toán cũng như sự tinh tế trong cách cài đặt chúng! Có nhiều bài toán nghĩ ra thuật toán rất khó nhưng nghĩ ra rồi thì cài đặt lại rất dễ. Lại có những bài ngược lại, thuật toán thì thấy ngay nhưng để biểu diễn cho máy nó hiểu thì khó vô cùng. Lại cũng có những bài “quái chiêu” cả thuật toán lẫn cài đặt đều khó nhăn răng và một trong số đó là bài toán kinh điển Hôn Nhân Bền Vững tôi muốn giới thiệu cùng các bạn.

Phát biểu bài toán nghe khá hấp dẫn: có N chàng trai và N cô gái, mỗi chàng trai phát biểu cảm nghĩ về N cô gái kia (rằng là cô này anh ta thích nhất, cô này thích nhì, ba, … cho đến cô thích thứ N) tương tự các cô gái cũng phát biểu như vậy về các chàng trai. Hãy ghép đôi họ với nhau sao cho các cuộc hôn nhân này là bền vững nghĩa là không được tồn tại 2 cặp mà người chồng bên cặp này lại thích người vợ bên cặp kia hơn vợ mình, đồng thời người vợ bên cặp kia lại cũng thích người chồng bên cặp này hơn chồng mình, khi đó 2 người này sẽ tìm đến với nhau và thế là ngoại tình.

Bây giờ chúng ta sẽ nghiên cứu một thuật toán xây dựng các cặp bền vững dựa trên ý tưởng giống như đời thực của bài toán. Mỗi chàng trai X sẽ chọn cho mình một cô dâu, hiển nhiên là anh ta sẽ chọn cô gái đầu tiên trong danh sách của mình. Nếu cô này đã hứa hôn (đã được chọn trước đó) với chàng trai khác mà cô ta thích hơn thì anh chàng X phải chọn người phụ nữ kế tiếp trong danh sách của anh ta, quá trình này tiếp tục cho đến khi X tìm được một cô Y chưa được hứa hôn hoặc thích anh ta hơn anh chàng đã hứa hôn trước đó. Nếu Y chưa được hứa hôn thì cô ta sẽ được gả cho X và chúng ta tiếp tục cho người đàn ông kế tiếp. Còn nếu Y đã hứa hôn thì sẽ hủy bỏ cuộc đính hôn và gả cô ta cho X (vì cô ta thích X hơn), và chúng ta lại tiếp tục với anh chàng vừa bị từ hôn.

Phương pháp này có lẽ được mô phỏng từ một câu chuyện trong các tiểu thuyết của thế kỉ 19. Rất đơn giản phải không? Nhưng còn cài đặt thì sao? Trong các tài liệu thường thấy ở VN thì họ dùng foward (ngôn ngữ Pascal) bởi phải xây dựng 2 hàm mà trong thân hàm này gọi tới hàm kia, rất rối rắm phức tạp, khó sửa lỗi và code cũng dài dòng. Còn trong cuốn Cẩm Nang Thuật Toán (sách dịch nước ngoài) tập 2, tác giả đã có một cách cài đặt vô cùng đỉnh cao, gọn nhẹ và xúc tích, (điều thường thấy trong bộ sách này) chẳng phải pho guốt pho ghiếc gì hết.

Bởi vì tất cả các danh sách sở thích đều co chung độ dài, cài đặt đơn giản nhất là dùng mảng 2 chiều. Ví dụ prefer[m, w] là cô gái thứ w trong danh sách sở thích của chàng trai thứ m. Hơn nữa chúng ta cần theo dõi xem mỗi chàng trai đã xử lí đến đâu trong danh sách anh ta. Điều nay có thể được thực hiện bằng một mảng một chiều next, mảng này khởi tạo đến 0 và next[m] + 1 là chỉ số của cô gái kế tiếp trong danh sách của chàng trai thứ m, chỉ danh của cô tra sẽ là prefer[m, next[m] + 1]. Với mỗi cô gái ta cần theo dõi vị hôn phu hiện thời là ai (fiancee[w] sẽ là chàng trai đã hứa hôn với cô gái w) và chúng ta cần trả lời câu hỏi “người đàn ông thứ s có được thích hơn so với người đàn ông fiancee[w] hay không?”. Câu trả lời này có thể được giải đáp bằng cách tìm kiếm tuần tự cho tới khi s hoặc fiancee[w] được tìm thấy, nhưng cách này không hiệu quả nếu 2 người nằm ở cuối danh sách. Thay vì vậy, chúng ta dùng một danh sách ngược: rank[w, s] là chỉ số của chàng trai thứ s trong danh sách sở thích của cô w. Sự phù hợp của vị hôn phu s có thể xác định rất nhanh chóng bằng cách kiểm tra xem rank[w, s] có nhỏ hơn rank[w, fiancee[w]] hay không. Các mảng này được xây dựng dễ dàng và trực tiếp từ danh sách các sở thích. Để khởi đầu, chúng ta dùng một lính canh là chàng trai 0 để khởi tạo cho vị hôn phu và đặt anh ta ở cuối tất cả các danh sách sở thích của các cô gái.

Với cấu trúc dữ liệu được khởi tạo bằng phương pháp này, việc cài đặt có thể thực hiện dễ dàng như sau:

for m := 1 to N do
begin
    s := m;
    repeat
        next[s] := next[s] + 1;
        w := prefer[s, next[s]];
        if rank[w, s] < rank[w, fiancee[w]] then
        begin
            t := fiancee[w]; fiancee[w] := s; s := t;
        end;
    until s = 0;
end;

Theo yêu cầu, sau đây là toàn bộ code hoàn chỉnh bằng ngôn ngữ Pascal của bài toán Hôn Nhân Bền Vững.

Input cho trong file WED.INP có cấu trúc như sau:

Dòng đầu là số nguyên dương N.
Tiếp theo là 1 dòng trắng.
N dòng tiếp theo mỗi dòng có N số: số thứ j của dòng thứ i trong N dòng này là tên cô gái mà chàng trai i thích thứ j.
Tiếp theo là 1 dòng trắng.
N dòng tiếp theo mỗi dòng có N số: số thứ j của dòng thứ i trong N dòng này là tên chàng trai mà cô gái i thích thứ j.

Ouput ra file WED.OUT gồm N dòng, mỗi dòng 2 số i, j nghĩa là cô gái i sẽ lấy anh chàng j.

Các số trên cùng 1 dòng ở cả Input và Output cách nhau ít nhất 1 dấu cách.

Ví dụ:

WED.INP
5

2 5 1 3 4
1 2 3 4 5
2 3 5 4 1
1 3 2 4 5
5 3 2 1 4

5 1 4 2 3
4 5 2 1 3
1 4 2 3 5
3 2 4 1 5
4 2 3 5 1

WED.OUT
1 1
2 5
3 4
4 2
5 3

const
    fi = 'WED.INP';
    fo = 'WED.OUT';
    max = 100;

var
    N: byte;
    prefer: array [1..max, 1..max] of byte;
    rank: array [1..max, 0..max] of byte;
    next, fiancee: array [1..max] of byte;

procedure readinput;
var
    f: text;
    i, j, x: byte;
begin
    assign(f, fi);
    reset(f);
    readln(f, N);

    readln(f); { có 1 dòng trắng ở đây }

    { đọc sở thích của các chàng trai: prefer[i, j]
    là tên cô gái mà anh chàng i thích thứ j }
    for i := 1 to N do
    begin
        for j := 1 to N do read(f, prefer[i, j]);
        readln(f);
    end;

    readln(f); { có 1 dòng trắng ở đây }

    { đọc sở thích của các cô gái: rank[i, x]
    là thứ tự của anh chàng x trong sở thích của cô gái i }
    for i := 1 to N do
    begin
        for j := 1 to N do
        begin
            read(f, x);
            rank[i, x] := j;
        end;
        readln(f);
    end;

    close(f);
end;

procedure init;
var
    i: byte;
begin
    for i := 1 to N do
    begin
        { mảng next khởi tạo đến 0 }
        next[i] := 0;
        { chàng trai 0 (lính canh) nằm cuối
        danh sách sở thích của các cô gái }
        rank[i, 0] := N + 1;
        { khoi tạo vị hôn phu cho các cô gái
        là anh chàng 0 }
        fiancee[i] := 0;
    end;
end;

procedure match;
var
    m, s, w, t: byte;
begin
    for m := 1 to N do
    begin
        s := m;
        repeat
            next[s] := next[s] + 1;
            w := prefer[s, next[s]];
            if rank[w, s] < rank[w, fiancee[w]] then
            begin
                t := fiancee[w]; fiancee[w] := s; s := t;
            end;
        until s = 0;
    end;
end;

procedure writeoutput;
var
    f: text;
    i: byte;
begin
    assign(f, fo);
    rewrite(f);
    for i := 1 to N do
        writeln(f, i, ' ', fiancee[i]);
    close(f);
end;

begin
    readinput;
    init;
    match;
    writeoutput;
end.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s