Phân biệt giải thuật tìm kiếm sâu và sâu dần...


Diễn đàn chia sẻ kiến thức, kinh nghiệm về IT và cuộc sống!
 
Trang ChínhGalleryTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
Top posters
Sakura (1124)
 
hotboy (705)
 
Già Làng (373)
 
con_ca_nho90 (289)
 
that_true (154)
 
theanhkkt (143)
 
phamay (137)
 
lovelonelyman (134)
 
o0ovioletstaro0o (128)
 
stevenhung (122)
 
Âm - Dương lịch
Clock
Logo
11TH02 Pro!
Liên kết
Tin tức 60s
Tin công nghệ
Thời sự 24h
Game Moblie

Share | 
 

 Phân biệt giải thuật tìm kiếm sâu và sâu dần...

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Già Làng


avatar

Thú CƯng :
Nam Libra

Số bài viết : 373
Điểm : 2200708
Được cảm ơn : 53
Ngày sinh : 20/10/1987
Tham gia ngày : 16/03/2010
Tuổi : 30
Đến từ : Bình Dương
Ngề nghiệp : Sinh Viên
Chăm ngôn : Cơm Cha - Áo Mẹ!

Bài gửiTiêu đề: Phân biệt giải thuật tìm kiếm sâu và sâu dần...   15/10/2010, 09:49

I. GIẢI THUẬT TÌM KIẾM 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

Code:
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ẽ
[You must be registered and logged in to see this link.]
Đỉ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[You must be registered and logged in to see this link.]
Kết quả đường đi là:
[You must be registered and logged in to see this link.]
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.
II. GIẢI THUẬT TÌM KIẾM SÂU DẦN:
1. Kỹ thuật tìm kiếm sâu dần Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giưói hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2,…đến độ sâu max nào đó.
Kỹ thuật tìm kiếm sâu dần thường được thực hiện khi cây tìm kiếm chứa nhánh vô hạn, và nếu sử dụng tìm kiếm theo độ sâu ta có thể mắc kẹt ở một nhánh nào đó (thuật toán không dừng) và không tìm ra nghiệm
2. Giải thuật
Thuật toán tìm kiếm sâu dần sử dụng thuật toán tìm kiếm sâu hạn chế như thủ tục con. Đó là thủ tục tìm kiếm theo chiều sâu nhưng chỉ tới độ sâu d nào đó rồi quay lên.

Code:
bool result = false;
openList.Push(n0);
deepOfNode(no, 0);//độ sâu của đỉnh xuất phát là 0
while (!openList.IsEmpty())
{
node = openList.Pop();
if (node.Equals(n*))
{
result = true;
break;
}closeList.Push(node);
int deep = deepOfNode[node];
if (deep < limitedDeep)
{
for (n in Tn(node))
{
if (!openList.InList(n) && !closeList.InList(n))
{
openList.Push(n);
BeforeOfNode(n, node);
deepOfNode.Add(n, deep + 1);//độ sâu của đỉnh n
}
}
}
}if (result)
{
DisplayResult();
}
else
{
NotFound();
}
3. Ví dụ

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

[You must be registered and logged in to see this link.]
Đỉnh xuất phát là (1), đỉnh đích là (11), độ sâu giới hạn là 3



Các bước chi tiết thực hiện giải thuật
[You must be registered and logged in to see this link.]
Kết quả
[You must be registered and logged in to see this link.]

_________________________________________________
Khách viếng thăm đọc rồi thì thanks đi chứ!!
Về Đầu Trang Go down
Xem lý lịch thành viên http://itworld.4rumer.com
hotboy


avatar

Thú CƯng :
Nam Aries

Số bài viết : 705
Điểm : 1043
Được cảm ơn : 9
Ngày sinh : 21/03/1990
Tham gia ngày : 13/05/2010
Tuổi : 27
Đến từ : BDU

Bài gửiTiêu đề: Re: Phân biệt giải thuật tìm kiếm sâu và sâu dần...   15/10/2010, 12:20

vất vả cho ông già quá Very Happy
Về Đầu Trang Go down
Xem lý lịch thành viên
mailoc




Nam Leo

Số bài viết : 1
Điểm : 1
Được cảm ơn : 0
Ngày sinh : 12/08/1994
Tham gia ngày : 20/12/2014
Tuổi : 23
Đến từ : thái bình

Bài gửiTiêu đề: Re: Phân biệt giải thuật tìm kiếm sâu và sâu dần...   20/12/2014, 15:12

c ơi cho  t hỏi nếu hết chiều sâu 3 mà không tói đích thì xét nút gốc mới rùi tìm lại như trên ak
Về Đầu Trang Go down
Xem lý lịch thành viên
Sponsored content




Bài gửiTiêu đề: Re: Phân biệt giải thuật tìm kiếm sâu và sâu dần...   

Về Đầu Trang Go down
 

Phân biệt giải thuật tìm kiếm sâu và sâu dần...

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

 Similar topics

-
» 0912976289 - Vải địa kỹ thuật, giấy dầu xây dựng, rọ đá, matit chèn khe, lưới B40 mạ kẽm bọc nhựa PVC
» Bán đất KD mặt đường Lê Viết Thuật TP Vinh
» Bán nhà khu dân cư Thuận Giao Bình Dương
» Cần sang nhượng Quầy thuốc, tại Kiều Mai, xã Phú Diễn, huyện Từ Liêm, Hà Nội.
» Cần chuyển nhượng nhà thuốc GPP, tại số 29 Đặng Tiến Đông, quận Đống Đa, Hà Nội.

Permissions in this forum:Bạn không có quyền trả lời bài viết
IT World! :: HỌC TẬP :: HỌC KỲ V :: Cơ Sở Trí Tuệ - Trí Tuệ Nhân Tạo-