xin mời các cao thủ của DDTH [Archive]

View Full Version : xin mời các cao thủ của DDTH

echcoms

15-04-2005, 10:45

khử đệ quy bài toán tháp hà nôi.

bichduyen_nt

15-04-2005, 13:10

Thường thì hay xài stack để khử đệ quy, còn không thì mời bạn nghiên cứu môn trí tuệ nhân tạo, có bài toán tháp hà nội hết sức thú vị, he he, bảo đảm không có miếng đệ quy nào !!!

misty

15-04-2005, 13:22

khử đệ quy bài toán tháp hà nôi.

thầy giáo còn cho bài nào nữa không ;)

echcoms

15-04-2005, 17:05

Thường thì hay xài stack để khử đệ quy, còn không thì mời bạn nghiên cứu môn trí tuệ nhân tạo, có bài toán tháp hà nội hết sức thú vị, he he, bảo đảm không có miếng đệ quy nào !!!
đúng vậy bạn à trí tuệ nhân tạo thì mình không biết nhưng thuật giải đệ quy của bài này thì mình có rồi,dùng stack,mình muốn thử xem có cách nào hay hơn không.

thầy giáo còn cho bài nào nữa không ;)
sorry khong dam mua rìu qua mắt các bác em chỉ muốn nhờ các bác làm thử nhưng muốn gây sốc tí thôi.sorry.

bete

18-04-2005, 07:10

Kijuto Riddle

18-04-2005, 08:49

bete nói đúng lắm, thật ra thì tất cả con đường đều dẫn tới ... giải phóng miền Nam.
Đệ quy về hình thức hay dùng stack về nguyên lý là y hệt, khác nhau là cách thì dễ hiểu, dễ cài đặt, cách thì có tốc độ thực thi nhanh hơn một chút.

TrongThaiVN

19-04-2005, 10:42

Chào mọi người,

Giải bài toán Tháp Hà Nội không đệ qui LÀ CÓ THỰC (tôi đã giải bài này bằng nhiều cách). Dùng ngôn ngữ nào hay AI đều cũng vậy, chỉ có điều là phải thay đổi thuật giải (thay đổi cách suy nghĩ). Các bạn không tin à?!

- Dùng vòng lặp với một hàm mục tiêu.
- Nếu mục tiêu chưa đạt thì bước kế tiếp sẽ làm gì? (cũng vẫn là vòng lặp). Chỉ làm một bước duy nhất đó rồi trở lại vòng lặp để kiểm tra tiếp.

Số lần thực hiện vẫn là 2^n - 1, nhưng bằng vòng lặp chứ không phải đệ qui hay stack giống như phân tích của bạn bete.

Cái dở ở đây là mỗi lần lặp đều phải kiểm tra từ đầu tới cuối (cỡ n lần kiểm tra), nếu có sử dụng đệ qui hay stack thì sẽ giảm bớt sự kiểm tra (một lần kiểm tra mỗi bước).

Bài toán kinh điển này thì mọi sinh viên CNTT đều biết nhưng những các cách giải khác nhau thì chưa chắc ai cũng thử qua. Mời các bạn thử suy nghĩ tiếp!!

Thân ái,
Trong Thai

Nhân tiện, tôi xin đưa ra một số mở rộng của bài toán này (trước đây, thầy tôi đã cho trên lớp):
- Bài toán đang ở trạng thái giữa chừng, xây dựng thuật giải để đi tiếp (có thể dùng đệ qui hoặc không).
- Có 4 cột (2 cột trung gian).

echcoms

19-04-2005, 14:12

bạn à không phải là không dùng stack đâu.theo mình thì để khử đệ quy bài này thì có thể có nhiều cách nhưng có thể dùng cả vòng lặp và stack.nguyên lý của đệ quy là khi bạn gọi chương trình con cấp 0 thì nó sẽ sinh ra các chương trình con cấp 1,2.. và lưu lại các giá trị biến của lời gọi cấp 1 tương tụ vậy đến các lời gọi cấp n(khi gặp trường hợp neo)khi sử dụng đệ quy, các biến được lưu sau mỗi lần gọi đệ quy được lưu bằng stack mặc định của ngôn ngữ,vì thế sẽ tốn bộ nhớ.dùng stack thực ra cũng là làm theo ý tưởng của đệ quy nhưng như vậy tối thiểu được phần bộ nhớ trong chương trình.chắc chắn rằng đệ quy lưu các giá trị các biến bằng stack vì đệ quy chỉ có thể sử dụng được với những ngôn có kiểu stack.hình như portran là một ngôn ngữ không dùng được thì phải.

bichduyen_nt

19-04-2005, 20:10

Bạn bichduyen_nt cho tui thắc mắc 1 tí nghen: xài AI có thể giải bài tháp Hanoi thì không cần đệ qui một tí nào hết hay sao !? Vậy thì đáng nể thiệt ! Tui biết là nếu xài Prolog thì "có vẻ" như không xài đệ quy; nhưng thực chất thì Prolog đã cài đặt cơ chế quay lui tự động cho mình rồi => nếu nhìn sâu xuống thì vẫn phải đệ qui. Tui cũng có thấy 1 cái thread bài về heuristic trong AI cho bài tháp Hanoi => tui nghĩ là nếu có heuristic là có ước lượng & quay lui (xài heuristic để "hy vọng" tìm ra cách giải nhanh nhứt thôi -- chẳng qua là xếp hạng các khả năng theo 1 thứ tự ưu tiên nào đó rồi tiến hành thử & quay lui)

Gì chứ chuyện giải Tháp HN bằng AI mà ko sử dụng đệ quy thì Duyên đảm bảo mà, vì khi làm bài này nộp cho giáo viên mà có miếng đệ quy nào là bị 0 ngay, vì nó không còn đi theo hướng của AI nữa.
Duyên chỉ sử dụng 2 mảng để chứa các trạng thái của tháp, một mảng chứa các trạng thái đã đi, một mảng chứa các trạng thái có thể đi tiếp từ trạng thái đang xét, từ trạng thái của tháp đang xét, ta sẽ tìm được những trạng thái tiếp theo có thể đi được, từ đó mình sẽ loại ra dần những trạng thái đã đi rồi nhằm tránh đi những bước vòng vo, rồi chọn trạng thái có ước lượng theo mình là tốt nhất, dễ có khả năng tới đích nhất để đi, chỉ cần một vòng lặp while cho đến khi tới được trạng thái đích hay là không thể đi được nữa (nghĩa là các trạng thái tiếp theo đều đã được đi rồi!!) nói chung là vậy, Thuật toán rất hay, Duyên nghĩ nó khá là gần với suy nghĩ của con người khi chơi trò này, mà mục đích của AI là vậy mà, làm cho máy tính có suy nghĩ như người (mới gọi là trí tuệ nhân tạo chứ!!).Đương nhiên sử dụng mảng có cái hại của nó (khắc phục bằng danh sách liên kết thôi), và có thể đôi khi thuật toán sẽ bị thất bại, không tới được đích, đó cũng là chuyện thường tình, vì đây là trí tuệ nhân tạo, làm cho máy giống người, mà người thì có bao giờ là hoàn hảo đâu ....
Duyên chưa nghiên cứu Prolog, khi học môn AI cũng có nghe thầy nói là học môn này thì nên làm bẳng Prolog thì sẽ hiểu nhiều hơn, nhưng xét trình độ mình có hạn, hì hì ... Làm bằng C++ vậy !!!

bete

20-04-2005, 04:25

Thân gửi TrongThaiVN: hướng làm của bạn có vẻ rất gần với hướng AI của bichduyen_nt. Tuy nhiên tại mỗi bước bạn chỉ cần làm n kiểm tra: n lần thì không nhỏ rồi nhưng so với hướng của bichduyen_nt thì có lẽ nhỏ hơn.

Thân gửi bichduyen_nt: tui nghĩ nếu làm theo hướng này thì tại mỗi bước có lẽ phải kiểm tra hơi nhiều phải không: tại mỗi bước có thể có tới 3 lựa chọn để di chuyển đĩa kế tiếp: 3 lần kiểm tra thì không sao nhưng để biết mỗi trạng thái kế đã đi qua chưa thì tui đoán là cái mảng chứa tất cả trạng thái đã đi qua sẽ có kích thước không nhỏ đâu => tại mỗi bước chắc phải làm hơn O(n) và sẽ làm nhiều hơn 2^(n-1) bước !?!? Tuy nhiên mục tiêu của AI có lẽ là giải các vấn đề tổng quát => tìm ra cách giải là hay rồi !!!!

Tui cũng thấy có 1 cách giải bằng vòng lặp và tại mỗi bước cần O(n) lần kiểm tra: giả sử có 4 đĩa, mình sắp 3 cái cột theo vòng tròn => cần làm (2^n)-1 (sửa nhờ sự góp ý của bạn TrongThai) phép dịch chuyển. Giả sử thêm là mình gán chỉ số 0 cho đĩa nhỏ nhứt, 1 cho đĩa nhỏ nhì,...., (n-1) cho đĩa lớn nhứt => tại mỗi bước mình thử biên xuống: chỉ số của đĩa được dời, chiều dời (xuôi hay ngược chiều kim đồng hồ) và bước hiện tại (dưới dạng nhị phân):

-;o;-;o;-;o;-;o;-;o;-;o;-;o;- (bit 0 của bước hiện tại)
o;-;-;o;o;-;-;o;o;-;-;o;o;-;- (bit 1 của bước hiện tại)
o;o;o;-;-;-;-;o;o;o;o;-;-;-;- (bit 2 của bước hiện tại)
o;o;o;o;o;o;o;-;-;-;-;-;-;-;- (bit 3 của bước hiện tại)
0;1;0;2;0;1;0;3;0;1;0;2;0;1;0 (chỉ số của dĩa được dời <- chỉ số của bit đầu tiên khác 0)
+;-;+;+;+;-;+;-;+;-;+;+;+;-;+ (chiều dời <- tính chẵn/lẻ của n và của chỉ số của đĩa được dời)

(4 dòng cuối là bước hiện tại (viết dưới dạng nhị phân 4 bit): xoay 90 độ khi đọc. Ví dụ cột 1 là 0001, cột 2 là 0010,..., cột 15 là 1111)

=> từ đây mình có thể viết 1 vòng lặp từ 1 đến 2^(n-1) để dời đĩa

Nếu hướng đi này không giống với hướng của TrongThaiVN thì xin bạn post lên cách của bạn để tui được học hỏi thêm

************* Xin có vài thắc mắc về 2 bài toán mở rộng:

1) Bài toán đang ở trạng thái giữa chừng, xây dựng thuật giải để đi tiếp (có thể dùng đệ qui hoặc không): mình được phép lưu giữ dữ liệu gì tại mỗi bước !? Nếu muốn lưu giữ gì cũng được thì thuật toán vòng lặp của TrongThaiVN chính là 1 lời giải (tui đoán bạn xài thêm 1 mảng phụ hay cái gì đó). Còn nếu không lưu giữ thêm dữ liệu gì ngoài trạng thái của các đĩa (đĩa nào nằm ở cột nào và nằm ở chỗ nào (trên cùng, dưới cùng,.....)) thì đây là 1 bài toán cũng lý thú lắm

2) Có 4 cột (2 cột trung gian): tui đoán yêu cầu của bài toán là làm ít hơn 2^(n-1) bước !?!? Nếu không thì cứ việc bỏ qua 1 cột trung gian, chỉ xài 1 là giải được rồi. Nói chung là càng nhiều cột trung gian thì số bước càng ít đi !?!?!

(có gì sai sót xin các bạn chỉ giúp cho, cám ơn rất nhiều)

-thân

TrongThaiVN

21-04-2005, 15:18

Chào bạn bete: Tôi thấy bạn có sự nhầm lẫn một chút: số bước là (2^n) - 1 chứ không phải 2^(n-1).

Cách giải không đệ qui (và không dùng stack để khử đệ qui) chắc chắn phải đi đến kết quả chứ không phải "có thể đôi khi thuật toán sẽ bị thất bại" như bài của bạn bichduyen_nt (tôi cũng không chắc vì tôi không biết cách giải của bạn bichduyen_nt).

Cách giải của tôi tuân theo nguyên lý chứ không phải theo lý thuyết trò chơi.

Xin nhắc lại đôi chút về bài toán:
- Có 3 tháp (gọi tắt là cột) gọi là 1, 2 và 3.
- Có n đĩa: 1 đĩa nhỏ, n đĩa lớn.
- Mỗi lần di chuyển một đĩa.
- Không được chồng đĩa lớn hơn đè lên đĩa nhỏ.
Yêu cầu: tìm một thứ tự di chuyển các đĩa sao cho số lần di chuyển là ít nhất.
Với các đặc điểm trên thì người ta chứng minh được là cách tối ưu (duy nhất; có số lần di chuyển ít nhất) sẽ có 2^n - 1 bước di chuyển đĩa.

Thông thường đầu vào: A là cột 1, B là cột 2 và C là cột 3 (A, B và C là các biến), n đĩa từ lớn đến nhỏ đã được chồng tại cột 1 (cột A), cần chuyển n đĩa này từ cột 1 sang cột 3.

Nguyên lý di chuyển tối ưu: để chuyển n đĩa từ cột nguồn (A) sang cột đích (C) thì trước hết phải di chuyển n-1 đĩa sang cột trung gian (B), rồi chuyển đĩa n sang cột C, và cuối cùng chuyển n-1 đĩa từ cột B sang cột C.

Bản thân nguyên lý trên bao hàm ý nghĩa đệ qui hay truy hồi. Nhưng nó cũng cho thấy hướng giải quyết vấn đề ở mỗi một trạng thái.

Theo các bạn, trong cách giải đệ qui (hoặc dùng stack) thì cái gì lưu trạng thái hiện tại???

Xét đoạn chương trình kinh điển sau (Xin lỗi, tôi viết bằng mã giả Pascal):
1: procedure Dichuyen(n, A, B, C);
2: begin
3: if n = 1 then
4: { chuyển đĩa trên cùng từ cột A sang C }
5: else begin
6: Dichuyen(n-1, A, C, B);
7: Dichuyen(1, A, B, C);
8: Dichuyen(n-1, B, A, C);
9: end;
10: end;

Giả sử có 3 đĩa ở cột 1 (3,2,1)()(); sau khi di chuyển đĩa đầu tiên được (3,2)()(1) thì trạng thái của chương trình:

Stack:
Dichuyen(1, 1, 2, 3) - câu lệnh kế tiếp 7
Dichuyen(2, 1, 3, 2) - câu lệnh kế tiếp 7
Dichuyen(3, 1, 2, 3) - trở về chương trình chính

Chính là trạng thái stack của hệ thống và cấu trúc chương trình nắm giữ điều đó.

Cách giải của tôi liên quan đến "trạng thái hiện tại". Từ trạng thái hiện tại sẽ tìm cách chuyển một đĩa để sang trạng thái kế tiếp. Thuật giải của tôi phải sử dụng 3 mảng ứng với 3 cột (hoặc mảng hai chiều m[3][n]) để lưu trạng thái hiện tại. Còn ở cách giải đệ qui như thông thường thì không thể tiếp tục với đầu vào là một trạng thái giữa chừng.

Cách giải trên của bạn bete (theo bit nhị phân) cũng là một cách đúng, như việc xây dựng các mảng trên lại mở ra một bài toán mới và theo tôi bạn sẽ gặp trở ngại trong chính việc xây dựng các mảng đó.

Các bạn có tham khảo cách giải trong quyển "Giải một bài toán trên máy tính như thế nào" tập 1 của tác giả Hoàng Kiếm (trang 230) chưa? Ý tưởng của bạn bete khá giống với thuật toán này nhưng thuật toán này đã hoàn chỉnh và rõ ràng hơn cách của bạn bete.

Tôi cũng chưa xây dựng thuật giải (và nguyên lý) để giải trong trường hợp có 4 cột, nhưng theo tôi thì vấn đề này sẽ có nguyên lý tối ưu và có thể có nhiều hơn một cách giải tối ưu. Ví dụ: để chuyển 3 đĩa từ cột 1 sang cột 4 cần 5 bước và có 2 cách tối ưu:
(3,2,1)()()()
(3,2)(1)()()
(3)(1)(2)()
()(1)(2)(3)
()(1)()(3,2)
()()()(3,2,1)
hay
(3,2,1)()()()
(3,2)()(1)()
(3)(2)(1)()
()(2)(1)(3)
()()(1)(3,2)
()()()(3,2,1)
Tôi có thể sẽ trình bày thuật giải của tôi ở lần sau.
Thân chào,
Trong Thai

bete

21-04-2005, 15:35

Thân gửi TrongThaiVN:

"số bước là (2^n) - 1 chứ không phải 2^(n-1)."
=> cám ơn bạn đã chi ra chỗ sai này !!!

"Còn ở cách giải đệ qui như thông thường thì không thể tiếp tục với đầu vào là một trạng thái giữa chừng." => đồng ý với bạn ở chỗ này

Tui nghĩ cách giải AI không cho lời giải tối ưu (số lần di chuyển là ít nhứt); nhưng nếu bỏ qua ràng buộc về thời gian chạy và kích thước bộ nhớ thì nó luôn luôn tìm ra 1 cách giải. Hơn nữa, cách giải là tổng quát cho (hầu như !?) mọi bài toán về "tìm đích"

Còn cách giải theo bit nhị phân thì dựa trên nhận xét trên lời giải đệ qui cho bài toán n_đĩa_3_cột
=> đổi thành 4_cột hay hơn thì phải tìm lại cách giải lại từ đầu (mà chưa chắc đã đi được theo hướng này). Cách giải theo bit nhị phân này cần lưu giữ 1 biến đếm & số đĩa ban đầu là chẵn hay lẻ

-thân

bichduyen_nt

23-04-2005, 00:16

Uh, Duyên biết là AI có cái hạn của nó chứ, cái mảng lưu mấy trạng thái đã đi thường thì ít lắm, nên chỉ có thể áp dụng được cho khoảng mười mấy đĩa một cột thôi à, Duyên thấy trong lớp có đứa chạy luôn 64 đĩa vẫn chạy được mà nó thì nhất định không chịu cho coi source, keo thấy ghê luôn!!!
Còn cái chuyện so sánh với các trạng thái đã đi thì Duyên nghĩ cũng không đến nỗi tệ lắm, hi hi, vì chỉ cần trong 2 trạng thái mà có một điểm khác nhau là out liền, với lại Duyên quản lý mấy trạng thái bằng cấu trúc struct nên cũng dễ làm lắm!!!!
Duyên nghĩ thuật toán của bạn TrongThaiVN không được uyển chuyển cho lắm, khi bạn cần thay đổi một chút về dữ liệu bài toán thì bạn sẽ phải làm lại thuật toán từ đầu, phê lắm bạn ơi, hi hi, nhưng nó cũng là một ý tưởng khá hay!!!

hoangtungoc

09-06-2007, 17:21

ai co code bài toán tháp hà nội ko vậy, mình đang cần để tham khảo, các bạn có thể gửi cho mình được ko, email mình là: hoangtungoc16@yahoo.com.vn