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

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

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

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