Bài toán thư ký
Bài toán thư ký là một bài toán nổi tiếng trong lý
thuyết dừng tối ưu. Bài toán này đã được nghiên cứu trong xác suất ứng
dụng, thống kê, và lý thuyết quyết định.
Dạng cơ bản của bài toán là như sau. Một người quản lý cần tuyển thư ký tốt nhất trong n
ứng viên có thể xếp hạng. Các ứng viên được phỏng vấn lần lượt theo một
thứ tự ngẫu nhiên. Quyết định cho mỗi ứng viên phải được đưa ra ngay
sau khi phỏng vấn ứng viên đó. Sau khi đã bị từ chối, ứng viên đó sẽ
không thể được tuyển. Trong quá trình phỏng vấn, người quản lý có thể
xếp hạng các ứng viên đã phỏng vấn nhưng không biết gì về chất lượng của
các ứng viên chưa phỏng vấn. Câu hỏi đặt ra là nên sử dụng chiến thuật
nào để tối ưu hóa xác suất tuyển được ứng viên tốt nhất.
Bài toán cơ bản trên có một lời giải đẹp. Đầu tiên phỏng vấn và từ chối khoảng n/e ứng viên (trong đó e
là cơ số của lôgarit tự nhiên). Sau đó chấp nhận ứng viên đầu tiên tốt
hơn tất cả các ứng viên đã được phỏng vấn trước đó (hoặc chấp nhận ứng
viên cuối cùng nếu điều này không xảy ra). Nếu áp dụng thuật toán này
thì xác suất tuyển được ứng viên tốt nhất là khoảng 1/e và đây cũng là xác suất tối ưu.
Nguồn gốc của bài toán
Bài toán được xuất bản lần đầu tiên bởi Martin Gardner trong Scientific American năm 1960.
Bài báo năm 1989 của T. S. Ferguson chỉ ra rằng có những bài toán khác tương tự đã được xem xét bởi Arthur Cayley năm 1875 và Johannes Kepler từ lâu trước đó.
- Title : Bài toán thư ký
- Posted by :
- Date : Thứ Tư, tháng 9 11, 2013
- Labels : Những bài toán nổi tiếng
