Tìm hiểu về cặp ghép

Bàn thêm về cặp ghép

Lưu Tuấn Anh

Bài toán cặp ghép là 1 bài toán rất cơ bản và cũng có rất nhiều ứng dụng trong thực tế.

Trên ISM đã có rất nhiều bài viết viết về những vấn đề liên quan đến bài toán này. Bài viết

của tôi chỉ xin nói thêm về 1 khía cạnh ít được đề cập đến. Đó là đếm số lượng cặp ghép.

Bài toán phát biểu như sau:

Cho N sinh viên( N<=12 ) và N vấn đề cần nghiên cứu. Mỗi sinh viên sẽ hứng thú với 1 số

vấn đề, và khi sinh viên được giao vấn đề họ thích thì họ sẽ làm việc hiệu quả hơn rất

nhiều. Ngài giáo sư đáng kính của chúng ta muốn biết có bao nhiêu cách ghép sao cho mỗi

sinh viên sẽ giải quyết 1 vấn đề mà họ thích.

Giáo sư sẽ cung cấp cho chúng ta 1 ma trận A kích thước NxN trong file PROBLEM.TXT

với

+ A[i,j]=1 khi sinh viên i thích vấn đề j.

+ A[i,j]=0 khi sinh viên i không thích vấn đề j.

Yêu cầu: Bạn hãy viết 1 chương trình tính số ghép thoả mãn yêu cầu của giáo sư và gửi

file kết quả SOLVE.TXT cho giáo sư.

Ví dụ:

PROBLEM.TXT

3

1 1 1

1 1 1

1 1 0

SOLVE.TXT

4

Giải thích : 4 cặp ghép là

((1,2),(2,3),(3,1))

((1,1),(2,3),(3,2))

((1,3),(2,1),(3,2))

((1,3),(2,2),(3,1))

Bài toán trên ta có thể giải theo cách tầm thường là tìm toàn bộ cách khả năng có thể ghép

bằng cách vét cạn, độ phức tạp là N!. Trong trường hợp ma trận A gồm toàn số 1, số cách

chọn sẽ là N!.Dù N<=12 nhưng N! vẫn là 1 giá trị “khủng khiếp”.

Sau đây tôi xin đề xuất cách giải với thuật toán QHĐ trạng thái. Xin nói qua về QHĐ trạng

thái.QHĐ trạng thái là QHĐ trên các trạng thái, các trang thái thường được biều diễn bằng

1 dãy bít hoặc tính trước.