Thuật toán leo đồi ví dụ đơn giản

Question

Tôi hơi bối rối với thuật toán Hill Climbing. Tôi muốn "chạy" thuật toán cho đến khi tôi tìm thấy giải pháp đầu tiên trong cây đó ("a" là ban đầu và h và k là trạng thái cuối cùng) và nó nói rằng các số gần các trạng thái là giá trị heuristic. Dưới đây là các cây:

Câu hỏi của tôi: tôi đang cố gắng để chạy đồi leo trên cây, vì vậy chúng ta bắt đầu ok a-> f-> g và sau đó kết thúc gì ?? (không có kết quả), nhưng tôi đọc rằng leo đồi không thể quay trở lại và thực hiện một sự lựa chọn mới (ví dụ j hoặc e)? Thê nay đung không ? Nếu tôi có thể quay lại thì làm cách nào? tôi có nghĩa là nơi chúng tôi thay đổi ví dụ lựa chọn ban đầu của chúng tôi, chúng tôi chọn e thay vì g hoặc j thay vì f

Xin lỗi nếu câu hỏi của tôi quá đơn giản.

Answer 1

Leo núi không đảm bảo việc bị kẹt trong một minima/cực đại địa phương. Tuy nhiên, chỉ có hình thức tinh khiết nhất của leo đồi không cho phép bạn quay trở lại.

Riff đơn giản trên leo đồi sẽ tránh được vấn đề minima địa phương (với chi phí nhiều thời gian và bộ nhớ) là tìm kiếm tabu, nơi bạn nhớ kết quả xấu trước đó và cố ý tránh chúng.

Answer 2

Cách thông thường để tránh bị kẹt ở mức tối đa địa phương với Hill Climbing là sử dụng khởi động lại ngẫu nhiên. Trong ví dụ của bạn nếu G là một cực đại cục bộ, thuật toán sẽ dừng lại ở đó và sau đó chọn một nút ngẫu nhiên khác để khởi động lại từ đó. Vì vậy, nếu J hoặc C được chọn (hoặc có thể là A, B, hoặc D), bạn sẽ tìm thấy cực đại toàn cầu trong H hoặc K. Rửa sạch và lặp lại đủ lần và bạn sẽ tìm thấy cực đại toàn cầu hoặc một cái gì đó gần; tùy thuộc vào giới hạn thời gian/tài nguyên và không gian vấn đề.

Lưu ý rằng Tìm kiếm địa phương như Hill Climbing chưa hoàn thành và không thể đảm bảo tìm được giá trị cực đại toàn cầu. Lợi ích, tất nhiên, là nó đòi hỏi một phần nhỏ của các nguồn lực. Trong thực tế và áp dụng cho các vấn đề đúng, đó là một giải pháp rất hiệu quả.

Answer 3

một trong những vấn đề với leo đồi đang gặp khó khăn tại địa phương min232 & đây là những gì sẽ xảy ra khi bạn đạt F. Một phiên bản cải tiến của leo đồi (mà thực sự được sử dụng thực tế) là để khởi động lại toàn bộ quá trình bằng cách chọn một nút ngẫu nhiên trong cây tìm kiếm & một lần nữa tiếp tục tìm kiếm một giải pháp tối ưu. Nếu một lần nữa bạn gặp khó khăn ở một số minima địa phương, bạn phải khởi động lại với một số nút ngẫu nhiên khác. Nói chung có giới hạn về số không. thời gian bạn có thể làm lại quy trình tìm kiếm giải pháp tối ưu này. Sau khi bạn đạt đến giới hạn này, bạn chọn ít nhất trong số tất cả các minimas địa phương bạn đã đạt được trong quá trình. Mặc dù nó vẫn chưa hoàn thành nhưng điều này có cơ hội tốt hơn để tìm ra giải pháp tối ưu toàn cầu.

Answer 4

Bạn có thể thử sử dụng kỹ thuật được gọi là simulated annealing để ngăn tìm kiếm của bạn bị kẹt ở mức tối thiểu địa phương. Về cơ bản, trong việc ủ mô phỏng, có một tham số T kiểm soát khả năng của bạn để chuyển sang trạng thái lân cận tối ưu. Nếu số T cao, bạn có nhiều khả năng thực hiện chuyển động tối ưu phụ tới một quốc gia láng giềng và do đó có thể thoát khỏi mức tối thiểu địa phương khi bị kẹt ở đó, mà bạn sẽ không nếu bạn sử dụng leo đồi bình thường.

Answer 5

Thực tế trong Hill Climbing bạn thường không quay lại, vì bạn không theo dõi trạng thái (tìm kiếm cục bộ) và bạn sẽ di chuyển ra khỏi cực đại. Cả backtracking hoặc Tabu Search đều giúp trả lời câu hỏi: câu lệnh cũ chỉ di chuyển bạn ra khỏi một cực đại cục bộ và sau đó giữ bạn khỏi xem lại cùng một cực đại cục bộ. Không giúp bạn đạt được mức tối đa toàn cầu.- Tyson Oct 16 '12 at 22:59

"nơi bạn nhớ kết quả xấu trước đó và cố ý tránh chúng" Tôi không thể đồng ý, bạn đánh dấu là điều cấm kỵ cũng là giải pháp tốt, nhưng Bạn không muốn theo cùng một con đường lần nữa. -

Answer 6

Dưới đây là giải pháp:

A -> F, với chi phí F ít nhất có thể -> G với chi phí 3 nhưng không có con đường.

Khởi động lại từ chi phí thấp nhất có thể ngoài G, E là E vì đã được chèn vào hàng đợi/xếp hàng ưu tiên hoặc bất kỳ cấu trúc dữ liệu nào bạn sử dụng.

Như vậy E -> tôi nhưng tôi có chi phí cao hơn so với E như vậy, bạn đang bị mắc kẹt: S

Bắt đầu lại từ tối thiểu chi phí khác ngoài FE & G, do đó chúng tôi chọn J vì J có chi phí thấp hơn so với B với sự khác biệt của 2 tức là J = 8 B = 10

J-> K với chi phí 0 do đó K là mục tiêu

LƯU Ý: các biến thể đề xuất của đồi leo núi để chọn một điểm ngẫu nhiên, nhưng chọn ít nhất chi phí khác so với các nút đã truy cập là tốt hơn so với chọn ngẫu nhiên.

LƯU Ý KHÁC: là khi nút E không truy cập tôi vì tôi có giá trị cao hơn E, thuật toán đã chèn nó vào cấu trúc dữ liệu, do đó chọn chi phí thấp nhất so với số đã truy cập sẽ tạo đường dẫn mới từ tôi bởi vì tôi chưa bao giờ đến thăm và do đó nó có giá trị thấp hơn J, đây là con đường duy nhất mà tôi đã bỏ qua.

Answer 7

con đường theo leo lên đồi tinh khiết sẽ a-> J -> k nếu bạn mở rộng dành cho trẻ em từ trái sang phải, nếu bạn mở rộng chúng từ phải sang trái sau đó bạn sẽ nhận được trong này địa phương cực tiểu A - > F -> G, nhưng nhìn chung chúng tôi mở rộng từ trái sang phải.