Bài toán Hanota

Trong sắp xếp trộn và dựng cây nhị phân, chúng ta phân rã bài toán ban đầu thành hai bài toán con, mỗi bài toán có kích thước bằng một nửa bài toán ban đầu. Tuy nhiên, đối với bài toán Hanota, chúng ta áp dụng một chiến lược phân rã khác.

Question

Cho ba cột ký hiệu là A, B và C. Ban đầu, cột A có \(n\) đĩa được xếp chồng lên nhau theo thứ tự kích thước tăng dần từ trên xuống dưới. Nhiệm vụ của chúng ta là di chuyển \(n\) đĩa này sang cột C trong khi vẫn duy trì thứ tự ban đầu của chúng (như thể hiện ở hình bên dưới). Các quy tắc sau đây phải được tuân thủ khi di chuyển đĩa.

1. Chỉ có thể lấy đĩa từ trên cùng của một cột và đặt lên trên cùng của một cột khác.
2. Mỗi lần chỉ được di chuyển một đĩa.
3. Đĩa nhỏ hơn luôn phải nằm trên đĩa lớn hơn.

Chúng ta ký hiệu bài toán Hanota quy mô \(i\) là \(f(i)\). Ví dụ, \(f(3)\) đại diện cho việc di chuyển \(3\) đĩa từ A sang C.

Xem xét các trường hợp cơ bản

Như được thể hiện trong hình dưới đây, đối với bài toán \(f(1)\), khi chỉ có một đĩa, chúng ta có thể di chuyển trực tiếp đĩa đó từ A sang C.

<1><2>

Như thể hiện trong hình dưới đây, đối với bài toán \(f(2)\), khi có hai đĩa, vì chúng ta luôn phải giữ đĩa nhỏ hơn ở trên đĩa lớn hơn, chúng ta cần sử dụng cột B để hỗ trợ việc di chuyển.

1. Đầu tiên, di chuyển đĩa nhỏ hơn từ A sang B.
2. Sau đó di chuyển đĩa lớn hơn từ A sang C.
3. Cuối cùng, di chuyển đĩa nhỏ hơn từ B sang C.

<1><2><3><4>

Quá trình giải bài toán \(f(2)\) có thể được tóm tắt là: di chuyển hai đĩa từ A sang C với sự trợ giúp của B. Ở đây, C được gọi là cột mục tiêu (target pillar), và B được gọi là cột đệm (buffer pillar).

Phân rã bài toán con

Đối với bài toán \(f(3)\), khi có ba đĩa, tình huống trở nên phức tạp hơn một chút.

Vì chúng ta đã biết lời giải cho \(f(1)\) và \(f(2)\), chúng ta có thể tư duy theo góc nhìn chia để trị, coi hai đĩa trên cùng của cột A là một thể thống nhất, và thực hiện các bước như hình dưới đây. Việc này sẽ di chuyển thành công ba đĩa từ A sang C.

1. Chọn B làm cột mục tiêu và C làm cột đệm, di chuyển hai đĩa từ A sang B.
2. Di chuyển đĩa còn lại từ A trực tiếp sang C.
3. Chọn C làm cột mục tiêu và A làm cột đệm, di chuyển hai đĩa từ B sang C.

<1><2><3><4>

Về bản chất, chúng ta chia bài toán \(f(3)\) thành hai bài toán con \(f(2)\) và một bài toán con \(f(1)\). Bằng cách giải quyết lần lượt ba bài toán con này, bài toán ban đầu sẽ được giải quyết. Điều này cho thấy các bài toán con là độc lập và lời giải của chúng có thể được hợp nhất.

Từ đây, chúng ta có thể tóm tắt chiến lược chia để trị giải bài toán Hanota như hình dưới đây: chia bài toán ban đầu \(f(n)\) thành hai bài toán con \(f(n-1)\) và một bài toán con \(f(1)\), rồi giải quyết ba bài toán con này theo thứ tự sau.

1. Di chuyển \(n-1\) đĩa từ A sang B với sự trợ giúp của C.
2. Di chuyển đĩa \(1\) còn lại trực tiếp từ A sang C.
3. Di chuyển \(n-1\) đĩa từ B sang C với sự trợ giúp của A.

Đối với hai bài toán con \(f(n-1)\) này, chúng ta có thể phân chia đệ quy theo cùng một cách cho đến khi đạt được bài toán con nhỏ nhất \(f(1)\). Lời giải cho \(f(1)\) đã được biết trước và chỉ yêu cầu một thao tác di chuyển duy nhất.

Triển khai mã nguồn

Trong mã nguồn, chúng ta khai báo một hàm đệ quy dfs(i, src, buf, tar) có nhiệm vụ di chuyển \(i\) đĩa trên cùng từ cột nguồn src sang cột mục tiêu tar với sự trợ giúp của cột đệm buf:

[file]{hanota}-[class]{}-[func]{solve_hanota}

Như hình minh họa bên dưới, bài toán Hanota tạo ra một cây đệ quy (recursion tree) có chiều cao \(n\), với mỗi nút đại diện cho một bài toán con tương ứng với một lần gọi hàm dfs(), do đó độ phức tạp thời gian là \(O(2^n)\) và độ phức tạp không gian là \(O(n)\).

Quote

Bài toán Hanota có nguồn gốc từ một truyền thuyết cổ xưa. Trong một ngôi đền ở Ấn Độ cổ đại, các nhà sư có ba cột kim cương cao và \(64\) chiếc đĩa vàng có kích thước khác nhau. Các nhà sư liên tục di chuyển những chiếc đĩa này, và tin rằng khi chiếc đĩa cuối cùng được đặt đúng vị trí, thế giới sẽ kết thúc.

Tuy nhiên, ngay cả khi các nhà sư di chuyển một đĩa mỗi giây, sẽ mất khoảng \(2^{64} \approx 1.84×10^{19}\) giây, tức là khoảng \(585\) tỷ năm, vượt xa ước tính hiện tại về tuổi của vũ trụ. Vì vậy, nếu truyền thuyết này là thật, chúng ta không cần phải lo lắng về ngày tận thế.