Giải thuật tìm kiếm theo chiều rộng

1. Kỹ thuật tìm kiếm rộng
Kỹ thuật tìm kiếm rông là tìm kiếm trên tất cả các nút của một mức trong không gian bài toán trước khi chuyển sang các nút của mức tiếp theo.
Kỹ thuật tìm kiếm rộng bắt đầu từ mức thứ nhất của không gian bài toán, theo hướng dẫn của luật trọng tài, chẳng hạn “đi từ trái sang phải”. Nếu không thấy lời giải tại mức này, nó chuyển xuống mức sau để tiếp tục … đến khi định vị được lời giải nếu có.

2. Giải thuật
Input:
Cây/Đồ thị G = (V,E) với đỉnh gốc là n0 (trạng thái đầu)
Tập đích Goals
Output:
Một đường đi p từ n0 đến một đỉnh n* in Goals
Method:
Để thực hiện giải thuật này ta sử dụng hai danh sách hoạt động theo nguyên tắc FIFO (queue)  OPENLIST và CLOSELIST


bool result = false;

openList.Append(n0);


while (!openList.IsEmpty())
{
node = openList.Take();

if (node.Equals(n*))//là node đích
{
result = true;
break;
}

closeList.Append(node);
for (n in Tn(Node))
{
if (!openList.InList(n) && !closeList.InList(n))
{
openList.Append(n);
BeforeOfNode(n, node);//node trước của n là node trong quá trình tìm đường đến đích
}
}
}

if (result)
{
DisplayResult();
}
else
{
NotFound();
}
}

3. Ví dụ


Cho đồ thị như hình vẽ

Đỉnh xuất phát là (1), đỉnh đích là (11)
Các bước chi tiết thực hiện giải thuật



Kết quả đường đi là:



4. Ưu và nhược điểm của phương pháp tìm kiếm rộng
Ưu điểm
– Kỹ thuật tìm kiếm rộng là kỹ thuật vét cạn không gian trạng thái bài toán vì vậy sẽ tìm được lời giải nếu có.
– Đường đi tìm được đi qua ít đỉnh nhất.

Nhược điểm
– Tìm kiếm lời giải theo thuật toán đã định trước, do vậy tìm kiếm một cách máy móc; khi không có thông tin hổ trợ cho quá trình tìm kiếm, không nhận ra ngay lời giải.
– Không phù hợp với không gian bài oán kích thước lớn. Đối với loại bài toán này, phương pháp tìm rộng đối mặt với các nhu cầu:
+ Cần nhiều bộ nhớ theo số nút cần lưu trữ.
+ Cần nhiều công sức xử lý các nút, nhất là khi các nhánh cây dài, số nút tăng.

+ Dễ thực hiện các thao tác không thích hợp, thừa, đưa đến việc tăng đáng kể số nút phải xử lý.
– Không hiệu qủa nếu lời giải ở sâu. Phương pháp này không phù hợp cho trường hợp có nhiều đường dẫn đến kết quả nhưng đều sâu.
– Giao tiếp với người dùng không thân thiện. Do duyệt qua tất cả các nút, việc tìm kiếm không tập trung vào một chủ đề.


  1. #1 by http://7pop.net/ on Tháng Ba 15, 2010 - 15:42

    Thanks bạn, mình đang cần cái nì ^^

  2. #2 by cuong on Tháng Tư 14, 2010 - 22:53

    thanhk ban nhieu nha

  3. #3 by cuong on Tháng Tư 14, 2010 - 22:59

    e co mot bai toan nhu vay mong cac bac gop y.
    cho n khoi kich thuoc Ei,mau Ci(cac khoi co the cung mau,cung kich thuoc) dung phuong phap tim kiem theo chieu rong de xep cac khoi thanh mot thap khoi theo thu tu kich thuoc tang dan,va hai khoi canh nhau khong cung mau

  4. #4 by cuong on Tháng Tư 14, 2010 - 22:59

    viet bang ngon ngu c

  5. #5 by đoàn on Tháng Mười Hai 13, 2010 - 22:03

    Mục Đồng ơi! bạn có thể gửi full code vs bản exe C# cho mình đc ko?
    cả 2 thuật toán tìm kiếm theo chiều xâu và chiều rộng nhé, mail của mình: doanithp@gmail.com
    tks!

  6. #6 by Zeor on Tháng Năm 9, 2011 - 15:27

    Bạn gửi mình full code C# với bản exe với nha.
    Mail của mình pzeor1001@gmail.com
    cảm ơn bạn trước ^^

  7. #7 by hoang hoa on Tháng Chín 24, 2011 - 01:43

    Bạn gửi mình full code C# với bản exe với nha.
    Mail của mình haiau91@gmail.com
    cảm ơn bạn trước ^^

  8. #8 by hoang hoa on Tháng Chín 24, 2011 - 01:44

    Bạn gửi mình full code C# với bản exe với nha.
    Mail của mình haiau91@gmail.com
    thanks!

  9. #9 by tocngan on Tháng Mười Hai 9, 2011 - 02:44

    chang hieu gj het

  10. #10 by suphamtink34 on Tháng Một 2, 2012 - 17:45

    bạn ơi >??tại sao lại có kết luận đường di như zay ??

  11. #11 by Anh Tuấn on Tháng Hai 3, 2012 - 10:29

    Chào bạn!

    Bạn gửi cho mình xin code C# thuật toán tìm kiếm theo chiều rồng và theo chiều sâu với nhé!

    Cảm ơn bạn rất nhiều!

    Email của mình là: tintuc624@gmail.com

  12. #12 by thanhbaton on Tháng Ba 4, 2012 - 21:00

    minh can co de tubor c tim duong di theo chieu rong gui wa yahoo phanbathanh92 nhe ban oi ai co giup minh nhe

  13. #13 by thuynga on Tháng Ba 14, 2012 - 16:03

    bạn ơi gửi cho t code với, mình đang cần gấp, thank you so much.
    Email của mình là ngadktin3b@gmail.com

  14. #14 by Kenly Wall on Tháng Năm 21, 2012 - 21:09

    Ban oi gui giup minh nha! Thanks
    Email : luutuong90@gmail.com

  15. #15 by n on Tháng Năm 28, 2012 - 22:16

    bạn có thể nó rõ hơn không?

  16. #16 by HoangVinh on Tháng Mười Hai 2, 2013 - 08:23

    bạn giúp mình nha..mình sắp thuyết trình về cái này.
    nguyenhoangvinh.vh@gmail.com

  17. #17 by trangmin on Tháng Mười Hai 2, 2013 - 21:47

    bạn ơi bạn gửi t xin code với nha. Thanks.

  18. #18 by cnttv on Tháng Ba 15, 2014 - 21:53

    Cảm ơn bạn. mình đang có bài tập báo cáo về phần này

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: