Giải bài Tháp Hanoi từ trạng thái ngẫu nhiên ban đầu

[kobebryant]

Ai cũng biết bài toán tháp Hanoi rồi, nhưng đó là bắt từ trạng thái tất cả các đĩa đều nằm ở 1 cột. Bây giờ mình muốn giải từ 1 trạng thái ban đầu bất kỳ (vẫn thoả mãn điều kiện là đĩa nhỏ phải nằm trên đĩa to), giải với số dịch chuyển là ít nhất. Ai biết thì giúp mình nhé. Thanks

[mr_invincible]

Khác gì nhau đâu bạn, chỉ thay số 1 bằng số bất kì :D

[kobebryant]

bạn vẫn ko hiểu ý của mình rồi. Trạn thái bất kỳ ở đây là các đĩa đều được xếp ngẫu nhiêu ở cả 3 cọc và vẫn thoả mãn đk đĩa nhỏ ở trên đĩa to. Vấn đề là với số di chuyển ít nhất đưa tất cả các đĩa về 1 cọc.

[mr_invincible]

Thế thì chắc không thực hiện được bởi vì ngay cả bài toán ban đầu mà quay lui thì đã tốn rất nhiều thời gian vì đòi hỏi quá nhiều bước chuyển. Do đó nếu các đĩa xếp bất kì mà phải thử mọi trường hợp thì có lẽ càng phức tạp do khi dùng quay lui thì phải duyệt mọi nhánh -> theo mình thì đa số trường hợp sẽ không đủ bộ nhớ. Nếu chỉ muốn biết số lần chuyển thì có lẽ nên suy nghĩ bằng toán học hoặc quy hoạch động, nhưng chắc cũng khó đấy
--> chịu :D :D

[kobebryant]

chán quá, thế chẳng bác nào giúp em à?

[mr_invincible]

Chắc mọi người cũng thấy không làm được :D :D

[tin.truc22]

Mình nghĩ chỉ là giải pháp đệ quy thôi. Muốn di chuyển 5 vòng từ tháp A sang B phải giải quyết bài toán di chuyển 4 vòng từ A->C rồi mới chuyển lại. Vì vậy cần dời tháp nào thì cứ thực hiện bài toán đó để dời đi. Nhưng đùa tiên là tìm cách để sắp các khối sao theo thứ tự từ thấp đến cao trước. Cách này có thể giải quyết bài toán nhưng mình nghĩ không là tối ưu.

[mr_invincible]

Cái chính là ít lần nhất nên trong trường hợp các vòng ở cả 3 tháp thì cần phải biết bắt đầu chuyển cái đầu tiên từ đâu đến đâu là tốn ít lần nhất

[bete]

Tui nghĩ như vầy:

Giả sử mình có n đĩa đánh số từ 1 (đĩa nhỏ nhứt) tới n (đĩa lớn nhứt)
Giả sử thêm mình có 3 cọc A, B, C và mình muốn chuyển các đĩa về cọc A

Mình viết 1 thủ tục DỜI(k,P): lấy từ đĩa 1 tới đĩa k (từ 3 cọc A,B,C), trộn lại thành 1 chồng và sắp ở cột P

Ý tuởng của thủ tục DỜI như sau:
Giả sử mình gọi DỜI(9,B) để dời đĩa 1 tới đĩa 9 (từ 3 cọc A,B,C) qua cọc B
Giả sử thêm là mình đang có đĩa 7,8 và 9 nằm sẵn ở cọc B; và đĩa 6 đang ở cọc C
Khi đó mình sẽ:
- gọi DỜI(5,A) để dời đĩa 1 tới đĩa 5 (từ 3 cọc A,B,C) qua cọc A; lúc này đĩa 6 đang nằm trên cùng của cọc C và đĩa 7 đang nằm trên cùng của cọc B
- dời đĩa 6 từ C sang B (đĩa 6 sẽ nằm ngay trên đĩa 7)
- gọi DỜI(5,B) để dời đĩa 1 tới đĩa 5 (từ 3 cọc A,B,C; thực chất là ở cọc C) qua cọc B

(Cách này hơi giống cách giải của bài toán nguyên thủy)

Để giải bài toán: mình gọi TRỘN(n,A)

Cách giải này có tối ưu hay không ?
=> cách giải của bài toán nguyên thủy có tối ưu hay không ?
Nếu có thì lập luận/chứng minh ra sao ?
=> thử áp dụng cho cách giải này !

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân