Giải thuật Leo đồi

 

1. Kỹ thuật tìm kiếm leo đồi
Tìm kiếm leo đồi là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo độ sâu, khi phát triển một đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh con của u, đỉnh có hứa hẹn nhiều nhất để phát triển, đỉnh này được xác định bởi hàm đánh giá.
2. Giải thuật
Input:
Đồ thị G = (V,E), đỉnh xuất phát n0.
Hàm đánh giá h(n) đối với mỗi đỉnh n.
Tập đỉnh đích DICH
Output:
Đường đi từ đỉnh n0 đến DICH


bool result = false;
openList.Push(n0);
while (!openList.IsEmpty())
{
node = openList.Pop();
if (node.Equals(n*))
{
result = true;
break;
}
closeList.Push(node);
Stack list = new Stack();
for (n in Tn(node))
{
if (!openList.InList(n) && !closeList.InList(n))
{
n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
BeforeOfNode(n, node);
list.Push(n);
}
}
list.Sort(SortType.DESCENDING);//sắp xếp các đỉnh phát triển tiếp theo theo thứ tự hàm đánh giá
while (!list.IsEmpty())
{
openList.Push(list.Pop());//chuyển các đỉnh tiếp theo vào danh sách OPEN theo thứ tự hàm đánh giá
}
}
if (result)
{
DisplayResult();
}
else
{
NotFound();
}

 

3. Ví dụ
Cho đồ thị như hình vẽ
Với giá trị Hueristic của mỗi đỉnh như sau

H(1) = 1  H(2) = 3  H(3) = 5   H(4) = 6  H(5) = 4
H(6) = 1  H(7) = 2  H(8) = 3   H(9) = 1  H(10) = 6
Đỉnh xuất phát là (1), đỉnh đích là (10)

Các bước chi tiết thực hiện giải thuật

Kết quả



Chi phí 24

  1. #1 by trung on Tháng Ba 8, 2010 - 23:03

    ban oi cho toi hoi
    toi dang lam bai tap lon ve thuat toan leo doi nhung minh cai dat tren java nhung toi khong biet cai ham danh gia h(n).toi dinh lay khoang cach giua 2 dinh lam h(n) co duoc khong>? hay fai cho nguoi chay chuong trinh nhap vao ham h(n)?

    Mong som nhan duoc fan hoi cua ban
    day la nick chat cua toi mong ban giup do: yahoo: phamhuytrung_k6a

  2. #2 by mucdong06 on Tháng Ba 9, 2010 - 06:57

    Hàm đánh giá này thường là những đánh giá mang tính kinh nghiệm, do đó trong trường hợp của bạn nên để cho người run chương trình cung cấp
    Thân !

  3. #3 by trung on Tháng Ba 9, 2010 - 23:56

    cam on ban da tra loi.
    cho toi hoi ngoai le 1 chut
    cai hinh do thi ma ban demo chuong trinh tren chay tren nen VB a? hay java hay C#? toi lam mai fan do hoa ma khong lam duoc, cai fan khi nhan nut tao diem va tu sinh ten diem tu 1,2,3…. o trong hinh tron nhu cua ban nhung khong duoc vay mong ban chi jup duoc khong?
    toi lam trong moi truong java.
    mong ban bot chut thoi gian tra loi. neu ranh ban cho toi xin nick chat de hoi ban nhieu hon. toi hoi kem ve phan nay va khong biet fai doc sach j de tot hon, doc nhiu tai lieu chi noi so wa.
    cam on ban!
    mong som nhan duoc phan hoi
    phamhuytrung_k6a@yahoo.com

  4. #4 by trung on Tháng Ba 10, 2010 - 00:00

    neu tao ham danh gia giua 2 diem nhu cua ban thi fai tao the nao?

  5. #5 by mucdong06 on Tháng Ba 10, 2010 - 08:27

    Về phần demo trên, mình làm bằng C#, nếu bạn cần thì gửi email cho minh, mình có thể share full code và phân tích 1 số lớp cơ bản trong đó để bạn tham khảo thêm, hiện tại mình đang bận dự án nên cũng không có nhiều thời gian support cho bạn được.
    Việc tạo hàm đánh giá, trong bản demo trên, mình cho nó trở thành một thuộc tính của đỉnh, có giá trị số thôi

    Thân !

    • #6 by quockiet on Tháng Mười 21, 2011 - 21:04

      bạn ơi mình cũng đang làm đồ án môn trí tuệ nhân tạo về bài toán 8 con hậu với giải thuật leo đồi, mình không hiểu lắm, bạn có thể share full code cho mình được không và file hướng dẫn, cảm ơn bạn trước

    • #7 by Phùng Phương Thảo on Tháng Hai 25, 2013 - 23:01

      a ơi? e đang làm bài thực tập môm trí tuệ nhân tạo về bài toán 8 con số với giải thuật leo đồi, tố nhất đầu tiên và beam.đọc phần hướng dẫn của a e vẫn chưa hiêu rõ lắm.a có thể full code cho e và gợi ý giúp e cách làm bài này được không a.e cảm ơn a. mong nhận được phản hồi của a sớm

  6. #8 by trung on Tháng Ba 10, 2010 - 11:48

    cam on ban toi da gui mail cho ban mong som nhan duoc su tro giup tu ban
    cam on ban rat nhieu!
    than!

  7. #9 by ha anh on Tháng Ba 15, 2010 - 01:21

    chao ban!
    toi co bai tap su dung thuat toan leo doi ngau nhien viet code cho bai toan xep 8 con hau, toi k biet tu vi tri ban dau di chuyen ngau nhien 1 con hau thi phai lam the nao? mong duoc ban giup do

  8. #10 by mucdong06 on Tháng Ba 15, 2010 - 08:22

    Đối với mấy giải thuật tìm kiếm, bạn phải chuyển bài toán về không gian trạng thái trước đã.
    Với bài toán 8 hậu thì cách xếp 1 quân hậu sao cho thỏa yêu cầu được xem như là một trạng thái (1 đỉnh, nút), các trạng thái sắp xếp hết 8 quân hậu trên một bàn cờ thỏa yêu cầu được xem là các trạng thái đích. Từ một trạng thái có n quân hậu, ta sắp xếp thêm được 1 quân hậu nữa thành trạng thái có n+1 quân hậu thì giữa 2 trạng thái này có 1 cung nối.
    Dựa vào kinh nghiệm, ta đặt các hàm đánh giá cho từng trạng thái.
    Như vậy bài toán giờ trở thành bài toán tìm kiếm trên miền đồ thị rồi

    Thân !

  9. #11 by phan code tren C3 cua thuat toan tren on Tháng Năm 23, 2010 - 21:42

    minh dang lam bai tap lon mon nay chu de ve tim kiem thuat toan sau dan.minh chua hieu gi ca.mong ban co the gui share full code va huong dan minh 1 so lop co ban.minh dung ngon ngu C#.monh ban som gui cho minh.
    Thanks!

  10. #12 by superpeople on Tháng Mười 6, 2010 - 18:34

    anh oi cho em hỏi: Thuật toan tim kiem leo doi dung de tim duong di ngan nhat khác voi thuat toan leo doi dùng để tìm đối tuong tốt nhất o điểm nào?

    • #13 by mucdong06 on Tháng Mười 8, 2010 - 10:12

      Vấn đề của bạn chính là chuyển bài toán tìm đường đi ngắn nhất và đối tượng tốt nhất về bài toán không gian trạng thái mà thôi, các thuật toán tìm kiếm dùng để tìm ra trạng thái theo mong muốn của mình
      Thân !

  11. #14 by trang_89 on Tháng Mười 30, 2010 - 09:05

    chao ban!
    minh dang can bai nay, ban co the share code full cua bai nay duoc ko ah?
    cam on ban!
    email cua minh: xuantrang89101@gmail.com

  12. #15 by anhdaoxutuyet on Tháng Mười Một 20, 2010 - 14:57

    anh ơi em dang làm bài tập về tìm kiếm leo đồi.thế Hill climber with sidestep khác giải thuật tìm kiếm leo đồi trên ở điểm nao hả anh.
    Anh phân tich giúp em được không ah?
    em cam ơn

  13. #16 by hoanganh on Tháng Mười Hai 20, 2010 - 23:54

    Ban co the send cho minh toan bo doan code cua thuat toan nay k?cam on ban
    email cua minh: hoang_anh_cao

  14. #17 by duong on Tháng Ba 24, 2011 - 19:52

    a oi…
    e dang lam do an ve cay khung :
    Ap dung mot thuat toan metaheurristic giai bai toan cay khung voi chi phi lo trinh nho nhat?
    e ap dung thuat toan leo doi dc k?
    a co the cho e xin y tuong va code ve bai nay dc k?

  15. #18 by duong on Tháng Ba 24, 2011 - 19:55

    a gui wa mali dum e dc k,
    van_duong1124@yahoo.com
    thank a !

  16. #19 by hung on Tháng Tư 5, 2011 - 10:55

    Bạn có bài tập hay quá. Bạn có thể gửi cho mình bài tập theo demo ở trên k? mình cũng đang tìm học c# nhưng vẫn chưa bít được nhìu. Mong bạn giúp đỡ.
    Thanks!
    gmail của mình: hnnguyenvanhung8@gmail.com.
    một lần nữa xin cảm ơn bạn.

  17. #20 by hoang.149 on Tháng Tư 5, 2011 - 19:42

    bạn có thể giải thích giùm giá trị Hueristic của mỗi đỉnh dược tính thế nào không?vì sao chi phí là 24?mong sớm nhận dc câu trả lời của bạn!

  18. #21 by Mục Đồng on Tháng Tư 6, 2011 - 14:48

    Đây là phần giới thiệu về hàm đánh giá trong entry Tìm kiếm tốt nhất đầu tiên. bạn đọc tham khảo xem

    2. Hàm đánh giá
    Trong nhiều vấn đề, ta có thể sử dụng kinh nghiệm, tri thức của chúng ta về vấn đề đó để đánh giá các trạng thái của vấn đề.
    Với mỗi trạng thái u, ta sẽ xác dịnh một giá trị số h(u), số này đánh giá “sự gần đích” của trạng thái u. Hàm h(u) được gọi là hàm đánh giá.
    Phương pháp tìm kiếm kinh nghiệm là phương pháp tìm kiếm có sử dụng đến hàm đánh giá. Trong quá trình tìm kiếm, tại mỗi bước ta sẽ chọn trạng thái kế tiếp là trạng thái có nhiều hứa hẹn dẫn tới đích nhiều nhất.
    Quá trình tìm kiếm trong không gian trạng thái có sử dụng hàm đánh giá bao gồm các bước cơ bản sau:
    Biểu diễn thích hợp các trạng thái và các toán tử chuyển trạng thái
    Xây dựng hàm đánh giá
    Thiết kế chiến lược chọn trạng thái ở mỗi bước

  19. #22 by anhquoc286 on Tháng Tư 26, 2011 - 09:44

    Bạn ơi gửi cho mình với mail:thanhuongquoc@gmail.com
    thank

  20. #23 by hoangdo@gmail.com on Tháng Tư 28, 2011 - 19:29

    bài của bạn làm thế cái cây để tìm đường đi có thể làm cho người dùng tự thiết kế ko mà như thế thì làm thế nào.

    bạn gửi tớ sin bài trên với
    mail: hoangdo@gmail.com

  21. #24 by hoangdo@gmail.com on Tháng Tư 28, 2011 - 21:11

    bài của bạn làm thế cái cây để tìm đường đi có thể làm cho người dùng tự thiết kế ko mà như thế thì làm thế nào.

    bạn gửi tớ sin bài trên với
    mail: hoangdo89@gmail.com

  22. #25 by Hạnh on Tháng Mười Hai 5, 2011 - 22:27

    Bạn cho mình xin code của bài với.
    Mail của mình: nhoc.ecstasy@yahoo.com.vn
    Thanks!

  23. #26 by dinhvui on Tháng Hai 29, 2012 - 01:40

    bạn cho mình xin code bài này với.nếu có thể bạn gửi cho mình code của tìm kiếm sâu,rộng,sâu lặp,leo đồi và tốt nhất đầu tiên nhé.mail của mình là dinhvui90@gmail.com
    thanks!!

  24. #27 by minmin on Tháng Ba 8, 2012 - 19:35

    Chao anh.Anh oi giup em voi em dang phai cai dat thuat toan leo doi(don gian) bang ngon ngu C(trituenhantao).anh co code anh giup em voi gmail cua em duchoang1208@gmail.com

  25. #28 by lynguyensqlserver on Tháng Ba 14, 2012 - 09:02

    bạn ơi bạn có thể send cho mình full code về giải thuật leo đồi được không.thank s bạn

  26. #29 by HuyenTera on Tháng Tư 1, 2013 - 21:23

    bạn ơi có thể cho mình xin bản share full code và demo của bài trên được k? mail của mình: dothihuyentrang92@gmail.com

  27. #30 by Hung on Tháng Tư 11, 2013 - 14:43

    minh cung doc giai thuat leo doi o day ban viet ctrinh cho bai toan 8 con hau theo minh biet bai toan nay duoc viet bang rat nhieu giai thuat khac nua vd viet bang de qui chang han… ban co the share full ctrinh cho minh tham khao duoc khong? thank ban!

  28. #31 by Hung on Tháng Tư 11, 2013 - 14:44

    mail cua minh: hungtb123456@gmail.com
    cam on nhieu!

  29. #32 by Cuong on Tháng Mười 9, 2013 - 19:02

    em đang cần làm một ví dụ đơn giản về thuật toán leo đồi này,a có ví dụ nào thì share e với email của e là

    smil30ns4d@gmail.com,cảm ơn ạ

  30. #33 by Hung on Tháng Ba 10, 2014 - 07:54

    a ơi, có thể share code cho em ko, gmail của em: phamchihung92@gmail.com. Em xin cảm ơn

  31. #34 by Mục Đồng on Tháng Ba 10, 2014 - 22:16

    Hi,

    Lâu nay bận quá, không check blog được.
    Link download đây nhé các bạn:

    https://www.dropbox.com/s/xqj8wx70nlw27jk/AiA.rar

  32. #35 by Thúy Vân on Tháng Mười 22, 2014 - 14:54

    Bạn ơi cho mình xin code của Hill Climbing được ko bạn
    vanthuythuyvan@gmail.com
    Thank bạn nhiều

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: