Trí tuệ nhân tạo, bài toán tháp HN

[bichduyen_nt]

hi, Duyên đang ko hiểu về thuật giải của bài này cho lắm, làm sao để máy có thể quyết định được bước tiếp theo là sẽ di chuyển đĩa nào , Duyên không hiểu hàm heuristic áp dụng vào bài tháp HN 3 đĩa ra sao hết, bạn nào có tài liệu về vấn đề này không ?, Duyên đang hỏi về trí tuệ nhân tạo nha, không phải là bài tháp HN bằng đệ quy đâu !!!!

[bichduyen_nt]

Uh, Duyên học ở Tự Nhiên, học thầy Bắc, hi hi, có khi nào chung thầy luôn hông hé ?
Duyên dùng AKT đó, khốn khổ là cái hàm h, chơi ơi, chịu không nổi, Duyên tính h theo kiểu sự sai biệt của hiện tại so với đích, khổ nỗi là hổng ra, he he, Bạn làm ơn chia sẻ cái hàm h của bạn cho Duyên đi, Duyên vẫn không nghĩ ra được làm sao tính trước được khả năng còn bao nhiêu bước nữa để đạt tới đích ? .
Mà bạn sử dụng chung một thuật giải cho các loại bài 3, 4, ..., 6 dĩa luôn hả, siêu vậy, kính nể !!!! Chắc phải gọi là sư phụ quá!!!!

[thailehuy]

Để mình về lục lại tài liệu, hình như mình có giải thuật cho n dĩa, nhưng không có code. Theo mình nhớ là dùng đệ quy, số bước thực hiện là 2^n thì phải

[Rikku]

To copcop: Anh cho vào quote sẽ tab được. Anh học ở ĐHKHTN-ĐHQGHN à??

[bichduyen_nt]

copcop à, thiệt tình thì BDuyên cũng cố gắng đọc hàm heuristic của bạn nhưng mà chắc không đủ thông minh nên rốt cuộc là hổng hiểu gì hết, biến n làm chức năng gì vậy bạn, Duyên không đoán ra được, chắc là tại vì Duyên không hiểu bạn lưu trữ cái tháp của bạn như thế nào, hi hi.
Duyên thì tính hàm heuristic như vậy nè, Duyên chỉ xét cọc đích thôi, tức là cọc mà các dĩa của tháp phải để vô. ví dụ cụ thể:
bắt đầu: có 3 cọc là A,B,C và các đĩa 1,2,3 nằm thứ tự như sau, 0 có nghĩa là tại vị trí đó không có đĩa:
A**B**C
1**0**0
2**0**0
3**0**0
kết thúc phải ra như vầy:
A**B**C
0**0**1
0**0**2
0**0**3
vậy thì Hàm h của Duyên được tính dựa vào các bước phải làm để cột thứ 3 của bước đang làm có thể = với cột thứ 3 của đích. h = số đĩa phải lấy ra + số đĩa phải bỏ vào
VD: trường hợp này:
A**B**C
0**0**0
0**0**1
0**2**3
ta thấy là muốn đạt được đến đích thì phải lấy đĩa 1 ra, rồi mới bỏ đĩa 2, rồi bỏ đĩa 1 vô, vậy tổng cộng là ta phải bỏ vô 2 đĩa. vây h= 1 + 2 = 3.
Ta sẽ chọn bước đi nào mà có h nhỏ hơn.
Tuy nhiên đến đây Duyên lại gặp một trở ngại là có trường hợp cả hai bước khác nhau nhưng lại có h bằng nhau, vấn đề là ta sẽ phải chọn bước nào để thuật giải có thể tốt hơn?
VD 2 trường hơp sau có h bằng nhau:
----TH1:
A**B**C
0**0**0
0**0**0
3**2**1 ---> có h = 1+3=4
----TH2:
A**B**C
0**0**0
1**0**0
3**0**2 ----> cũng có h = 4
hoặc là
A**B**C
0**0**0
0**0**1
0**0**3 có h = 3
và
A**B**C
0**0**0
2**0**0
3**1**0 có h = 3
Có bạn nào biết cách giải quyết chỗ này không?
Cấu trúc dữ liệu của Duyên như sau:
struct Cọc
{
int số_dĩa; // số dĩa có trong cọc đó
int dĩa[3];//dĩa[i]=j nghĩa là vị trí i có dĩa số j ở đây cho là mỗi cọc có 3 dĩa. Ví dụ ta có cột A có các đĩa từ trên xuống là 1,2,3 thì được lưu như sau dĩa[0]=3,dĩa[1]=2 và dĩa[2]=1
}
struct Thap // lưu trữ tháp HN
{
Cọc C[3]; //ba cọc A,B,C
}
struct BướcDi//lưu trạng thái của tháp tại mỗi bước di chuyển một đĩa
{
Tháp T;
int h; // giá trị ước lượng hàm heuristic của bước đi này
}

[echcoms]

mình hôm qua cũng vừa nhận bài tập đệ qui này, chưa nghiên cứu được cái gì cả,bạn nào có thể nói rõ hơn cho mình cái giải thuật AKT được ko?

[bichduyen_nt]

Nếu đã là đệ quy thì không là AKT, rốt cuộc bạn muốn hỏi cái nào?

[echcoms]

bài của mình là đệ quy,vậy bạn cứ chỉ giúp cai AKT nó là cái gì cho mình nhé,nó có tốt hơn đệ quy ko?

[bichduyen_nt]

echcoms à, Nếu bạn muốn hỏi về AKT thì nó chính là cái Duyên đã trình bày ở trên á, còn thuật giai A* chính là cái vấn đề mà Duyên đặt ra ở cuối bài vì Duyên thiệt ra cũng không hiểu nhiều lắm về A* !!! Đệ quy chạy tốt hơn nhiều, nhưng học AKT cũng có cái thú vị riêng của nó !!!

[echcoms]

ok. vậy các bạn có ai có tài liệu gì hay về cái giải thuật đệ quy này không?nếu có thì gửi mail cho mình hoặc post link cũng đươc.cám ơn

[bichduyen_nt]

Hình như Duyên nhớ là trong sách Pascal của Quách Tuấn Ngọc có đề cập đến nó và đương nhiên là bằng ngôn ngư Pascal.
Sau đây là một vài link Duyên search được, chỉ mới đọc lướt qua nhưng vẫn hy vọng se giúp được bạn, nhất là link thứ 2, khá là rõ ràng, chúc thành công vơi đệ quy, và vẫn mong bạn sẽ tìm hiểu về AKT để thấy sự khác biệt giữa thuật toán và thuật giải !!!
http://www.qiksearch.com/cpp/hanoi.htm
http://max.cs.kzoo.edu/AP/Java/cs210/Handouts/hanoi.combined

[echcoms]

cam on ban nhiều.chúc bạn mọi điều tốt lành

[ssass]

Thầy Bắc giảng hay wá xá , hay bà cố lun .

[tinhthl]

Tháp HN đủ loại, liên hệ tui để biết thêm chi tiết... nick yahoo cũng dc.

[deptraicungchan]

Bạn BDuyen ,mình cũng đang tim hiêu về "Tháp HN AKT" nhưng coi bộ không hề đơn giản tí nào hết,nếu co thể hãy zúp mình với deptraicungchan@gmail.com

[fanglightning]

Bạn BDuyen ,mình cũng đang tim hiêu về "Tháp HN AKT" nhưng coi bộ không hề đơn giản tí nào hết,nếu co thể hãy zúp mình với deptraicungchan@gmail.com

Sau đúng 1 năm tham gia ddth, bài viết đầu tiên là đào mộ...