Giải thuật tìm kiếm tốt nhất đầu tiên

1. Kỹ thuật tìm kiếm tốt nhất đầu tiên
Kỹ thuật tìm kiếm tốt nhất đầu tiên tìm lời giải có dùng tri thức về bài toán để hướng dẫn. Tri thức này hướng việc tìm kiếm về nút lời giải trong không gian bài toán.
Tại mỗi nút được xem xét, người ta sẽ quyết định việc tìm kiếm tiếp tục theo nhánh nào tin tưởng sẽ dẫn đến lời giải.
Trong các chương trình trí tuệ nhân tạo, kỹ thuật tìm kiếm tốt nhất đầu tiên sử dụng hàm đánh giá. Hàm này dùng các thông tin hiện tại về mức độ quan trọng của bài toán tại nút đó để gán giá trị cho nút này, gọi là trọng số của nút. Giá trị này được xem xét trong lúc tìm kiếm. Thông thường, nút có trọng số nhỏ (lớn) nhất sẽ được chọn trong quá trình tìm kiếm.
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


3. Giải thuật

bool result = false;
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))
{
n.Cost = n.Huerictis;
openList.Push(n);
BeforeOfNode(n, node);
}
}
openList.Sort(SortType.ASCENDING);//sắp xếp theo thứ tự giảm dần theo Cost từ đỉnh Stack
}

if (result)
{
DisplayResult();
}
else
{
NotFound();
}
4. 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ả

5. Ưu và nhược điểm của phương pháp tìm kiếm tốt nhất đầu tiên
Ưu điểm
– Phương pháp tìm kiếm tốt nhất đầu tiên tổ hợp các ưu điểm của phương pháp tìm kiếm rộng và tìm kiếm sâu.
– Ưu điểm chủ yếu của phương pháp tìm kiếm tốt nhất đầu tiên là dùng tri thức để dẫn dắt việc tìm kiếm. Tri thức này giúp người ta bắt đầu từ đâu là tốt nhất và cách tốt nhất để tiến hành tìm lời giải.
– Tìm kiếm tốt nhất đầu tiên tuân theo cách suy lý của một chuyên gia. Do đó có thể thấy rõ đường đi hơn tìm kiếm rộng và tìm kiếm sâu.
Nhược điểm
– Quá trình tìm kiếm có thể đi xa khỏi lời giải. Kỹ thuật này chỉ xét một phần của không gian và coi đó là phần hứa hẹn hơn cả.

  1. #1 by voicoi on Tháng Ba 27, 2012 - 22:39

    a ơi!a viết bằng ngôn ngữ gì vậy?có thể gửi code cho e qua mail dinhvui90@gmail.com dc ko?thank nhiu!!!

  2. #2 by Ngân on Tháng Chín 16, 2014 - 18:54

    anh ơi có thể gửi code qua mail cho em đc ko ạ,

  3. #3 by Ngân on Tháng Chín 16, 2014 - 18:55

    mail của em là ngan.bmn@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: