Kata learns to code

Nghe ISIS có cảm giác thật mông lung…

Through fiction we saw The Birth
Of Futures Yet to come
Yet in Fiction lay the Bones
Ugly in their nakedness
Yet under this Mortal Sun
We cannot hide Ourselves

Quy Hoạch Động (QHD) là 1 phương pháp rất mạnh mẽ trong Tin học. Nếu phân tích kĩ các bạn sẽ thấy những thuật toán nổi tiếng như Ford-Bellman, Dijkstra, hay Floyd đều có bản chất là QHD. Nhưng không phải bài toán nào cũng giải bằng QHD được, nếu quá áp đặt, cố sức giải nó như vậy bạn sẽ dễ dàng mắc phải 1 sai lầm gọi là Phụ thuộc tiền sử.

Để tìm hiểu sai lầm này chúng ta nhắc lại về nguyên lí QHD do Bellman phát minh ra: “Một dãy là tối ưu thì các dãy con của nó cũng là tối ưu”. Nghe có vẻ khó hiểu nhưng đại loại là ta có 1 cái bảng rồi lần lượt điền các số vào bảng đó, các số điền vào đầu tiên thường đơn giản, các số sau
đó dựa vào các số trước mà điền, cho đến khi điền kín bảng. Kết quả bài toán là số mà ta điền cuối cùng. Như vậy nguyên lí “chia để trị” đã được đẩy tới cao độ ở đây.

Khâu quan trọng nhất là làm thế nào điền được số sau dựa trên các số trước, hay nói cách khác là ta đang tìm 1 hệ thức truy hồi.

Gọi f(i) là hàm QHD tại i, ta xây dựng công thức truy hồi tính f(i) dựa vào các f(j) với j = i - 1, i - 2, … Công thức truy hồi này chỉ được phụ thuộc vào các f(j) cùng các đại lượng cố định của các j (cho trong đề bài) tuyệt đối không được phụ thuộc vào tiền sử, cách thức tạo nên f(j). Đây là chính là sai lầm mà tôi muốn nói đến!

Để dễ hiểu chúng ta xét 1 ví dụ rất thú vị sau:

Bài toán: ngày xửa ngày xưa, có 1 chàng Hoàng tử bị 1 mụ Phù thủy hóa phép biến thành 1 con ếch, còn Công chúa thì bị mụ ta nhốt trong 1 tòa lâu đài nằm trên 1 hòn đảo giữa hồ. Bây giờ ếch đang đứng ở bờ hồ, trên đoạn thẳng từ chỗ đó đến tòa lâu đài có các lá sen nổi trên mặt nước ở những vị trí, khoảng cách khác nhau, ếch phải nhảy qua các lá sen để vào tòa lâu đài cứu Công chúa. Bước nhảy kề sau không được dài hơn bước nhảy kề trước A mét cho trước.
Ếch có 1 túi rất nhiều muỗi thần, ăn K con muỗi, ếch có thể nhảy tối đa trong 1 bước là K mét. Mỗi bước nhảy (dù dài hay ngắn) đều tốn 1 giây. Cho trước thời gian giới hạn là T giây, hãy tính số muỗi ít nhất mà ếch cần ăn để có thể nhảy đến tòa lâu đài!

Dữ liệu vào cho trong file ECHOP.INP có cấu trúc:
Dòng đầu là 3 số nguyên N A T
Dòng 2 là N số nguyên dương tăng dần thể hiện tọa độ các lá sen.
Các số trên cùng 1 dòng cách nhau bởi ít nhất 1 dấu cách.
Dữ liệu ra file ECHOP.OUT gồm 1 số duy nhất là số muỗi tối thiểu, nếu không có phương án giải
cứu Công chúa in ra số -1

Rồi, đọc xong là biết phải dùng QHD, đây là cách sai:
Gọi d[t, i] là số muỗi ít nhất cần ăn khi phải nhảy đến lá sen thứ i và thời gian giới hạn là t. Để tính d[t, i] ta chỉ cần xét các d[j, t - 1] với j = i - 1, i - 2, … kiểm tra xem khoảng cách từ lá sen j đến lá sen i là bao nhiêu (là P), xem tiền sử của d[j, t - 1] xem lá sen kề trước j là lá nào (lá thứ z), tính khoảng cách giữa lá sen z và j là Q, kiểm tra Q + A >= P được thỏa mãn rồi đặt x = max(d[t, j], P), trong các x như thế chọn ra cái nhỏ nhất và đó chính là d[t, i]

Cách đúng: gọi d[t, i, j] là số muỗi ít nhất khi trong thời gian t, cần nhảy đến lá sen j nhưng lá kề trước j phải là i. Lúc này hệ thức truy hồi tương tự như trên nhưng không còn phụ thuộc tiền sử nữa.

Bạn cũng dễ mắc sai lầm này khi đi tìm cách giải hoàn hảo cho các bài toán “bất trị”, cho đến nay loài người vẫn chưa giải được như bài toán Người du lịch, bài toán Tìm đường đi dài nhất không lặp lại đỉnh trên đồ thị trọng số dương, bài toán Tập thống trị nhỏ nhất…

Cuối cùng cũng xong sự kiện mà suốt thời gian qua được rùm beng: Unite 08 với MCR. Thực ra tôi đi là cho có đi, gọi là không bị chê lạc hậu. Đến khá sớm và có được chỗ đứng ngon: phía trước, ngay sát rào chắn, nhưng không hiểu sao lúc UnlimiteD sắp đánh, tôi lại nổi cơn hâm: chen xuống dưới cùng, sát khán đài để xem. Trên đường “tháo lui”, nghe có vài tiếng nói con gái dễ thương đại loại: “Ăn ơi, sao lại xuống dzzzzzzzzở?”, “Rồiiiiiiiii, cám ơn ăn!”

Về đến nhà mệt bã người, xong xuôi đâu đấy, theo thói quen trước khi đi ngủ, tôi bật máy lên nghe nhạc. Đã hết thời hạn làm crazy fan “tạm thời” của MCR, “I don’t love you”, uh, đúng đấy, “I don’t hate you”, cũng đúng luôn, tôi không thích mà cũng chẳng ghét MCR. Tôi định đêm nay tìm hiểu 1 band mới. Trong list các album download về để đó, ít hoặc chưa nghe, tôi ngẫu nhiên chọn Dolmen (Demo) của Öröm (country: Hungary, genres: Doom/Dark/Folk). OK, để xem thế nào.

Mở đầu album là tiếng mưa rơi tầm tã, 1 kiểu khá quen thuộc. Nhưng kiểu Doom của Öröm thì chả quen thuộc, không có gào thét thảm thiết, không có những đoạn riff xé lòng hay thê lương, không có cao trào hay điệp khúc gì cả. Tất cả cứ chầm chậm, đều đều, từ từ, vocal thì thầm, thở dài ngao ngán, khô khan. Bài nào cũng như bài nào, nhưng bài nào cũng hay.

Nhạc của Öröm gợi lên trước mắt người nghe những cảnh tượng của rừng già xám xịt, ảm đạm, bi ai, khói sương mù mịt, của nỗi nhớ, kỷ niệm buồn xa xăm.

Öröm cũng mới chỉ có 1 full length duy nhất ra năm 2006, tên là “8″, chỉ phát hành đúng 8 bản, nhưng album lại có 9 bài.

Chưa thể nói có thể làm fan của Öröm hay không, đợi nghe xong “8″ đã. Tuy nhiên, sống giữa cái thành phố ồn ào, bụi bặm và tắc đường này, đêm nay nghe Öröm, vâng, cho nói phét tí, như được sống giữa rừng thiêng nước độc, thiên nhiên hoang vắng, nỗi buồn và sự cô đơn mới đẹp làm sao!

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à 1 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 1 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 1 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ừ 1 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 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ó 1 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 goắc 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 1 mảng 1 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 1 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 1 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:

Language: Pascal
Author: Katatunix

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;

Browser: Firefox, IE
Play here