Bài giảng Toán rời rạc - Bài 8 - Trần Vĩnh Đức

1 Hôn nhân bền vững •stable.2 Hay lấy người mình yêu và không bỏ được •stable.3 Tham khảo • Mathematics for Computer Science. • Albert R. Meyer ‘s slides Hôn nhân bền vững •stable.4 Tổ chức đám cưới 1 2 3 4 5 A B C D E Chàng trai Cô gái Hôn nhân bền vững •stable.5 Nam Nữ 1 : CBEAD A : 35214 2 : ABECD B : 52143 3 : DCBAE C : 43512 4 : ACDBE D : 12345 5 : ABDEC E : 23415 Mức độ yêu thích Hôn nhân bền vững •stable.6 1: CBEAD 2 : ABECD 3 : DCBAE 4 : ACDBE 5 : ABDEC Thử chiến lược “tham lam” cho nam Mức độ yêu thích 1: CBEAD 2 : ABECD 3 : DCBAE 4 : ACDBE 5 : ABDEC Hôn nhân bền vững •stable.7 Chàng trai 1 cưới Cô gái C (lựa chọn thứ 1 của anh ta) C 1 Mức độ yêu thích 2 : ABE D 3 : D BAE 4 : A DBE 5 : ABDE Hôn nhân bền vững •stable.8 Mức độ yêu thích 2 : ABED 3 : DBAE 4 : ADBE 5 : ABDE Hôn nhân bền vững •stable.9 Mức độ yêu thích 2 : ABED 3 : DBAE 4 : ADBE 5 : ABDE Hôn nhân bền vững •stable.10 Chàng trai 2 cưới Cô gái A (vẫn là lựa chọn thứ 1 của anh ta) A 2 Mức độ yêu thích Tiếp theo: Hôn nhân bền vững •stable.11 Cuối cùng với đám cưới “tham lam cho nam” 1 C 2 A 3 D 4 B 5 E Hôn nhân bền vững •stable.12 Vấn đề! C 1 B 4 Hôn nhân bền vững •stable.13 C 1 B 4 Chàng trai 4 thích cô C hơn vợ anh ta. Hôn nhân bền vững •stable.14 C 1 B 4 và ngược lại Hôn nhân bền vững •stable.15 C 1 B 4 Một cặp lừa đảo Hôn nhân bền vững Bài toán Hôn nhân bền vững: Tổ chức đám cưới cho mọi người mà không có cặp lừa đảo! •stable.16 Hôn nhân bền vững •stable.17 Dễ không? Cùng thử xem! Hôn nhân bền vững •stable.18 Nam Nữ 1 : CBEAD A : 35214 2 : ABECD B : 52143 3 : DCBAE C : 43512 4 : ACDBE D : 12345 5 : ABDEC E : 23415 Mức độ yêu thích Hôn nhân bền vững I. •stable.19 3 A 5 B 4 C 1 D 2 E Mọi cô gái đều lấy được người yêu thích nhất Hôn nhân bền vững II •stable.20 5 A 2 B 4 C 3 D 1 E “tối ưu cho nam” Hôn nhân bền vững Không chỉ là một bài toán vui: • Tuyển sinh đại học (bài báo của Gale & Shapley, 1962) • Ghép cặp Bệnh viện & Sinh viên nội trú. • Ghép cặp các Clients & Servers •stable.21 Hôn nhân bền vững Không chỉ là một bài toán vui: • Tuyển sinh đại học (bài báo của Gale & Shapley, 1962) • Ghép cặp cho các Bệnh viện & các Sinh viên nội trú. • Ghép cặp nhảy •stable.22 Hôn nhân bền vững •stable.23 Bài toán Hôn nhân bền vững Trần Vĩnh Đức HUST Ngày 24 tháng 7 năm 2018 1 / 26 Tài liệu tham khảo ▶ Eric Lehman, F Thomson Leighton & Albert R Meyer, Mathematics for Computer Science, 2013 (Miễn phí) ▶ Albert R Meyer’s slides 2 / 26 Bài toán Hôn nhân bền vững ▶ N chàng trai & N cô gái, ▶ Mỗi chàng trai có một danh sách xếp hạng các cô gái, ▶ Mỗi cô gái có một danh sách xếp hạng các chàng trai. ▶ Hãy tìm cách ghép cặp mỗi chàng trai với một cô gái sao cho không có cặp lừa đảo. 3 / 26 Định nghĩa ▶ Cho một cặp ghép M, cô gái x và chàng trai y gọi là một cặp lừa đảo nếu họ thích nhau hơn bạn của họ trong cặp ghép M. ▶ Cặp ghép không chứa cặp lừa đảo gọi là cặp ghép ổn định. 4 / 26 Nội dung Thủ tục kén chồng Cặp ghép tối ưu Thủ tục kén chồng Ngày qua ngày... 6 / 26 Buổi sáng Các chàng trai đến hát dưới ban công cô gái chàng thích nhất. 7 / 26 Buổi chiều Cô gái từ chối hết chỉ trừ chàng trai cô thích nhất ở dưới ban công. Hình: Nếu anh không phải Brad thì về đi! 8 / 26 Buổi tối Chàng trai bị từ chối xóa tên cô gái khỏi danh sách yêu thích của anh ta 9 / 26 Kén chồng (theo ngày) Buổi sáng: Chàng trai đến hát dưới ban công nhà cô gái mình thích nhất. Buổi chiều: Cô gái từ chối hết chỉ trừ chàng trai cô thích nhất ở dưới ban công. Buổi tối: Chàng trai bị từ chối xóa tên cô gái khỏi danh sách yêu thích của anh ta 10 / 26 Điều kiện dừng ▶ Dừng khi mọi cô gái không còn ai để từ chối. ▶ Và các cô gái cưới chàng trai hiện tại đến cầu hôn. 11 / 26 Hôn nhân bền vững ▶ Thuật toán luôn Dừng: ▶ Luôn có một ngày để làm đám cưới. ▶ Thuật toán Đúng đắn: ▶ Mọi người đều có chồng (hoặc vợ). ▶ Hôn nhân ổn định. 12 / 26 Định lý Thuật toán dừng trong ≤ N2 + 1 ngày. ▶ Nếu vào một ngày thuật toán chưa kết thúc, vậy đêm đó có một chàng trai xóa tên một cô gái khỏi danh sách. ▶ Có N danh sách, mỗi danh sách có N tên. Vậy chỉ có ≤ N2 lần xóa. 13 / 26 Tính đúng đắn của thuật toán Khẳng định Với mỗi cô gái, chàng trai mà cô thích nhất đến cầu hôn vào ngày mai không tệ hơn chàng của ngày hôm nay. vì chàng thích nhất của ngày hôm nay vẫn ở lại cho đến khi bị cô từ chối vì có chàng tốt hơn. 14 / 26 Tính đúng đắn của thuật toán Khẳng định Với mỗi chàng trai, cô gái mà chàng cầu hôn ngày mai sẽ không tốt hơn cô của ngày hôm nay. vì nếu bị cô gái thích nhất từ chối, chàng phải chấp nhận thôi bằng cách xóa tên cô ta khỏi danh sách yêu thích. 15 / 26 Tính đúng đắn của thuật toán Bất biến trong mọi ngày Nếu cô gái G không có trong danh sách của chàng trai B, vậy hiện tại G đang được một chàng trai B′ mà cô ấy thích hơn cầu hôn. 16 / 26 Định lý Khi thuật toán dừng, mọi người đều có chồng hoặc vợ. ▶ Vì mỗi cô gái chỉ giữ lại một chàng trai mà cô ấy thích nhất trong danh sách. ▶ và tại mỗi thời điểm, mỗi chàng trai chỉ đến hát dưới ban công một cô gái. 17 / 26 Định lý Cặp ghép thu được được bởi thủ tục kén chồng là ổn định. 18 / 26 Chứng minh. Chàng Bob không thể nằm trong cặp lừa đảo 1. với cô gái G có trong danh sách yêu thích cuối cùng của mình: vì Bob đã cưới cô gái anh ấy thích nhất trong danh sách này. 2. với cô gái G không có trong danh sách cuối cùng của mình: vì theo bất biến thì G thích chồng của mình hơn Bob. 19 / 26 Nội dung Thủ tục kén chồng Cặp ghép tối ưu Ai thích thủ tục kén chồng hơn, các chàng trai hay các cô gái? 21 / 26 Định nghĩa Ký hiệu S = ”tập mọi cặp ghép ổn định”. Với chàng trai (hoặc cô gái) p, ta định nghĩa lựa chọn có thể của p là tập {q | ∃m ∈ S, {p, q} ∈ m} Đây là những cô gái (hoặc chàng trai) có thể ghép cặp với p trong một cặp ghép ổn định nào đó. 22 / 26 Ví dụ Xét danh sách Chàng trai thích Cô gái thích 1: a,b a: 1,2 2: a,b b: 1,2 Hãy tìm các lựa chọn có thể của chàng trai 1. 23 / 26 Định nghĩa ▶ Bạn đời tốt nhất của một người là người tốt nhất trong các lựa chọn có thể của anh/chị ta. ▶ Bạn đời tệ nhất của một người là người tệ nhất trong các lựa chọn có thể của anh/chị ta. 24 / 26 Định lý Trong thủ tục kén chồng, mọi chàng trai đều được bạn đời tốt nhất. 25 / 26 Định lý Trong thủ tục kén chồng, mọi cô gái đều được bạn đời tệ nhất. Chứng minh. ▶ Giả sử tồn tại cách ghép cặp ổn định M sao cho cô gái g lấy anh b′ tệ hơn anh b trong thủ tục kén chồng. ▶ Trong M ta có cặp ghép {b′, g} và {b, g′} Vậy b và g là cặp lừa đảo với M. Tại sao? 26 / 26