Scaling một, thuật toán bitwise lặp đi lặp lại để giải quyết vấn Towers Hà Nội sử dụng đĩa X và tháp Y

Question

Tôi thích các thuật toán được đề cập trong câu hỏi này: "Làm thế nào để làm việc này Weird Towers của Giải pháp Hà Nội" How does this work? Weird Towers of Hanoi Solution

Có bất kỳ cách nào để mở rộng giải pháp không đệ quy của Tháp Hà Nội để sử dụng các đĩa X và tháp Y, với các tháp được biểu diễn như là ngăn xếp?

Answer 1

Một giải pháp lặp đi lặp lại cho tháp của Hà Nội với Y = 3 Towers và đĩa X và có thể được tìm thấy trên Wikipedia:

Đối với một số chẵn các đĩa:

• làm cho di chuyển hợp pháp giữa các chốt A và B
• thực hiện di chuyển hợp pháp giữa các điểm A và C
• thực hiện di chuyển hợp pháp giữa các điểm B và C lặp lại cho đến khi hoàn thành

Đối với một số lẻ của đĩa:

• làm cho di chuyển pháp lý giữa chốt A và C
• làm cho di chuyển pháp lý giữa chốt A và B
• làm cho di chuyển pháp lý giữa chốt B và C lặp lại cho đến khi hoàn thành

Trong mỗi trường hợp, tổng cộng 2^X-1 được thực hiện. Số lượng di chuyển với thuật toán này chỉ là minimal for Y=3.

Giải pháp này bỏ qua các tháp khác, vì vậy nó hoạt động với bất kỳ Y> = 3 và bất kỳ X.

Mặc dù phiên bản ba-peg có một giải pháp đệ quy đơn giản như được nêu trên, tối ưu giải pháp cho vấn đề Tháp Hà Nội với bốn chốt (gọi là câu đố của Reve), hãy để một mình thêm chốt, vẫn là một vấn đề mở. Điều này là một ví dụ tốt về cách thức đơn giản, vấn đề có thể giải quyết có thể được thực hiện đáng kể khó khăn hơn bằng cách hơi nới lỏng một trong những vấn đề ràng buộc.

Trích dẫn từ Wikipedia.