Sự khác biệt giữa tính đơn điệu và sự chấp nhận của một heuristic là gì?

Question

Tôi đang đọc qua sách giáo khoa AI của mình và tôi tò mò về sự khác biệt giữa tính đơn điệu và khả năng chấp nhận của chẩn đoán (tôi biết chúng không loại trừ lẫn nhau).

Theo như tôi có thể nói, một heuristic được chấp nhận đơn giản có nghĩa là bạn được đảm bảo để có được con đường ngắn nhất để một giải pháp nếu có tồn tại.

Điều tôi đang gặp phải là khái niệm về tính chất đơn điệu. Ai đó có thể mô tả điều này với tôi theo cách tôi có thể hiểu không?

Tương tự, làm cách nào tôi có thể xác định liệu một phỏng đoán được cho là đơn điệu/có thể chấp nhận? Một trong những ví dụ được đưa ra trong cuốn sách là Câu đố trượt 8 mảnh. Một heuristic tôi đang xem xét là # trong số gạch ra khỏi chỗ, và trực giác tôi có thể nói rằng tôi biết rằng nó là chấp nhận được nhưng tôi không có cách chính thức để hiển thị nếu nó được chấp nhận/đơn điệu.

Answer 1

Russel and Norvig, 2ed page 99 nói:

Giải pháp thứ hai là để đảm bảo rằng con đường tối ưu cho bất kỳ trạng thái lặp đi lặp lại luôn là người đầu tiên đi theo - như là trường hợp với tìm kiếm thống nhất chi phí. Tài sản này nắm giữ nếu chúng tôi áp đặt thêm yêu cầu trên h(n), cụ thể là yêu cầu của tính nhất quán (còn được gọi là đơn điệu).

Khi bạn nói về chức năng, đơn điệu có nghĩa là hàm tăng hoặc giảm, nhưng không phải cả hai. Nói cách khác, thứ tự trong phạm vi vẫn giữ nguyên trên toàn miền. Vì lý do này trong vấn đề của bạn, giải pháp duy trì con đường ngắn nhất bất kể bạn bắt đầu bước nào.

Các admissibility tài sản của một heuristic, có nghĩa là chi phí để đạt được mục tiêu không bao giờ được đánh giá quá cao (ví dụ đó là lạc quan) (trang 98).

Answer 2

Học đơn điệu là khi tác nhân không thể tìm hiểu bất kỳ kiến ​​thức nào mâu thuẫn với những gì nó đã biết. Ví dụ, nó có thể không thay thế một tuyên bố với phủ định của nó. Do đó, cơ sở tri thức chỉ có thể phát triển với các sự kiện mới theo một cách đơn điệu. Những lợi thế của việc học đơn điệu là:

1.greatly đơn giản hóa sự thật duy trì sự lựa chọn

2.greater trong các chiến lược học tập

không đơn điệu học tập là khi một nhân viên có thể học hỏi kiến ​​thức mà mâu thuẫn với những gì nó đã biết rồi. Vì vậy, nó có thể thay thế kiến ​​thức cũ với mới nếu nó tin rằng có đủ lý do để làm như vậy. Những lợi thế của việc học không đơn điệu là:

áp dụng 1.increased đến lĩnh vực sản,

2.greater tự do trong những điều để được học trong

Một tài sản có liên quan là sự thống nhất của kiến ​​thức. Nếu kiến ​​trúc phải duy trì một cơ sở tri thức nhất quán thì mọi chiến lược học tập mà nó sử dụng phải là đơn điệu.

Answer 3

Khả năng chấp nhận:

Thuật toán tìm kiếm được chấp nhận nếu được đảm bảo tìm đường dẫn tối thiểu cho giải pháp bất cứ khi nào giải pháp tồn tại. Bề rộng tìm kiếm đầu tiên là chấp nhận được, bởi vì nó nhìn vào mọi trạng thái ở mức n trước khi xem xét bất kỳ trạng thái nào ở mức n + 1.

Tính đơn điệu: Thuộc tính này hỏi xem thuật toán có được chấp nhận cục bộ hay không - nghĩa là, nó luôn luôn đánh giá thấp chi phí giữa hai trạng thái trong không gian tìm kiếm. Nhớ lại rằng A * không yêu cầu g (n) = g * (n). Một hàm heuristic, h là đơn điệu nếu: 1. Đối với tất cả các trạng thái ni và nj, trong đó nj là hậu duệ của ni, h (ni) - h (nj) < = chi phí (ni, nj).

2.Đánh giá phỏng đoán của trạng thái mục tiêu là 0: h (Mục tiêu) = 0.