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 đó.

Ghi chú

Tham khảo

 Hill, T.P. "Knowing When to Stop". American Scientist, Vol. 97, 126-133 (2009). (Có một bản dịch tiếng Pháp tại cover story  trong số tháng 7 của Pour la Science (2009))

 Merrill R. Flood, thư viết năm 1958, một bản sao nằm trong bài báo của Martin Gardner tại Stanford University Archives, series 1, box 5, folder 19.
 Martin Gardner, "New Mathematical Diversions" trong Scientific American. Simon and Schuster, 1966, Chương 3, bài 3 [in lại từ bài báo xuất bản tháng 2 năm 1960 với thông tin bổ sung].

Framing Our Thoughts: Ecological Rationality as Evolutionary Psychology's Answer to the Frame Problem, Timothy Ketelaar and Peter M. Todd, Chương 5 của Conceptual Challenges in Evolutionary Psychology, tr. 187.

Lý thuyết quyết định