Vấn đề treo cổ nghịch ngợm

Question

Nghịch lý Hangman là một trò chơi được chơi nhiều như Hangman thông thường với một sự khác biệt quan trọng: Từ chiến thắng được xác định tự động bởi ngôi nhà tùy thuộc vào những chữ cái đã được đoán. Ví dụ: giả sử bạn có bảng _ A I L và 12 lần đoán còn lại. Bởi vì có 13 từ khác nhau kết thúc trong AIL (bảo lãnh, thất bại, mưa đá, tù, kail, mail, móng tay, thùng, đường sắt, buồm, đuôi, vail, than van) nhà được đảm bảo để giành chiến thắng vì không có vấn đề gì 12 chữ cái bạn đoán , ngôi nhà sẽ yêu cầu từ được chọn là từ bạn không đoán. Tuy nhiên, nếu bảng là _ I L M, bạn đã dồn vào nhà vì FILM là từ duy nhất kết thúc bằng ILM.

Thách thức là: Với một cuốn từ điển, chiều dài từ & số câu trả lời cho phép, đưa ra một thuật toán mà một trong hai:

a) chứng minh rằng các cầu thủ luôn luôn thắng bởi outputting một cây quyết định cho các cầu thủ mà góc nhà không có vấn đề gì

b) chứng minh ngôi nhà luôn thắng bằng cách đưa ra một cây quyết định cho ngôi nhà cho phép nhà trốn thoát bất kể điều gì.

Như một ví dụ đồ chơi, xem xét các từ điển:

bat 
bar 
car 

Nếu bạn được phép 3 lần đoán sai, người chơi thắng với cây sau:

Guess B 
NO -> Guess C, Guess A, Guess R, WIN 
YES-> Guess T 
     NO -> Guess A, Guess R, WIN 
     YES-> Guess A, WIN 

Answer 1

này là gần như giống hệt với " làm cách nào để tìm đồng tiền kỳ lạ bằng cách cân nhắc lặp đi lặp lại? " vấn đề. Thông tin chi tiết cơ bản là bạn đang cố gắng tối đa hóa lượng thông tin bạn thu được từ phỏng đoán của mình.

Thuật toán tham lam để xây dựng cây quyết định như sau: - cho mỗi lần đoán, chọn phỏng đoán câu trả lời là "đúng" và câu trả lời là "sai" gần bằng 50-50 có thể, như thông tin về mặt lý thuyết, điều này mang lại nhiều thông tin nhất.

Gọi N là kích thước của tập hợp, A là kích thước của bảng chữ cái và L là số chữ cái trong từ.

Vì vậy, hãy đặt tất cả các từ của bạn trong một bộ. Đối với mỗi vị trí thư, và cho mỗi chữ cái trong bảng chữ cái của bạn đếm có bao nhiêu từ có chữ cái đó trong vị trí đó (điều này có thể được tối ưu hóa với một bảng băm bổ sung). Chọn số có kích thước gần bằng một nửa bộ. Đây là O (L * A).

Chia bộ này thành hai bằng cách lấy tập hợp con có chữ cái này ở vị trí này và đặt hai nhánh đó vào cây. Lặp lại cho mỗi tập hợp con cho đến khi bạn có toàn bộ cây. Trong trường hợp xấu nhất này sẽ yêu cầu O (N) bước, nhưng nếu bạn có một từ điển tốt đẹp này sẽ dẫn đến O (logN) bước.

Answer 2

Đây không phải là câu trả lời đúng, vì nó không cung cấp cho bạn cây quyết định, nhưng tôi đã làm điều gì đó rất giống khi viết hangman solver. Về cơ bản, nó nhìn vào tập các từ trong từ điển phù hợp với mẫu và chọn chữ cái phổ biến nhất. Nếu nó đoán sai, nó sẽ loại bỏ số lượng ứng cử viên lớn nhất. Vì không có hình phạt để đoán đúng trong hangman, tôi nghĩ đây là chiến lược tối ưu cho những ràng buộc.

Vì vậy, với từ điển bạn đã cung cấp, trước tiên nó sẽ đoán a chính xác.Sau đó, nó sẽ đoán r, cũng chính xác, sau đó b (không chính xác), sau đó c.

Vấn đề với móc treo nghịch đảo là bạn luôn đoán sai nếu bạn có thể đoán sai, nhưng điều đó hoàn hảo cho thuật toán này vì nó loại bỏ tập hợp lớn nhất trước. Như một ví dụ hơi có ý nghĩa hơn:

điển:

mar 
bar 
car 
fir 
wit 

Trong trường hợp này nó đoán r sai đầu tiên và là trái với chỉ wit. Nếu wit được thay thế trong từ điển bằng sir, thì sẽ đoán r chính xác rồi a không chính xác, loại bỏ tập hợp lớn hơn, rồi w hoặc f một cách ngẫu nhiên không chính xác, tiếp theo là từ cuối cùng chỉ với 1 lần đoán không chính xác.

Vì vậy, thuật toán này sẽ giành chiến thắng nếu có thể giành chiến thắng, mặc dù bạn phải thực sự chạy qua nó để xem chiến thắng có thắng hay không.