Bài 9
Bài toán ghép cặp Bài toán ghép cặp
Giới thiệu
Bài toán ghép cặp có thể chia thành 2 loại
Xét việc ghép mỗi phần tử của tập hợp này với 1 phần tử của tập hợp khác như phân công n việc khác nhau cho n người, mỗi người 1 việc, đó chính là bài toán hôn nhân.
Xét việc chia 2k phần tử của 1 tập hợp thành k cặp, ví dụ như sắp xếp 2k sinh viên vào k phòng trong ký túc xá (mỗi phòng có 2 sinh viên)
Định lý Hall
Bài toán hôn nhân do Phillip Hall giải quyết năm 1935 có rất nhiều ứng dụng và được phát biểu dưới nhiều dạng khác nhau.
2
Đồ thị lưỡng phân
Định nghĩa: Đơn đồ thị G=(V,E) sao cho V=V1 (cid:0)
(cid:0)
(cid:0) V2=(cid:0)
, V2 (cid:0)
, V1
(cid:0) V2, và mỗi cạnh của G được V1 nối một đỉnh trong V1 và một đỉnh trong V2 được gọi là đồ thị 2 đầu (lưỡng phân).
Cho đồ thị lưỡng phân G=(A,B,E). Một ghép cặp là một tập hợp các cạnh sao cho không có cạnh nào có chung 1 đầu mút.
Một ghép cặp từ A đến B được gọi là hoàn hảo khi
nó có thể nối tất cả các đỉnh của A đến B
3
(cid:0)
Đặt vấn đề
Có 5 việc cần tuyển người đảm nhiệm, mỗi người 1
việc.
Gọi Si là tập hợp các ứng viên thích hợp cho việc
thứ i và giả sử rằng ta có S1 = {A, B, C}, S2 = {D, E}, S3 = {D}, S4 = {E}, S5 = {A, E}
Có thể tuyển đủ 5 người thích hợp cho 5 việc nói
trên hay không? ?
4
Đặt vấn đề
Có 4 chàng trai B1, B2, B3, B4 và 5 cô gái G1, G2, G3, G4, G5; mỗi chàng có 1 danh sách các cô gái thích hợp như sau:
B1: {G1, G4, G5} B2: {G1} B3: {G2, G3, G4} B4: {G2, G4}
Một chàng trai có thể kết hợp với 1 cô gái thích hợp
hay không?
Dễ dàng ta thấy lời giải cho bài toán này là các cặp
sau: (B1, G4), (B2, G1), (B3, G3), (B4, G2)
5
Định nghĩa
Cho S là một tập hợp hữu hạn và đa tập hợp A={A1,
A2, … Am} là một họ các tập con của S.
Ta bảo A thỏa điều kiện Hall nếu với mọi k (cid:0)
{1, …,
A, ta có
m} và k phần tử bất kỳ Ai1, … Aik (cid:0) … Aik| >=k |Ai1
Ai2
Một hệ đại diện riêng biệt hay 1 SDR (Systems of Distinct Representatives) của A là một bộ (a1, a2, …, am) gồm m phần tử khác nhau của S sao cho ai (cid:0) Ai; mỗi một ai gọi là 1 đại diện của Ai.
6
(cid:0) (cid:0)
Ví dụ
Cho A ={A1, A2, A3, A4} với
A2 (cid:0)
A3 | = 2 nên A không thỏa điều kiện
A1={1, 2}, A2={2, 3, 4}, A3={1}, A4={2} thì vì |A1 (cid:0) Hall.
7
Định lí Hall và ứng dụng
Định lí Hall Cho đồ thị lưỡng phân X, Y. Với mỗi tập con A thuộc X, gọi G(A) là tập các đỉnh thuộc Y kề với một đỉnh nào đó thuộc A. Khi đó điều kiện cần và đủ để tồn tại một đơn ánh f: X → Y sao cho x kề f(x) là |G(A)| ≥ |A| với mọi A khác rỗng thuộc X.
Cho S là một tập hợp hữu hạn và đa tập hợp {A1, A2, … Am} là một họ các tập con của S, A có 1 SDR nếu và chỉ nếu A thỏa điều kiện Hall.
8
Định lí Hall (tt)
Chứng minh Điều kiện cần là hiển nhiên: Nếu tồn tại đơn ánh f thì với mỗi thuộc X, ta có chứa các phần tử phân biệt , do đó . Ta chứng minh điều kiện đủ bằng quy nạp theo |X|. Khi , khẳng định là hiển nhiên. Giả sử định lý đã đúng với các tập X với . Giả sử bây giờ . Ta xét hai trường hợp:
9
Định lí Hall (tt)
Chứng minh (tt) 1) Giả sử với mọi , ta có . Chọn một phần tử bất kỳ thuộc X, theo điều kiện , do đó tồn tại thuộc Y kề với X. Ta đặt . Bây giờ xét và , và G’(A) là tập các đỉnh thuộc Y’ kề với A. Khi đó . Vì nên theo giả thiết quy nạp, tồn tại đơn ánh sao cho kề x với mọi x thuộc x’. Bổ sung thêm ta được đơn ánh thỏa mãn yêu cầu định lý.
10
Định lí Hall (tt)
Chứng minh (tt) 2) Trong trường hợp ngược lại, tồn tại sao cho . Khi đó, do nên tồn tại đơn ánh . Xét , . Xét B thuộc X’ và là tập các đỉnh thuộc Y’ kề với B. Nếu thì ta có mâu thuẫn với điều kiện định lý. Như vậy ta có với mọi B thuộc X’. Theo giả thiết quy nạp, tồn tại đơn ánh sao cho g(x) kề với x. Như vậy, ta có thể xây dựng được đơn ánh sao cho h(x) kề với x: cụ thể h(x) = f(x) nếu x thuộc A và h(x) = g(x) nếu x thuộc .
11
Thuật toán tìm SDR
Cho một phần tử a1 tùy ý của A1 làm đại diện cho A1. ta chọn 1 phần tử
Với i>=2 và Ai – {a1, a2, …, ai-1} (cid:0) bất kỳ của Ai – {a1, a2, …, ai-1}
Nếu chọn được a1, a2, …, am thì tập hợp này sẽ tạo
thành 1 SDR của A.
hay Ak (cid:0)
Ngược lại, trong trường hợp có k sao cho Ak – {a1, a2, …, ak-1} = (cid:0) {a1, a2, …, ak-1} (có nghĩa là mỗi phần tử Ak đã là đại diện. Gọi S(b) là phần tử của A có đại diện là b.
12
(cid:0)
Thuật toán tìm SDR (tt)
Đặt B1 = Ak và sắp các phần tử của B1 thành 1 dãy thì đặt U2 = U1;
U1 = b1b2…bh. Nếu S(b1) – B1 = (cid:0) nếu S(b1) – B1 = {bh+1 …bp}, ta lập dãy U2 = U1 bh+1 …bp= b1b2 …bp
Giả sử có Ui và Bi là tập hợp các phần tử xuất hiện thì đặt Ui+1 = Ui; nếu
trong Ui. Nếu S(bi) – Bi= (cid:0) ngược lại S(bi) – Bi = {bi1, …bit}, thì ta lập dãy Ui+1 = Ui bi1, …bit
13
Thuật toán tìm SDR (tt)
Nếu cuối cùng có dãy Uq với các phần tử b1, …br
… (cid:0)
S(b1) (cid:0)
đều đã là đại diện của S(bi), i=1, …, r thì |Ak (cid:0) S(br)| = r < r+1, điều này trái với giả thiết A thỏa điều kiện Hall. Vậy có r mà trong Ur có một phần tử bs- chưa là đại diện. Theo định nghĩa của U1 thì bs không có trong U1 và có s1 < s sao cho bs (cid:0) S(bs2), bs2
S(bs2), …, bt-1 (cid:0)
S(bst), bst (cid:0)
Ak
14
(cid:0)
Thuật toán tìm SDR (tt)
Ta chọn bs làm đại diện cho S(bs1-), bs1 làm đại diện cho S(bs2-), …, và bt-1 làm đại diện cho S(bst-), cuối cùng bst làm đại diện cho Ak Lặp lại quá trình trên ta có một SDR của A
15
Bài toán phân công công việc
Giả sử ta có 4 việc v1, v2, v3, v4 và 4 ứng viên U1, U2, U3, U4 mà ta muốn phân công mỗi người một việc. Khả năng của mỗi ứng viên tương ứng với mỗi công việc cho trong bảng sau đây, trong đó điểm càng cao khả năng càng thấp.
J1
J2
J3
J4
82
83
69
W1
92
77
37
49
W2
92
11
69
5
W3
86
8
9
98
W4
23
16
Bài toán phân công công việc (tt)
Thuật toán tìm phương án phân công tốt nhất
Bước 1: Trừ mỗi dòng cho số nhỏ nhất của dòng đó
Bước 2: Trừ mỗi cột cho số nhỏ nhất của cột đó.
Bước 3: Xác định k, số đường nhỏ nhất chứa tất cả
các zero của A và chỉ rõ đường k
Nếu k 17 18 J3 J4 J2 Bước 2 J1 J2 J3 J4 Bước 1 J1 J2 J3 J4 W1 82 83 69 92 13 14 0 W1 8 W1 13 14 0 23 (-69) W2 77 37 49 92 40 0 12 W2 40 W2 40 0 12 55 (-37) W3 11 69 5 86 6 64 0 W3 66 W3 6 64 0 81 (-5) W4 8 9 98 23 W4 0 1 90 15 (-8) 0 1 90 W4 0 (-0) (-0) (-0) (-15) Bước 3 J1 J2 J3 J4 W1 13 14 0 8 Bước 4 J1 J2 J3 J4 W2 40 0 12 40 x 0 2 W1 7 8 W3 6 64 0 66 18 40 W2 40 0 Số lượng dòng
(bao phủ tất cả 0
trong ma trận) là
3 < n=4 của ma
trận nên chuyển
sang bước 4. Số
nhỏ nhất trong
ma trận hiện tại
là 6. W4 0 1 90 0 x W3 0 58 0 60 (-6) x W4 1 0 96 0 Bước 3’ J1 J2 J3 J4 (+6) W1 7 8 0 2 x W2 40 0 18 40 x Số lượng dòng (bao phủ tất cả 0 trong ma
trận) là 4 = n=4 của ma trận nên chuyển
sang bước 5. 19 W3 0 58 0 60 x W4 0 1 96 0 x Bước 5 J1 J2 J3 J4 J1 J2 J3 J4 W1 7 8 0 2 82 83 69 92 W1 W2 40 0 18 40 77 37 49 92 W2 11 69 5 86 W3 W3 0 58 0 60 Tổng chi phí của phân công công việc tối ưu là
69 + 37 + 11 + 23 = 140. 20 8 9 98 23 W4 W4 0 1 96 0 Loại bài toán giao việc khác đó là xét tầm quan trọng
của công việc. Việc nào quan trọng hơn sẽ được ưu
tiên nhận người. Quy ước: J1 tiên hơn công việc J2 21 Định nghĩa
Cho A = {a1, a2, …. an} là tập hợp các công việc a1<
a2 …. < an. Ta nói rằng A phân công được nếu có thể
phân công những người khác nhau phụ trách tất cả
nhưng công việc khác nhau trong A. Cho A = {a1, a2, …. an} phân công được. A được gọi
là tập hơn phân công được tối ưu hay OAS (order
acceptance and scheduling) nếu với mọi tập hợp
phân công được B = {b1, b2, … bn} ta có m<=n và
ai<=bi, trong đó i=1, …, m 22 Cho J1 < J2 < J3 < J4 < J5 và danh sách các ứng viên cho các công việc này như sau A, B B, C
B A, C B, C, D Công việc Ứng viên
J1
J2
J3
J4
J5 23 Có thể kiểm chứng các tập hợp {J2 , J3 , J4} , {J1 , J4 , J5},
{J1 , J2 , J3 , J5} là phân công được, trong đó {J1 , J2 , J3 ,
J5} là tối ưu. Thuật toán tìm tập hợp phân công được tối ưu riêng biệt cho A= {J1, … Js} với J1 < … < Js. Thuận toán này chính là thuật toán tìm một hệ đại diện 24 Chọn đại diện theo thứ tự ưu tiên. Nếu đến Jr mà không
tìm được đại diện cho Jr sau khi đã đổi việc thì bỏ qua
công việc này (chưa có người phụ trách) để xét đến Jr+1. A, B B, C B A, C
B, C, D Công việc Ứng viên
J1
J2
J3
J4
J5 J1, B (cid:0) J2, thì không thể chọn đại diện cho Ví dụ: Tìm tập hợp phân công
tối ưu OAS cho các
công việc theo bảng Chọn A (cid:0)
J3={B}. đại diện. Đặt U1=B, ta có S(B)=J2={b, C} nên U2=BC và C chưa là S(B), B (cid:0) U1 nên ta thay đổi đại diện như sau: C là 25 đại diện cho J2 và B là đại diện cho J3 Vì C (cid:0) Vậy ta có OAS là là {J1, J2, J3, J5} với các phân công sau
A -> J1, C -> J2, B->J3, D->J5 26 Ví dụ: (tt)
Đặt U1=AC ta có
S(A) = J1 = {A, B} nên U2 = ACB,
S(C) = J2={B, C} U3=ACB,
S(B) = J3={B} U4=ACB Không có đại diện nào cho J4
nên ta xét đến J5 (loại J4 ra khỏi A) và chọn D làm đại
diện cho J5.Bài toán phân công công việc (tt)
Thuật toán tìm phương án phân công tốt nhất (tt)
Bước 4: Gọi a là số nhỏ nhất không xuất hiện trong các
đường xác định ở Bước 3.
-Trừ a cho tất cả các số không trên đường nào
-Cộng a cho tất cả các số trên 2 đường (giao điểm của
dòng, cột
-Giữ nguyên các số chỉ ở trên 1 đường. Trở lại Bước 3.
Bước 5: Đặt Ai={j: Aij= 0}. Dùng thuật toán Hall để tìm ra
SDR của A = {A1, …An}, tức là tìm n zero độc lập (Các số
0 ở trên những dòng và những cột khác nhau của ma trận
A được gọi là các zero độc lập) Suy ra kết quả. Dừng.
Bài toán phân công công việc (tt)
J1
Bài toán phân công công việc (tt)
Bài toán giao việc của Gale
Bài toán giao việc của Gale (tt)
Bài toán giao việc của Gale (tt)
Bài toán giao việc của Gale (tt)
Bài toán giao việc của Gale (tt)
Bài toán giao việc của Gale (tt)
