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ả.

Mã nguồn tham khảo tại đây