Đề tài Ứng dụng phương pháp phân tích xác suất các thuật toán ngẫu nhiên trong quá trình phân tích các bài toán

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC ˜¯™ TIỂU LUẬN MÔN: MÔ PHỎNG NGẪU NHIÊN ĐỀ TÀI: ỨNG DỤNG PHƯƠNG PHÁP PHÂN TÍCH XÁC SUẤT VÀ CÁC THUẬT TOÁN NGẪU NHIÊN TRONG QUÁ TRÌNH PHÂN TÍCH CÁC BÀI TOÁN Giáo viên giảng dạy: PGS.TS. Trần Lộc Hùng Học viên thực hiện: Nguyễn Lý Hữu Huấn Lớp: Khoa học máy tính, Khóa năm: 2008-2010 Huế, 6/2009 MỤC LỤC LỜI MỞ ĐẦU Tiểu luận này trình bày về phương pháp sử dụng phép phân tích xác suất và các thuật toán ngẫu nhiên trong quá trình phân tích và ước lượng chi phí của một bài toán. Trong tiểu luận này, tôi đưa ra một bài toán cụ thể, đó là bài toán Thuê nhân viên để tiến hành phân tích và đánh giá chi phí thực hiện ở các trường hợp sử dụng phương pháp phân tích xác suất và phương pháp ứng dụng thuật toán ngẫu nhiên. Tôi xin chân thành cảm ơn Thầy giáo – PGS.TS. Trần Lộc Hùng đã tận tình giảng dạy và chỉ bảo cho tôi những kiến thức bổ ích về môn học. Do khả năng và thời gian có hạn nên tiểu luận không tránh khỏi những thiếu sót và hạn chế. Tôi mong tiếp tục nhận được sự chỉ bảo của Thầy để có thể hoàn chỉnh hơn nữa những hiểu biết của mình. Học viên thực hiện Nguyễn Lý Hữu Huấn 1. GIỚI THIỆU BÀI TOÁN 1.1 Mô tả bài toán Thuê nhân viên Giả sử bạn cần thuê một nhân viên văn phòng mới thông qua dịch vụ môi giới việc làm. Nhà môi giới sẽ lần lượt gửi cho bạn một ứng cử viên mỗi ngày. Bạn sẽ phỏng vấn mỗi người và sau đó bạn quyết định có thuê người đó hay không. Để phỏng vấn một người xin việc, bạn phải tốn một chi phí nhỏ để trả cho nhà môi giới, tuy nhiên để thuê được một người thì rất tốn kém vì bạn phải sa thải nhân viên hiện tại và trả một khoản chi phí thuê rất lớn cho nhà môi giới. Vì vậy, sau khi phỏng vấn một người, nếu người đó tốt hơn người hiện tại bạn sẽ sa thải người hiện tại và thuê người mới. Mục tiêu của bài toán này là nhằm ước tính xem chi phí đó là bao nhiêu. Thủ tục HIRE-ASSISANT dưới đây sẽ mô tả quá trình này. Giả sử số lượng các ứng cử viên là từ 1 đến n. Sau khi phỏng vấn ứng cử viên thứ i, thủ tục có thể cho bạn xác định ứng cử viên nào là tốt nhất trong các ứng cử viên trước đó. Để khởi gán giá trị ban đầu, thủ tục tạo ra 1 ứng cử viên mang giá trị 0 (gọi là ứng cử viên bù nhìn, có chất lượng tệ nhất). * Thủ tục HIRE-ASSITANT 1. BEST:=0 {ứng cử viên bù nhìn} 2. For i:=1 to n do 3. 4. if then 5. BEST: = i 6. Ở đây ta không đề cập đến thời gian thực hiện của thủ tục, mà chỉ quan tâm đến chi phí thực hiện thông qua việc phỏng vấn và thuê. Việc phỏng vấn thì tốn chi phí thấp – gọi là ci, nhưng ngược lại thuê thì tốn chi phí rất đắt – gọi là ch. Gọi m là số người được thuê, thì tổng chi phí của thuật toán này là O(nci + mch). Dù ta thuê bao nhiêu người đi chăng nữa thì ta cũng phải luôn phỏng vấn hết n người, và như vậy ta luôn tốn nci cho việc phỏng vấn. Vì thế, ta chỉ tập trung vào phân tích chi phí thuê mch, con số này biến đổi ứng với mỗi lần thực thi thuật toán. 1.2 Phương pháp phân tích truyền thống - Trường hợp tốt nhất Trong trường hợp tốt nhất, ta chỉ cần thực hiện việc thuê đúng 1 lần. Tức là các ứng cử viên đến theo thứ tự giảm dần về chất lượng, như vậy ta đã phỏng vấn n lần và thuê 1 lần với tổng chi phí thuê là O(ch). - Trường hợp xấu nhất Trong trường hợp xấu nhất, mọi ứng cử viên phỏng vấn ta đều thuê cả. Tức là các ứng cử viên đến theo thứ tự tăng dần về chất lượng, như vậy ta đã thuê n lần với tổng chi phí thuê là O(nch). Điều đó có thể xảy ra, tuy nhiên các ứng cử viên không phải lúc nào đến cũng theo thứ tự tăng dần. Thực tế, ta không biết hoặc không thể điều khiển thứ tự mà họ đến. Ví dụ: Cho một danh sách đã được xếp hạng theo thứ tự sau A1 = (1,2,3,4,5,6,7,8,9,10), thì sẽ mất 10 lần thuê ứng cử viên mới, vì mỗi ứng cử viên đến sau đều tốt hơn ứng cử viên trước và như vậy việc thuê (dòng 5-6 của giải thuật HIRE-ASSITANT) sẽ luôn được thực hiện với mỗi ứng cử viên. Cho danh sách được xếp hạng theo thứ tự ngược lại A2 = (10,9,8,7,6,5,4,3,2,1), thì chỉ cần mất 1 lần thuê ứng cử viên mới, vì mỗi ứng cử viên đến sau đều tệ hơn ứng cử viên trước và như vậy dòng 5-6 của giải thuật HIRE-ASSITANT chỉ thực hiện một lần đối với ứng cử viên đầu tiên. Cho danh sách được xếp hạng theo thứ tự như sau A3 = (5,2,1,8,4,7,10,9,3,6), thì mất 3 lần thuê ứng cử viên mới, đó là ứng cử viên có thứ hạng 5, 8, 10. Tóm lại, độ phức tạp của thuật toán này tùy thuộc vào số lần mà ta thuê một nhân viên mới, ta có trường hợp xấu nhất là A1, tốt nhất là A2 và trường hợp trung bình là A3. 2. PHƯƠNG PHÁP PHÂN TÍCH XÁC SUẤT 2.1 Khái niệm phân tích xác suất Phân tích xác suất là sử dụng xác suất trong việc phân tích các bài toán. Hầu hết, ta sử dụng phân tích xác suất để phân tích thời gian thực hiện của thuật toán. Đôi khi ta sử dụng nó để phân tích các đại lượng khác như phân tích chi phí thuê nhân viên trong thủ tục HIRE-ASSISTANT. Để phân tích xác suất, ta phải mô tả được sự phân phối bộ dữ liệu vào hoặc giả định về sự phân phối bộ dữ liệu vào hợp lý. Sau đó, ta phân tích thuật toán, tính toán một kỳ vọng về thời gian thực thi. Kỳ vọng này là dựa trên sự phân phối dữ liệu vào. Như vậy, ta có thể tính được trung bình thời gian thực thi dựa trên dữ liệu vào. Vậy, ta phải rất cẩn thận trong việc quyết định phân phối bộ dữ liệu vào. Ở một số bài toán, nếu ta có thể giả sử một tập hợp các bộ dữ liệu vào hợp lý thì ta có thể sử dụng phân tích xác suất như một kỹ thuật để thiết kế một thuật toán hiệu quả và như là một phương tiện để hiểu rõ bài toán. Còn nếu ở một bài toán, ta không thể mô tả một bộ phân phối dữ liệu vào hợp lý thì ta không thể sử dụng phân tích xác suất. Ở bài toán thuê nhân viên, ta có thể giả sử rằng các ứng cử viên đến theo một thứ tự ngẫu nhiên. Điều đó có nghĩa là gì? Giả sử rằng ta có thể so sánh bất kỳ 2 ứng cử viên nào và quyết định người nào tốt hơn; như vậy ta sẽ có được thứ tự toàn bộ các xếp hạng của các ứng cử viên. Ta có thể xếp hạng mỗi ứng cử viên ứng với 1 số duy nhất từ 1 đến n, sử dụng rank(i) là vị thứ của ứng cử viên i và ta quy ước rằng vị thứ cao hơn ứng với người có chất lượng tốt hơn. Danh sách thứ tự (rank(1), rank(2), …, rank(n)) là một sự hoán vị của (1, 2, …, n). Ta nói các ứng cử viên đến theo thứ tự ngẫu nhiên tương đương với việc nói rằng danh sách các hoán vị của các vị thứ là như nhau đối với mỗi hoán vị trong n! hoán vị của 1 đến n. Ta nói rằng các vị thứ tạo nên một hoán vị ngẫu nhiên đều (uniform radom permution) tức là mỗi hoán vị trong n! hoán vị xuất hiện với xác suất bằng nhau. Để thuê chính xác một lần thì ứng cử viên đến phỏng vấn đầu tiên phải là ứng cử viên tốt nhất. Như vậy xác suất để thuê chính xác một lần chính bằng xác suất để ứng cử viên tốt nhất nằm ở vị trí thứ nhất trong dãy dữ liệu vào (có n vị trí), vậy xác suất này bằng 1/n. Để thuê chính xác n lần thì các ứng cử viên phải đến theo thứ tự tăng dần về chất lượng, đây là trường hợp xấu nhất của thuật toán. Các hoán vị bộ dữ liệu vào có khả năng như nhau, mà có tất cả là n! hoán vị. Như vậy xác suất để các ứng cử viên đến theo thứ tự tăng dần là 1/n!. Nên xác suất mà bạn sẽ thuê chính xác n lần là 1/n!. 2.2 Biến chỉ thị ngẫu nhiên Để phân tích nhiều thuật toán như Bài toán thuê nhân viên ở trên ta sẽ sử dụng biến chỉ thị ngẫu nhiên. Biến chỉ thị ngẫu nhiên cho ta một phương pháp thuận tiện để chuyển đổi giữa xác suất và kỳ vọng. Giả sử rằng ta có một không gian mẫu S và một sự kiện A, thì biến chỉ thị ngẫu nhiên I{A} gắn với sự kiện A được định nghĩa như sau: I{A}= 1 nếu A xuất hiện 0 nếu A không xuất hiện (1) Một ví dụ đơn giản, để xác định được kỳ vọng của số lần xuất hiện mặt ngửa khi ta tung một đồng xu cân đối. Ta gọi không gian mẫu S = {H,T} đại diện cho mặt ngửa (H) và mặt sấp (T) của đồng xu với xác suất xuất hiện mặt ngửa và mặt sấp Pr{H}=Pr{T}=1/2. Ta có thể định nghĩa biến chỉ thị ngẫu nhiên XH là số mặt ngửa của đồng xu xuất hiện – gắn với sự kiện H. Biến này tính số mặt ngửa xuất hiện khi tung đồng xu và nó bằng 1 nếu là mặt ngửa, bằng 0 nếu ngược lại (mặt sấp). Ta viết: XH=I{H}= 1 nếu H xuất hiện 0 nếu H không xuất hiện Kỳ vọng của số mặt ngửa xuất hiện trong một lần tung đồng xu chính là giá trị kỳ vọng của biến chỉ thị XH. E[XH] = E[I{H}] = 1.Pr{H}+ 0.Pr{T} = 1.(1/2) +0.(1/2) = 1/2 Như vậy, kỳ vọng của số lượng mặt ngửa xuất hiện với một lần tung đồng xu ngẫu nhiên là 1/2. Bổ đề sau cho thấy, giá trị kỳ vọng của một biến chỉ thị ngẫu nhiên với sự kiện A chính bằng xác suất để sự kiện A xảy ra. Bổ đề 1 Cho không gian mẫu S và sự kiện A trong không gian mẫu. Gọi XA=I{A}, thì E[XA]=Pr{A} Chứng minh: Từ định nghĩa biến chỉ thị ngẫu nhiên ở công thức (1) và định nghĩa giá trị kỳ vọng, ta có: E[XA] = E[I{A }] = 1.Pr{A}+ 0.Pr{} = Pr{A} Với thể hiện sự kiện S-A (phần bù của A) Mặc dầu, biến chỉ thị ngẫu nhiên có thể làm cho ứng dụng trở nên nặng nề hơn ví dụ như việc tính kỳ vọng của số mặt ngửa xuất hiện khi tung đồng xu, nhưng nó lại rất cần thiết trong các trường hợp phân tích các mẫu thử nghiệm lặp ngẫu nhiên. 2.3 Phân tích bài toán bằng cách sử dụng biến chỉ thị ngẫu nhiên Trở lại Bài toán thuê nhân viên, ta muốn tính kỳ vọng của chi phí về thời gian khi ta thuê một nhân viên mới. Để sử dụng phương pháp phân tích xác suất, ta giả sử rằng các ứng cử viên đến theo thứ tự ngẫu nhiên. Gọi X là biến ngẫu nhiên chỉ chi phí thời gian mà ta thuê một nhân viên mới. Ta có thể áp dụng định nghĩa giá trị kỳ vọng: Nhưng cách tính toán này không được thuận tiện lắm. Vì vậy, thay vào đó ta sẽ sử dụng biến chỉ thị ngẫu nhiên để đơn giản hóa việc tính toán. Thay vì tính E[X] bằng cách định nghĩa một biến chỉ chi phí về thời gian thuê một nhân viên mới, ta dùng n biến logic riêng biệt tương ứng với mỗi ứng cử viên được thuê hoặc không được thuê. Cụ thể, ta gọi Xi là biến chỉ thị ngẫu nhiên tương ứng với sự kiện ứng cử viên thứ i được thuê. Như vậy: Xi=I{i được thuê}= 1 nếu i được thuê 0 nếu i không được thuê (2) Và X = X1 + X2 + … + Xn (3) Theo Bổ đề 1 ta có E[Xi] = Pr{i được thuê} Vì thế ta phải tính xác suất ở dòng 5-6 của thủ tục HIRE-ASSISTANT. Ở dòng 5, ứng cử viên i được thuê khi ứng cử viên thứ i tốt hơn các ứng của viên từ 1 đến i-1. Bởi vì ta đã giả định rằng các ứng cử viên đến theo thứ tự ngẫu nhiên nên i ứng cử viên đầu tiên đã xuất hiện theo thứ tự ngẫu nhiên. Bất kỳ một ứng cử viên nào trong i ứng cử đầu tiên đều có thể được xem là tốt nhất. Ứng cử viên thứ i có xác suất là 1/i khả năng tốt hơn các ứng cử viên từ 1 đến i-1, và như vậy 1/i là xác suất được thuê. Theo Bổ đề 1 ta có được: E[Xi] = 1/i (4) Suy ra: (Theo công thức (3)) (5) (Theo tính chất tuyến tính của kỳ vọng) (Theo công thức (4)) (6) Mặc dù ta phỏng vấn n người nhưng thực tế trung bình ta chỉ thuê xấp xỉ ln n lần. Ta tóm tắt kết quả này trong bổ đề sau: Bổ đề 2 Giả sử rằng các ứng cử viên đến theo thứ tự ngẫu nhiên, thì thuật toán HIRE – ASSISTANT có độ phức tạp là O(ch ln n). Chứng minh: Hiển nhiên, ta có được từ định nghĩa về chi phí thuê và công thức (6). Kỳ vọng của chi phí thuê là sự cải tiến dựa trên trường hợp xấu nhất có độ phức tạp O(nch). 3. PHƯƠNG PHÁP SỬ DỤNG THUẬT TOÁN NGẪU NHIÊN 3.1 Khái niệm thuật toán ngẫu nhiên Để sử dụng phân tích xác suất, ta cần biết một vài điều về sự phân phối bộ dữ liệu vào. Trong nhiều trường hợp, ta biết rất ít về sự phân phối dữ liệu vào. Thậm chí nếu ta về sự phân phối này thì ta cũng không thể mô hình được điều mà ta biết. Trong Bài toán thuê nhân viên, các ứng cử viên được đưa đến theo thứ tự ngẫu nhiên nhưng ta không có cách nào để biết được điều đó. Vì vậy, để phát triển thuật toán ngẫu nhiên đối với Bài toán thuê nhân viên này, ta điều khiển thứ tự các ứng cử viên khi vào phỏng vấn bằng cách chọn ngẫu nhiên các ứng cử viên để phỏng vấn. Mặc dù ta không biết gì về các ứng cử viên (ngoài tên của họ) nhưng ta đã tạo ra một sự thay đổi có ý nghĩa. Thay vì tin vào một phỏng đoán là các ứng cử viên đến theo thứ tự ngẫu nhiên thì ta đã điều khiển được tiến trình và buộc nó phải theo một thứ tự ngẫu nhiên. Nói chung, ta gọi thuật toán ngẫu nhiên nếu hành vi của nó được xác định không chỉ bởi dữ liệu vào mà còn bằng các giá trị được tạo ra bởi bộ tạo số ngẫu nhiên (random-number generator). Giả sử ta có sẵn hàm sinh số ngẫu nhiên RANDOM. Một lời gọi RANDOM(a,b) trả về 1 số nguyên giữa a và b, với mỗi giá trị trả về như vậy có xác suất bằng nhau. Ví dụ, RANDOM(0,1) cho kết quả 0 với xác suất là ½ và cho kết quả 1 với xác suất ½. Một lời gọi RANDOM(3,7) trả về kết quả là 3, 4, 5, 6 hoặc 7 với xác suất là 1/5. Mỗi số nguyên được trả về bởi hàm RANDOM không phụ thuộc vào các số nguyên trả về ở các lời gọi trước đó. Thông thường, hầu hết các môi trường lập trình đều đề cập đến pseudo-random number generator - bộ tạo số giả ngẫu nhiên. 3.2 Ứng dụng thuật toán ngẫu nhiên trong phân tích bài toán Trong phần trước, ta đã chỉ ra cách để phân phối dữ liệu vào để phân tích trường hợp trung bình của thuật toán. Nhiều khi, ta không hoặc không thể phân tích trường hợp trung bình của thuật toán. Như đã đề cập trong phần 1, ta có thể sử dụng thuật toán ngẫu nhiên. Thuật toán ngẫu nhiên là phương pháp đơn giản và hiệu quả nhất để giải quyết các bài toán. Chẳng hạn như Bài toán thuê nhân viên ở trên, giả định rằng tất cả các hoán vị của dữ liệu vào đều như nhau thì việc phân tích xác suất sẽ hướng cho ta phát triển thành thuật toán ngẫu nhiên. Thay vì cho một bộ dữ liệu vào, ta tráo đổi bộ dữ liệu đó. Cụ thể là trước khi thực hiện thuật toán, ta hoán đổi các ứng cử viên một cách ngẫu nhiên để chứng tỏ rằng các hoán vị đều như nhau. Điều này không làm thay đổi kỳ vọng của chi phí thời gian để thuê một nhân viên mới (có giá trị xấp xỉ ln n). Khi sử dụng phương pháp thuật toán ngẫu nhiên, đầu tiên chúng ta hoán đổi ngẫu nhiên danh sách các ứng cử viên, và sau đó tiến hành phỏng vấn để ghi nhận ứng cử viên tốt nhất. Trong trường hợp này, sự ngẫu nhiên nằm ở trong thuật toán chứ không ở trong việc phân phối dữ liệu vào. Cho 1 dữ liệu vào cụ thể, ví dụ như A3 ở trên, ta không biết được số lần tối đa phép toán được thực hiện là bao nhiêu bởi vì con số này thay đổi với mỗi lần thực hiện thuật toán. Lần đầu tiên, ta thực thi thuật toán trên A3, nó tạo ra 1 hoán vị A1 và thực hiện 10 lần cập nhật, trong khi thuật toán thực thi lần thứ 2, nó sẽ tạo ra 1 hoán vị A2 và thực hiện 1 lần cập nhật. Lần thực hiện thuật toán thứ 3, nó sẽ tạo ra 1 hoán vị ngẫu nhiên khác và sẽ thực hiện một số lần cập nhật nào đó. Cứ mỗi lần thực thi thuật toán, việc thực thi thuật toán tùy thuộc vào sự lựa chọn ngẫu nhiên được tạo ra ban đầu và lúc nào cũng khác với các lần thực thi ở trước. Đối với thuật toán này và nhiều thuật toán ngẫu nhiên khác, không có trường hợp dữ liệu vào cho ra trường hợp xấu nhất. Thuật toán ngẫu nhiên thực hiện chỉ xấu khi hàm sinh số ngẫu nhiên tạo ra một hoán vị không may mắn. Nên đối với Bài toán thuê nhân viên, chỉ có một thay đổi là thêm vào phép hoán vị ngẫu nhiên dãy dữ liệu vào ở đầu thuật toán. * Thủ tục RANDOMIZED-HIRE-ASSITANT 1. Thực hiện hoán đổi ngẫu nhiên danh sách các ứng cử viên 2. BEST:=0 {ứng cử viên bù nhìn thứ 0 có chất lượng tệ nhất} 3. For i:=1 to n do 4. 5. if then 6. BEST: = i 7. Bổ đề 3 Kỳ vọng của độ phức tạp đối với thuật toán RANDOMIZED-HIRE-ASSITANT là O(ch ln n) So sánh Bổ đề 2 và Bổ đề 3 ta thấy rõ sự khác biệt giữa phân tích xác suất và thuật toán ngẫu nhiên. Ở Bổ đề 2, ta gán một bộ dữ liệu vào, còn ở Bổ đề 3, ta không làm như vậy, mặc dù ta mất một lượng thời gian để hoán đổi ngẫu nhiên dữ liệu vào. Dưới đây ta sẽ thảo luận một vài vấn đề liên quan đến việc hoán đổi ngẫu nhiên dữ liệu vào. 3.3 Các thuật toán hoán đổi ngẫu nhiên dữ liệu vào Có nhiều thuật toán hoán đổi ngẫu nhiên dữ liệu vào (có nhiều cách hoán đổi). Ở đây ta sẽ thảo luận hai phương pháp. Giả sử rằng A là một dãy gồm các phần tử từ 1 đến n, mục đích của ta là tạo ra một hoán đổi ngẫu nhiên của dãy này. Cả hai phương pháp dưới đây đều sử dụng hàm Random(a, b) dùng để sinh ra một số ngẫu nhiên nằm trong khoảng giữa a và b. Khi đưa các thuật toán này vào phần mềm R, trong R có rất nhiều hàm sinh số ngẫu nhiên theo các luật phân phối khác nhau. Ở đây ta chỉ cần sử dụng hàm runif(n, min=a, max=b) để tạo ra một dãy gồm n số ngẫu nhiên nằm trong khoảng min và max (ở đây tương ứng là min=a và max=b), dãy này tuân theo luật phân phối đều. a. Thủ tục PERMUTE-BY-SORTING Phương pháp thứ nhất là gán mỗi phần tử A[i] của dãy tương ứng với P[i] – thứ tự ưu tiên ngẫu nhiên và sau đó sắp xếp các phần tử của dãy A theo thứ tự ưu tiên này. Ví dụ: Nếu dãy ban đầu là A= (1, 2, 3, 4) và ta chọn thứ tự ưu tiên ngẫu nhiên là P= (36, 3, 97, 19) thì ta được mảng B =(2, 4, 1, 3) và ưu tiên của phần tử thứ 2 là nhỏ nhất, tiếp đến là phần tử thứ 4, phần tử thứ nhất và cuối cùng là phần tử thứ 3. Ta gọi thủ tục này là PERMUTE-BY-SORTING. PERMUTE-BY-SORTING (A) 1. n := length [A] 2. for i:= 1 to n do 3. P[i] := Random (1,n3) 4. Sắp xếp dãy A theo P 5. Return A Trong đó thủ tục sắp xếp dãy A theo P thực hiện như sau: For i:=1 to n-1 do For j:=i+1 to n do If P[i] > P[j] then Hoán đổi A[i] với A[j]; Ở dòng 3 ta chọn những số ngẫu nhiên nằm trong khoảng từ 1 đến n3. Việc chọn giá trị n3 nhằm bảo đảm các giá trị ngẫu nhiên tạo ra sẽ gần như là duy nhất. Ở đây ta xem như các thứ tự ưu tiên là duy nhất. (Trong trường hợp có hai hay nhiều thứ tự ưu tiên P[i] bằng nhau do hàm Random(1,n3) cho cùng 1 kết quả thì dãy A vẫn được sắp xếp theo P, lúc này các phần tử có thứ tự ưu tiên bằng nhau đứng liên tiếp nhau. Vì dãy có n phần tử, nên ta luôn có n! hoán vị, và xác suất của mỗi hoán vị là 1/n! cho dù có hai hay nhiều thứ tự ưu tiên P[i] bằng nhau đi chăng nữa.) Trong thuật toán này, bước đòi hỏi mất nhiều thời gian nhất là ở dòng 4. Ta biết rằng nếu sử dụng thuật toán sắp xếp so sánh thì mất thời gian Ω(nlgn). Sau khi sắp xếp, nếu P[i] có thứ tự ưu tiên nhỏ nhất là j, thì A[i] sẽ nằm ở vị trí j. Ở một khía cạnh nào đó ta có được một sự hoán vị. Chứng tỏ rằng thuật toán tạo ra một hoán vị ngẫu nhiên đều tức là mỗi hoán vị từ 1 đến n đều có khả năng như nhau. Bổ đề 4 Giả sử tất cả các thứ tự ưu tiên đều khác nhau, thì thủ tục PERMUTE-BY-SORTING tạo ra một hoán vị ngẫu nhiên đều. Chứng minh: Ta xét một hoán vị cụ thể mà ở đó mỗi phần tử A[i] nhận i là thứ tự ưu tiên nhỏ nhất. Ta cần chứng minh rằng hoán vị này xuất hiện với xác suất chính xác 1/n!. Cho i = 1, 2, 3, …, n, gọi Xi là sự kiện mà phần tử A[i] nhận i là thứ tự ưu tiên nhỏ nhất. Ta tính xác suất mà với mọi i, sự kiện Xi xuất hiện: = Ta đã có Pr{X1}=1/n, bởi vì xác suất để chọn ngẫu nhiên 1 phần tử trong tập gồm n phần tử là 1/n. Tiếp theo, ta còn lại n-1 phần tử, ta tính Pr{X2|X1}=1/(n-1) vì đã có phần tử A[1] có độ ưu tiên nhỏ nhất. Như vậy, Với i=2,3,…,n ta có Pr{Xi | Xi-1ÇXi-2Ç…ÇX1} = 1/(n-i+1) vì đã có các phần tử từ A[1] đến A[i-1] có i-1thứ tự ưu tiên nhỏ nhất, n-(i-1) phần tử còn lại có độ ưu tiên nhỏ nhất như nhau là i, Do vậy, ta có: Vậy, xác suất của hoán vị là bằng 1/n! Ta có thể mở rộng chứng minh cho bất kỳ một hoán vị ưu tiên nào. Xem xét bất kỳ một hoán vị cố định σ =(σ(1), σ(2), ….., σ(n)) của tập {1, 2, …, n}. Gọi ri là độ ưu tiên của A[i], với độ ưu tiên nhỏ nhất là j – xếp hạng thứ j. Nếu ta gọi Xi là sự kiện A[i] nhận σ(i) là độ ưu tiên nhỏ nhất hoặc ri = σ(i), thì giống chứng minh trên. Vì vậy, nếu ta tính xác suất của một hoán vị bất kỳ nào đó thì thu được kết quả giống như trên. Như vậy xác suất của sự hoán vị này luôn luôn là 1/n!. Có thể nói rằng để chứng minh một hoán vị là hoán vị ngẫu nhiên đều thì đủ để chứng tỏ rằng với mỗi phần tử A[i] xác suất mà A[i] nằm ở vị trí j là 1/n. b. Thủ tục RANDOM-IN-PLACE Một phương pháp tốt hơn tạo một hoán vị dựa trên thứ tự ưu tiên ngẫu nhiên là hoán vị ngẫu nhiên trực tiếp trên dãy số đã cho. Thuật toán RANDOM-IN-PLACE dưới đây có độ phức tạp là O(n). RANDOM-IN-PLACE(A) 1. n:= length(A); 2. For i:= 1 to n do 3. Trong lần lặp thứ i, phần tử A[i] được chọn ngẫu nhiên trong khoảng A[i] đến A[n]. Sau lần lặp thứ i, A[i] không bao giờ bị thay đổi. Đây là sự bất biến của vòng lặp. Ta sẽ sử dụng sự bất biến của vòng lặp để chứng tỏ rằng thuật toán RANDOM-IN-PLACE sinh ra một hoán vị ngẫu nhiên đều. Cho tập hợp gồm n phần tử, một bộ hoán vị-k là dãy chứa k phần tử trong n phần tử. Ta có n!/(n-k)! hoán vị như thế. Bổ đề 5 Thuật toán RANDOM-IN-PLACE sinh ra một hoán vị ngẫu nhiên đều. Chứng minh: Ta sử dụng sự bất biến của vòng lặp sau đây: Chỉ lần lặp thứ i trở về trước trong vòng For ở dòng 2 – 3, mỗi bộ hoán vị-(i – 1) thì xác suất mà dãy A[1.. i-1] chứa bộ hoán vị-(i-1) là (n-i+1)!/n! (vì có n!/(n-i+1)! hoán vị như thế). Ta cần chứng tỏ rằng sự bất biến này: (i) đúng ở trước lần lặp đầu tiên; (ii) duy trì với các lần lặp tiếp theo; (iii) đúng cho đến khi kết thúc vòng lặp. - Trước lần lặp đầu tiên: Xét trường hợp trước lần lặp đầu tiên, tức là trường hợp i = 1. Vòng lặp bất biến chỉ ra rằng mỗi bộ hoán vị-0 thì xác suất mà dãy A[1..0] chứa bộ hoán vị-0 là (n – i +1)!/n! = n!/n! = 1. Dãy con A[1..0] là một dãy con rỗng và bộ hoán vị-0 không có phần tử. Như vậy, dãy A[1..0] chứa bộ hoán vị-0 với xác suất là 1 và vòng lặp bất biến đúng cho đến lần lặp đầu tiên. - Ở các lần lặp tiếp theo: Ta giả sử rằng trước lần lặp thứ i, xác suất mà mỗi bộ hoán vị-(i – 1) xuất hiện trong dãy A[1..i-1] là (n – i +1)!/n! và ta sẽ chứng tỏ rằng sau lần lặp thứ i, mỗi bộ hoán vị-i xuất hiện trong dãy A[1..i] với xác suất (n – i)!/n!. Tăng i cho mỗi lần lặp thì sẽ duy trì được sự bất biến của vòng lặp. Ta xét ở lần lặp thứ i. Xét một bộ hoán vị-i cụ thể, được biễu diễn bởi (x1, x2, ..,xi). Hoán vị này chứa bộ hoán vị-(i-1) (x1, x2, ..,xi-1) tiếp theo đó là giá trị xi đặt ở vị trí A[i]. Gọi E1 là sự kiện mà i-1 lần lặp đầu tiên đã tạo ra bộ hoán vị-(i – 1) (x1, x2, ..,xi-1) trong dãy A[1..i-1]. Vì sự bất biến của vòng lặp nên Pr{E1} = (n – i +1)!/n!. Gọi E2 là sự kiện ở lần lặp thứ i, đặt xi ở vị trí A[i]. Bộ hoán vị-i (x1, x2, ..,xi) được tạo thành trong dãy A[1..i] khi cả hai sự kiện E1 và E2 cùng xuất hiện, ta sẽ tính được Pr{E2∩E1} Theo công thức xác suất có điều kiện, ta có: Pr{E2∩E1} = Pr{E2 |E1} Pr{E1} Xác suất Pr{E2 |E1} = 1/(n – i +1) vì ở dòng 3 trong thuật toán chọn xi ngẫu nhiên từ n – i +1 giá trị trong các vị trí của A[i ...n]. Như vậy, ta có: Pr{E2∩E1} = P{E2 |E1} Pr{E1} - Kết thúc vòng lặp: Với i = n, xác suất bộ hoán vị-n trong dãy A[1..n] là (n – n)!/n! = 1/n! Như vậy, thuật toán RANDOM-IN-PLACE tạo ra một hoán vị ngẫu nhiên đều. Bây giờ giả sử rằng thay vì hoán đổi phần tử A[i] với phần tử ngẫu nhiên trong dãy A[i..n], ta hoán đổi A[i] với phần tử ngẫu nhiên bất kỳ trong toàn bộ dãy A[1..n]: RANDOM-WITH-ALL (A) 1. n:= length(A); 2. For i:= 1 to n do 3. Ta chứng minh rằng thủ tục trên không sinh ra hoán vị ngẫu nhiên đều: Gọi E1 là sự kiện mà i-1 lần lặp đầu tiên đã tạo ra hoán vị-(i – 1) (x1, x2, ..,xi-1) trong dãy A[1..i-1]. Vì tại mỗi lần lặp thứ k, có thể hoán đổi phần tử a[k] với bất kỳ phần tử nào trong n phần tử từ 1 đến n. Ta có Pr{E1} = 1/ni-1 Gọi E2 là sự kiện ở lần lặp thứ i, đặt xi ở vị trí A[i]. Hoán vị-i (x1, x2, ..,xi) được tạo thành trong dãy A[1..i] một cách chính xác khi cả hai sự kiện E1 và E2 cùng xuất hiện, ta sẽ tính được Pr{E2∩E1} Pr{E2∩E1} = Pr{E2 } Pr{E1} Xác suất Pr{E2} = 1/n vì ta có thể chọn xi ngẫu nhiên từ n giá trị trong các vị trí của A[1...n]. Như vậy, ta có: Pr{E2∩E1} = P{E2} Pr{E1}=1/ni-1 x 1/n =1/ni Với i = n thì xác suất sinh hoán vị là 1/nn ≠ 1/n! (Vì có tất cả là n! hoán vị, do đó mỗi hoán vị đều phải là 1/n!) Vậy, thủ tục này không sinh hoán vị ngẫu nhiên đều. 3.4 Mở rộng bài toán Tiếp theo, ta sẽ xét Bài toán thuê nhân viên theo cách khác. Giả sử rằng ta không muốn phỏng vấn hết tất cả các ứng cử viên để tìm ra ứng cử viên tốt nhất. Ta cũng không muốn cứ sa thải và thuê mới khi thấy các ứng cử viên đến mỗi lúc càng tốt hơn. Thay vào đó, ta sẵn sàng chấp nhận ứng cử viên gần tốt nhất để chỉ cần sa thải và thuê chính xác một lần. Ta phải tuân theo các yêu cầu của công ty: tức là sau mỗi lần phỏng vấn hoặc là ngay lập tức ta phải đề xuất một vị trí cho họ hoặc là thông báo cho họ rằng họ không được nhân việc. Sự kết hợp tốt nhất giữa số lượng nhỏ nhất các lần phỏng vấn với chất lượng tốt nhất của ứng cử viên được thuê là như thế nào? Ta có thể mô hình hóa bài toán này bằng cách sau. Sau khi phỏng vấn một ứng cử viên ta có thể cho mỗi người một con số điểm nào đó, Gọi score (i) là điểm của nhân viên thứ i, giả sử rằng không có hai nhân viên nào có cùng số điểm. Sau khi phỏng vấn được j người, ta biết ứng cử viên nào trong j ứng cử viên này có điểm cao nhất, nhưng ta không biết liệu n – j ứng cử viên còn lại có thể có điểm cao hơn không. Ta quyết định chấp nhận một chiến lược là lựa chọn một số nguyên dương k < n, phỏng vấn rồi loại bỏ k ứng cử viên đầu tiên, thuê ứng cử viên đầu tiên người mà có điểm cao hơn tất cả các ứng cử viên trước đó. Nếu nhân viên có năng lực tốt nhất nằm trong k nhân viên được phỏng vấn đầu tiên thì ta sẽ thuê nhân viên thứ n. Chiến lược này được mô hình hóa ở thủ tục ON-LINE- MAXIMUM(k,n) dưới đây. Thủ tục này trả về chỉ số của ứng cử viên mà ta muốn thuê. * Thủ tục ON-LINE-MAXIMUM(k,n) 1 bestscore := -∞ 2 for i := 1 to k do 3 if score (i) > bestscore then 4 bestscore := score (i) 5 for i := k + 1 to n do 6 if score(i) > bestscore then 7 return i 8 return n Ta muốn xác định với mỗi giá trị của k xác suất mà ta thuê được ứng cử viên tốt nhất. Sau đó, ta sẽ chọn giá trị tốt nhất của k và thực hiện chiến lược này với giá trị đó. Giả sử rằng k được cố định. Gọi M(j) = max1≤i≤j{score(i)} là số điểm lớn nhất của ứng cử viên thứ 1 đến j. Gọi S là sự kiện ta chọn thành công ứng cử viên có năng lực tốt nhất và Si là sự kiện ta chọn thành công ứng cử viên có năng lực tốt nhất được phỏng vấn lần thứ i. Vì các giá trị Si khác nhau là rời rạc nên ta có: Pr{S} = Chú ý rằng ta sẽ không bao giờ thành công khi ứng cử viên có năng lực tốt nhất là một trong k ứng cử viên đầu tiên, ta có Pr{Si} = 0 với i = 1, 2, ..., k. Như vậy, ta được: Pr{S} = (7) Bây giờ ta tính Pr{Si}. Để có được thành công khi ứng cử viên có năng lực tốt nhất là ứng cử viên thứ i thì hai sự kiện sau phải xảy ra đồng thời. Thứ nhất, ứng cử viên có năng lực tốt nhất phải ở vị trí i – sự kiện này ta biễu diễn bởi Bi. Thứ hai, giải thuật phải không chọn bất kỳ một ứng cử viên nào từ vị trí k +1 đến i – 1, điều này xảy ra nếu với mỗi j từ k + 1 ≤ j ≤ i – 1 thì score (j) < bestscore ở dòng 6 (Bởi vì các điểm số là duy nhất và ta có thể bỏ qua khả năng score (j) = bestscore). Một cách diễn đạt khác, đó là trường hợp tất cả các giá trị từ score (k+1) đến score (i -1) đều nhỏ hơn M(k); nếu có bất kỳ một giá trị nào đó lớn hơn M(k) thì ta sẽ trả về chỉ số của người lớn hơn đầu tiên đó. Ta gọi Oi là sự kiện mà không có nhân viên nào trong khoảng k + 1 đến i – 1 được chọn. Hai sự kiện Bi và Oi độc lập nhau. Sự kiện Oi chỉ phụ thuộc vào thứ tự tương đối của các giá trị ở vị trí từ 1 đến i -1, trái lại sự kiện Bi chỉ phụ thuộc vào giá trị ở vị trí i có lớn hơn giá trị ở các vị trí khác không. Thứ tự của các giá trị từ 1 đến i- 1 không ảnh hưởng đến việc giá trị ở vị trí i lớn hơn tất cả các giá trị ở những vị trí khác hay không và giá trị ở vị trí i không ảnh hưởng đến thứ tự của các giá trị từ 1 đến i -1. Như vậy, áp dụng công thức về các sự kiện độc lập ta có: Pr{Si} = Pr{Bi ∩ Oi} = Pr{Bi}Pr{Oi} Xác suất Pr{Bi} rõ ràng bằng 1/n, vì giá trị lớn nhất có thể nằm ở bất kỳ vị trí nào trong n vị trí. Để sự kiện Oi xuất hiện, giá trị lớn nhất từ vị trí thứ 1 đến i – 1 phải là một trong k vị trí đầu tiên và nó có thể là bất kỳ giá trị nào trong i – 1 vị trí. Cho nên, Pr{Oi} = k/ (i –1), suy ra Pr{Si}= k/ (n(i -1)). Sử dụng công thức (7) ta có: Theo bất đẳng thức Giới hạn của một tổng bởi các tích phân, ta có: Suy ra: Đây là một giới hạn chặt chẽ hơn đối với Pr{Si}. Bởi vì ta muốn xác suất thành công là lớn nhất, nên ta tập trung vào chọn giá trị k mà xác suất Pr{S} đạt giá trị lớn nhất là tại cận trên của Pr{S}. (Ngoài ra, biểu thức giới hạn trên dễ dàng đạt giá trị cực đại hơn biểu thức giới hạn dưới). Lấy vi phân biểu thức (k/n)(ln n – ln k) đối với k, ta được: (ln n – ln k – 1) Đặt đạo hàm này bằng 0, ta thấy giới hạn dưới của xác suất là lớn nhất khi ln k = ln n – 1 = ln (n/e) hay tương đương với k = n/e. Như vậy, nếu ta thực hiện chiến lược với k = n/e thì ta sẽ thành công với việc thuê ứng cử viên tốt nhất với xác suất ít nhất là 1/e. TÀI LIỆU THAM KHẢO [1] Trần Lộc Hùng, Cơ sở mô phỏng ngẫu nhiên, NXB Giáo dục, 1997. [2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, 2nd Edition.