Bàn luận thêm về Cặp ghép
Nguyễn Tuấn Dũng
'Ghép cặp' các đốitượng theo một quan hệ nào đó là một bài toán mang tính hết sức tự nhiên và cónhiều ý nghĩa trong ứng dụng thực tiễn. Chẳng hạn, các sinh viên ngành sư phạmdo được nhà nước đào tạo miễn phí nên khi ra trường họ được phân công về dạyhọc ở các trường miền núi. Nhưng những sinh viên đó được đưa ra danh sách nhữngtrường mà mình muốn công tác với độ ưu tiên khác nhau. Một bài toán đặt ra làphải bố trí các sinh viên này sao cho phù hợp nhất (có thể được) với sở thíchcủa mỗi người, tuy nhiên ở đây, sinh viên nào có kết quả học tập tốt hơn sẽđược ưu tiên hơn. Hay ta có thể gặp vấn đề ghép cặp trong các bài toán quenthuộc khác như: bài toán phân công công việc, bài toán hôn nhân bền vững, bàitoán xếp thời khoá biểu...
Trong số 26(11/2001), tác giả Lê Văn Chương đã giới thiệu với chúng ta thuật toánKuhn-Munkres giải bài toán tìm cặp ghép có tổng trọng số lớn nhất. ở đây, không đi vào thuật toán tìm cặpghép có tổng trọng số lớn nhất nữa vì điều đó khá rõ ràng trong số báo trước.Tuy nhiên, chúng ta sẽ xem xét thêm một chút để giúp các bạn phần nào tiếp cậngần bài toán hơn và đỡ nhầm lẫn trong lúc cài đặt chương trình. Để tiện theodõi, ta tóm tắt lại bài toán:
Cho G = (X U Y,E) là đồ thị hai phía đầy đủ, trong đó: X, Y là hai tập hữu hạn gồm n phần tử, E là tập các cạnh của đồ thịvà với mỗi cạnh được gán với một trọng số Cij. Cần tìm tập cặp ghépđầy đủ M có tổng trọng số lớn nhất.
Đối với bài toánnày có thể sử dụng bài toán luồng cực đại để giải bằng cách thêm vào G hai đỉnhgiả S và T, nối với các đỉnh xi thuộc X và nối T với các đỉnh yj thuộc Ybằng các cạnh có trọng số là 0. Tuy nhiên, bài toán cặp ghép cực đại là trườnghợp riêng của bài toán luồng nên nó có những đặc điểm riêng và do đó dẫn đếnviệc giải quyết nó thì cũng có những thuật toán đặc thù, mà tiêu biểu là thuậttoán gán nhãn, trong đó ta có thể đi theo hai hướng chính:
Hướng thứnhất, xuất phát từ một cặp ghép M đầy đủ bất kỳ của G, ta xây dựng một nhãnF tương ứng với M, nếu F chấp nhận được thì M là nghiệm cần tìm, ngược lại nhãnF là không chấp nhận được thì ta tiếp tục điều chỉnh.
Hướng thứ hai,xây dựng một nhãn F chấp nhận được, sau đó tìm M tương ứng với F bằng cách:khởi tạo M là tập rỗng, chừng nào mà M chưa đầy đủ thì ta còn tiếp tục điềuchỉnh (tăng cặp ghép).
Thuật toánKunh-Munkres trình bày trên số báo 26 là cách giải thứ hai, được trình bày khárõ ràng. Tuy nhiên có điểm cần chú ý trong bước 5 (sửa nhãn), lượng sửa nhãnkhông phải:
d:=min {F(xi)+ F (yj) - Cij, xi thuộc S, yj thuộc T} (cóthể do lỗi khi in ấn) mà là:
d:=min {F(xi)+ F(yj) - Cij, xi thuộc S, yj thuộc T } (*)
Bởi vì, trongbước 3 khi không tìm được đường tăng cặp ghép ta mới phải sửa nhãn sao cho:
- Nhãn Fmớivẫn chấp nhận được.
- Fmớivẫn tương ứng với M đang có, để cho số cạnh của G (F, M) không bị giảm đi.
- Tăng thêm sốcạnh trong đồ thị cân bằng tương ứng G (F, M)
