Giải thuật tìm kiếm theo chiều sâu

1. Kỹ thuật tìm kiếm sâu

Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích. Tại mỗi nút có luật trong tài, chẳng hạn, “đi theo nút cực trái”, hướng dẫn việc tìm. Nếu không đi tiếp được, gọi là đến ngõ cụt, hệ thống quay lại một mức trên đồ thị và tìm theo hướng khác, chẳng hạn, đến nút “sát nút cực trái”. Hành động này gọi là quay lui.
Thuật toán tìm kiếm theo chiều sâu được hình dung như việc khảo sát một cây bắt đầu từ gốc đi theo mọi cành có thể được, khi gặp cành cụt thì quay lại xét cành chưa đi qua.
– Ở bước tổng quát, giả sử đang xét đỉnh i, khi đó các đỉnh kề với i có các trường hợp:
+ Nếu tồn tại đỉnh j kề i chưa được xét thì xét đỉnh này (nó trở thành đỉnh đã xét) và bắt đầu từ đó tiếp tục quá trình tìm kiếm với đỉnh này..
+ Nếu với mọi đỉnh kề với i đều đã được xét thì i coi như duyệt xong và quay trở lại tìm kiếm từ đỉnh mà từ đó ta đi đến được i.

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:
Sử dụng hai danh sách hoạt động theo nguyên tắc LIFO (Stack)  OPENLIST và CLOSELIST



openList.Push(n0);
while (!openList.IsEmpty())
{
node = openList.Pop();
if (node.Equals(n*))
{
result = true;
break;
}

closeList.Push(node);
for (n in Tn(Node))
{
if (!openList.InList(n) && !closeList.InList(n))
{
openList.Push(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 sâu
Ưu điểm:
– Nếu bài toán có lời giải, phương pháp tìm kiếm sâu bảo đảm tìm ra lời giải.
– Kỹ thuật tìm kiếm sâu tập trung vào đích, con người cảm thấy hài lòng khi các câu hỏi tập trung vào vấn đề chính.
– Do cách tìm của kỹ thuật này, nếu lời giải ở rất sâu, kỹ thuật tìm sâu sẽ tiết kiệm thời gian.
Nhược điểm:
– Tìm sâu khai thác không gian bài toán để tìm lời giải theo thuật toán đơn giản một cách cứng nhắc. Trong quá trình tìm nó không có thông tin nào hổ trợ để phát hiện lời giải. Nếu chọn nút ban đầu không thích hợp có thể không dẫn đến đích của bài toán.
– Không phù hợp với không gian bài toán lớn, kỹ thuật tìm kiếm sâu có thể không đến lời giải trong khoảng thời gian vừa phải.

  1. #1 by Thanh Luan on Tháng Sáu 8, 2010 - 14:55

    Help me! Khi nao phuong phap tim kiem leo doi va phuong phap tim kiem sau cho ket ket qua giong nhau. Cho vi du lun:d

  2. #2 by trương tiến thành on Tháng Chín 11, 2010 - 21:50

    bạn có thể viết code sang C được không.

  3. #3 by Long on Tháng Mười Một 28, 2010 - 23:20

    bạn có thể Viết CODE sang C dc ko ,gửi code cả chương trinh vào mail lonelylonely23@ymail.com nhá

  4. #5 by Nguyễn Mạnh Dũng on Tháng Mười Hai 22, 2010 - 23:50

    Hình như theo mình cái cây của cậu duyệt chưa đúng thì phải đường đi phải là 1 đến 2 đến 5 đến 10 đến 11 mới là đúng chứ vì tìm kiếm chiều sâu là từ trái sang phải mà

  5. #6 by Mục Đồng on Tháng Mười Hai 23, 2010 - 09:40

    Chúng ta dùng danh sách LIFO (Last In First Out) nên số 4 vào sau lại chọn ra trước, do đó kết quả sẽ đi theo như vậy🙂

    Thân !

  6. #7 by Ngo QUang Toan on Tháng Hai 22, 2011 - 00:04

    a oi, tim kiem theo chieu sau co phai la dang day thuat vet can ko?

  7. #8 by Mục Đồng on Tháng Hai 22, 2011 - 07:50

    Giải thuật vét cạn thường được dùng để tìm các lời giải tối ưu, thường so sánh với một phương án mẫu để có được đáp án tốt nhất. Còn duyệt sâu mục đích của nó chỉ tìm ra lời giải, chứ không phải lời giải tối ưu (duyệt sâu chỉ rơi vào vét cạn khi mà lời giải trải rộng :)).

    Thân !

  8. #9 by phu on Tháng Hai 28, 2011 - 10:25

    bạn vui lòng gửi code của C cho mình với nha.thanhks

  9. #10 by dung on Tháng Tư 25, 2011 - 10:19

    gởi code bằng C mình với..thank

  10. #11 by thanh on Tháng Tư 26, 2011 - 14:13

    anh ơi.anh có thể gửi bài bằng C cho em được ko ạ? mail của em là demonking_137@yahoo.com

  11. #12 by Thạch on Tháng Tư 30, 2011 - 23:30

    thanks all
    i see that what i don’t undesand every bad

  12. #13 by minhchau on Tháng Năm 19, 2011 - 13:01

    Bạn ơi.mình cũng đang làm bài tập về phần này.Bạn có thể gửi code C cho mình được không.Nếu không được thì bạ hướng dẫn qua cho mình cách viết chương trình được không?

  13. #14 by vidia on Tháng Bảy 20, 2011 - 15:29

    ban co the share cai function BeforeOfNode(n, node) ko .

  14. #15 by Còi on Tháng Mười Hai 28, 2011 - 12:50

    Tớ hỏi một chút là khi mình đẩy các phần tử vào Stack thì có theo thứ tự nào hay không ví dụ như là theo thứ tự từ lớn đến bé hoặc là theo danh sách cạnh vì tớ nhìn bạn đẩy vào không theo 1 quy tắc nào cả.

  15. #16 by Mục Đồng on Tháng Mười Hai 28, 2011 - 13:48

    Vì nguyên lý thì tìm kiếm rộng và sâu đều là các phương pháp tìm kiềm “mù”, tức là không có qui tắc nào chọn phần tử để đưa vào Stack cả bạn ạ.
    Ở đây mình chọn phần tử theo thứ tự mà phần tử đó được tạo ra trong mảng của đồ thị.

    Thân.

  16. #17 by Còi on Tháng Mười Hai 29, 2011 - 00:43

    Thế tớ hỏi nhé khi duyệt 9 các phần tử kề với 9 sao không lấy là 4,3,10 hoặc 3,4,10 mà lấy là 4,10,3 ?

  17. #18 by Mục Đồng on Tháng Mười Hai 29, 2011 - 08:41

    Câu hỏi rất hay🙂

    Thật ra thứ tự mà bạn thấy 4,3,10 hay 4,10,3 trong bài làm của mình không phải là thứ tự theo chỉ số.
    Trong ứng dụng này, khi mình tạo một đồ thị, ban đầu sẽ tạo các đỉnh (các chỉ số sẽ tăng dần 1-2-3..) nhưng để tính đỉnh kề ta phải phụ thuộc vào việc nối cung. Do vậy, việc nối 1 cung từ đỉnh A-B sẽ tạo ra thứ tự của các đỉnh kề, đó là lý do vì sao thứ tự các đỉnh kề của 9 trên đồ thị là 4,10,3, điều này hoàn toàn là do thứ tự khi mình nối cung các đỉnh “liên quan” với đỉnh 9

    Thân.

  18. #19 by Coi on Tháng Mười Hai 30, 2011 - 16:10

    Uh.Tớ thấy duyệt theo danh sách cạnh cũng được nó dễ nhìn và không bị nhầm lẫn.

  19. #20 by Còi on Tháng Mười Hai 31, 2011 - 14:53

    Bạn có thể nói rõ hơn một chút được không?t vẫn chưa rõ lắm hihi.

  20. #21 by cnttv on Tháng Ba 16, 2014 - 07:42

    hãy làm 1 bài hướng dẫn về thuật toán theo chiều rộng nữa nhé

  21. #23 by thanh on Tháng Sáu 16, 2014 - 15:09

    có code c ko cho em xin vào mail nxthanh.it@gmail.com

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: