Bài toán đố sau là do Mohammad Mahdian truyền bá ở hội nghị FOCS 2005, biết thông qua 3dpancakes.
Có
n \geq 2
quả bong bóng (chưa thổi) với thể tích
1, 1/2, \dots, 1/n
. Ta không biết bóng nào có thể tích nào. Thổi quá thể tích thì bóng vỡ. Tìm một phương pháp thổi ngẫu nhiên hóa sao cho tổng thể tích kỳ vọng (expected volume) của không khí trong các bóng (chưa vỡ) là lớn nhất. Ví dụ:
- Thổi tất cả các bóng đến thể tích 1. Kết quả là 1 vì (n-1) bóng còn lại vỡ mất.
- Thổi tất cả các bóng đến thể tích 1/n. Kết quả là 1 vì không có bóng nào vỡ.
- Chọn một thứ tự ngẫu nhiên, thổi thể tích 1 đến quả đầu tiên không vỡ, sau đó thổi thể tích 1/n. Thể tích kỳ vọng sẽ là
\sum_{i=1}^n\frac 1 n \cdot \left( 1 + \frac{n-i}{n} \right) = \frac 3 2 - \frac{1}{2n}
Thể tích này gần khoảng 1.5 khi n lớn.
Có cách nào làm tốt hơn 1.5 không?
8 Comments
Cách thứ 3 vẫn tồn tại 1 sác xuất lựa chọn quả có thể tích 1 cuối cùng -> V=1
Như vậy kết quả của cách này phụ thuộc nhiều vào số thứ tự của quả có thể tích 1 được chọn.
Kết quả 1.5 chính bằng 1+1/2 vì vậy, đồ rằng sẽ có khả năng để thổi đạt 1+1/2+1/3 khi n lớn, với biến cố đêm thử không phải là 1 mà có thể là 1/2 chẳng hạn.
Các biến cố gieo cũng không cố định từ 2 đầu là 1 và 1/n nữa mà có thể tiến dần về giá trị trung bình.
Ở trên mới chỉ là đánh giá cá nhân khi xem kết quả của cách thứ 3, chưa kiểm chứng
Ở 3dpancakes (link trong bài) đã ghi lời giải cho xác suất
và một lời giải tốt hơn cho ra xác suất
(đây là lời giải mà Mohammad đưa ra trong hội nghị FOCS 2005). Ví dụ cho ra lời giải 1.5 chỉ có tính minh họa cho cụm từ “phương pháp thổi ngẫu nhiên hóa”
Nếu bạn có lời giải cho ra xác suất
thì lời giải của bạn tốt hơn các lời giải tôi biết cho bài này.
Tôi chưa đủ trình độ để nghĩ ra lời giải, nhưng tôi muốn biết với những bài toán dạng này có thể chứng minh được một lời giải tôí ưu không (optimal solution).
Riêng với bài này thì tôi phải suy nghĩ thêm. Một số bài loại này có thể chứng minh sự tối ưu được bằng cách giới hạn một lớp các giải thuật ngẫu nhiên nhất định, mô hình chúng bằng một công cụ nào đó (probabilistic Turing machine chẳng hạn), sau đó dùng các kết quả về độ phức tạp tính toán để chứng minh tính tối ưu. Một ví dụ cơ bản là bài toán Max3SAT và các randomized algorithms mà có thể derandomized được. Nếu expected solution cost là 8/7 (của tổng số clauses) thì thuật toán đó optimal. Xem thêm ở đây và ở đây.
Bài này là một dạng đặc biệt thuộc lớp bài toán sequential-decision making và có thể giải tổng quát cho từng giá trị n cụ thể bằng phương pháp dynamic programming. Tuy nhiên có lẽ với n lớn thì việc tính toán này sẽ không hữu dụng vì phải dynamic programming đòi hỏi nhiều tính toán. Tuy nhiên, có lẽ hiểu được structure của optimal solution có thể giúp ta tính được asymptotically optimal solution (khi n tiến đến vô cùng).
Một ví dụ của dạng bài sequential decision making chính là sequential analysis theory của Abraham Wald, sau đó được phát triển tổng quát lên thành lớp bài toán Markov decision processes và phương phát dynamic programming (Richard Bellman).
Quay lại bài toán trên: Giả sử chúng ta các quả bóng được sắp xếp theo thứ tự ngẫu nhiên (tất cả n! hoán vị đều có xác suất như nhau), ký hiệu bởi thể tích của chúng X_1,…,X_n. Giả sử ta sẽ thử các quả bóng theo thứ tự này. Tại thời điểm k, ta chọn quả X_k (tất nhiên ta không biết giá trị thể tích X_k). Vấn đề là ta phải phải quyết định thổi quả X_k một lượng U_k. Nếu U_k
Hình như comment section bị chặn quota. Tôi viết dài hơn nhưng comment bị cắt mất sau khi đã gửi đi.
Không phải đâu, Long xem post này. Ngoài ra, cái post đó không bị mất. Có thể edit trực tiếp được (click “edit this”).
Bác Long viết tiếp phần giải quyết bài này đi ạ. Em vào trang 3dpancakes không thấy bài toán này.