Bài viết sưu tầm

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

7.2. Giải thuật.

Input:

          Đồ thị G = (V,E), đỉnh xuất phát n₀.

          Hàm đánh giá h(n) đối với mỗi đỉnh n.

          Tập đỉnh đích DICH

Output:

          Đường đi từ đỉnh n₀ đến DICH

Procedure HLC; {Hill Climbing Search}

begin

          Push(MO,n₀);

          while MO <> null do

          begin

                   i = Pop(MO);

                   if T(i) Ç DICH <> null then

                   begin                   

                             L:= null;

for  j Î T(i) do

                                      if j chưa xét then

                                                đưa j vào danh sách L

                             sắp xếp L theo thứ tự hàm đánh giá;

                             chuyển danh sách L vào đầu danh sách MO;

          end;

          write(‘Khong co loi giai’);
end;

7.3. Nhận xét.

Phương pháp tìm kiếm leo đồi chú trọng tìm hướng đi dễ dẫn đến trạng thái đích nhất. Cách đó được đưa ra nhằm làm giảm công sức tìm kiếm. Thuật toán tìm kiếm leo đồi thực chất là thuật toán tìm kiếm theo chiều sâu, song tại mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đich nhất để phát triển trước. Vấn đề quan trọng là biết khai thác kheo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhnah quá trình tìm kiếm. Thông thường ta gán mỗi trạng thái của bài toán với một số đo (hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó. Điều đó có nghĩa là nếu trạng thái hiện thời là u thì trạng thái v sẽ được phát triển tiếp theo nếu v kề với u và hàm đanh giá của v đạt giá trị max (hoặc min).

Tuy nhiên phương pháp này không được cải thiện so với các phương pháp khác trong một số trường hợp sau:

• Cực trị địa phương: nút đang xét tốt hơn các nút lân cận, nhưng đó không phải là phương án tốt nhất trong toàn thể, ví vậy có thể phải quay lui về nút trước để đi theo hướng khác. Giải pháp này đòi hỏi ghi nhớ lại nhiều đường đi.
• Cao nguyên bằng phẳng: Các giá trị của các phương án như nhau, không xác định được ngay hướng nào là tốt hơn trong vùng lân cận.