Tháp giải pháp Hà Nội tốt hơn O (2^n)?

Question

Có một giải pháp cho Towers Hà Nội có thời gian chạy là ít hơn O (2 ⁿ), nơi n là số đĩa để di chuyển? Giải pháp của tôi mất thời gian O (2 ⁿ).

Ngoài ra, giải pháp dưới đây là đệ quy. Chúng ta có thể sử dụng Lập trình động với khái niệm ghi nhớ để giải quyết điều này trong một thời gian ngắn hơn không?

public void towersOfHanoi(
     int num, 
     MyStack<Integer> from, 
     MyStack<Integer> to, 
     MyStack<Integer> spare 
) { 
    if (num == 1) { 
     int i = from.pop(); 
     to.push(i); 
     System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName()); 
     return; 
    } 
    towersOfHanoi(num - 1, from, spare, to); 
    towersOfHanoi(1, from, to, spare); 
    towersOfHanoi(num - 1, spare, to, from); 
} 

MyStack là một phiên bản mở rộng của Stack lớp trong Java có thêm một lĩnh vực name và accessor.

Ngoài ra, có bất kỳ biến thể nào của cùng một vấn đề không?

Answer 1

Vì việc giải quyết Tháp Hà Nội luôn mất 2^n - 1 bước ... không, bạn sẽ không tìm được thuật toán nhanh hơn, vì phải mất O (2^n) để in các bước, ít tính toán chúng hơn.

Answer 2

Tôi sẽ không chứng minh (như Stephen đã làm), nhưng tôi sẽ cố gắng giải thích bằng trực giác rằng 2^n-1 là min: Ở mọi trạng thái, chỉ có ba bước di chuyển cho đĩa. Hãy biểu diễn trạng thái hiện tại theo lệnh seq (1, 1, .., 1) sao cho số đầu tiên cho biết đĩa ổ đĩa lớn nhất là ở đâu và số cuối cùng cho biết đĩa nhỏ nhất ở đâu. (1, 1, .., 1) có nghĩa là tất cả các đĩa đều ở vị trí 1. Cũng từ (1, 1, ..1) chỉ có hai trạng thái giảm dần: (1, 1, ... 2) và (1, 1, .... 3). Từ (1, 1, ... 2) có ba trạng thái giảm dần:

1. Quay trở lại (1, 1, .. 1)
2. goto (1, 1, ..., 3)
3. goto (1, 1, ... 3, 2)

Nếu bạn tiếp tục, bạn sẽ nhận được đồ thị mà các nút là các trạng thái có thể và các cạnh (chuyển tiếp) là "di chuyển đĩa".

Bạn sẽ nhận được hình ảnh như hình bên dưới (nếu bạn tiếp tục, nó sẽ trông giống như hình tam giác và ở các đỉnh sẽ là (1, 1, ... 1), (2, 2, ..2), (3 , 3, ... 3)). Số bước thực sự là đường dẫn trong biểu đồ.

Nếu bạn đi dọc theo cạnh trên hình tam giác, số bước trong 2^n-1. Tất cả các đường dẫn khác có cùng chiều dài hoặc dài hơn.

Nếu bạn sử dụng chiến lược: Di chuyển tất cả các ổ đĩa trừ lớn nhất để đặt 3, sau đó di chuyển larges để đặt 2, và cuối cùng là di chuyển tất cả hình thức 3-2, công thức có thể được đặt ra trong những điều sau đây cách:

f (n) =
f (n -1) // di chuyển tất cả trừ lớn nhất 1-3
+ 1 // di chuyển lớn nhất 1-2
+ f (n -1) // di chuyển tất cả từ 3 đến 2
->
f (n) = 1+ 2 * f (n-1)

các giải pháp của phương trình tái cung cấp cho bạn số lượng các bước theo yêu cầu của chiến lược đó (mà sẽ xảy ra là số lượng tối thiểu các bước)

Answer 3

Giải pháp cho Tháp của Hà Nội không thể tách rời 2 ⁿ. Tuy nhiên, trong một giải pháp lập trình động, mỗi bài toán con chỉ được tính một lần, và sau đó vấn đề được giải quyết bằng cách kết hợp giải pháp subproblem đầu tiên, di chuyển đĩa hiện tại và giải pháp phụ đề thứ hai.

Vì vậy, có hai thành phần trong việc tạo ra mỗi giải pháp: phân bổ bộ nhớ cho giải pháp hiện tại, và sau đó điền vào bộ nhớ đó. Việc cấp phát bộ nhớ xấp xỉ độc lập với kích thước bộ nhớ được phân bổ và là thành phần đắt tiền. Bản sao bộ nhớ tuyến tính ở kích thước của bộ nhớ được sao chép, mặc dù nhanh, là hàm mũ trong n làm giải pháp cho các Towers.

Time = c * n + c * 2 ⁿ, trong đó c >> c . Tức là, nó bắt đầu tuyến tính và kết thúc theo cấp số mũ.

Link to article appearing in ACM's SIGCSE Inroads magazine (September 2012)

Answer 4

Tòa tháp tiêu chuẩn của vấn đề hanoi đề cập đến 3 chốt.

Tuy nhiên, nếu chúng ta có k-pegs, độ phức tạp thời gian sẽ là O (2^(n/(k-2))).

Tôi đã giải quyết vấn đề này với 4 chốt và 5 chốt và sự phức tạp thời gian dẫn đến là O (2^(n/2)) và O (2^(n/3)) tương ứng