Giải thuật Leo đồi

1. Kỹ thuật tìm kiếm leo đồi
Tìm kiếm leo đồi là tìm kiếm theo độ sâu được hướng dẫn bởi hàm đánh giá. Song khác với tìm kiếm theo độ sâu, khi phát triển một đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh con của u, đỉnh có hứa hẹn nhiều nhất để phát triển, đỉnh này được xác định bởi hàm đánh giá.
2. Giải thuật
Input:
    Đồ thị G = (V,E), đỉnh xuất phát n0.
    Hàm đánh giá h(n) đối với mỗi đỉnh n.
    Tập đỉnh đích DICH
Output:
    Đường đi từ đỉnh n0 đến DICH

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

                closeList.Push(node);
                Stack list = new Stack();
                for (n in Tn(node))
                {
                    if (!openList.InList(n) && !closeList.InList(n))
                    {
                        n.Cost = node.Cost + Edge(node, n).Value + n.Huerictis;
                        BeforeOfNode(n, node);
                        list.Push(n);
                    }
                }
                list.Sort(SortType.DESCENDING);//sắp xếp các đỉnh phát triển tiếp theo theo thứ tự hàm đánh giá
                while (!list.IsEmpty())
                {
                    openList.Push(list.Pop());//chuyển các đỉnh tiếp theo vào danh sách OPEN theo thứ tự hàm đánh giá
                }
            }
            if (result)
            {
                DisplayResult();
            }
            else
            {
                NotFound();
            }

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

Chi phí 24




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