Tuy nhiên, giữa cả kỹ thuật tìm kiếm có thông tin và không có thông tin, việc tìm kiếm có hiểu biết sẽ hiệu quả và tiết kiệm chi phí hơn.
Biểu đồ so sánh
| Cơ sở để so sánh | Tìm kiếm thông báo | Tìm kiếm không xác định |
|---|---|---|
| Căn bản | Sử dụng kiến thức để tìm các bước để giải quyết. | Không sử dụng kiến thức |
| Hiệu quả | Hiệu quả cao vì tiêu thụ ít thời gian và chi phí. | Hiệu quả là trung gian |
| Giá cả | Thấp | Tương đối cao |
| Hiệu suất | Tìm giải pháp nhanh hơn | Tốc độ chậm hơn tìm kiếm thông báo |
| Thuật toán | Tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng và tìm kiếm đầu tiên có chi phí thấp nhất | Độ sâu tìm kiếm đầu tiên và tìm kiếm theo chiều rộng đầu tiên và tìm kiếm A * |
Định nghĩa tìm kiếm thông tin
Kỹ thuật tìm kiếm thông báo sử dụng kiến thức cụ thể của vấn đề để đưa ra manh mối cho giải pháp của vấn đề. Loại chiến lược tìm kiếm này thực sự ngăn các thuật toán vấp ngã về mục tiêu và hướng đến giải pháp. Tìm kiếm thông tin có thể là lợi thế về chi phí mà sự tối ưu đạt được với chi phí tìm kiếm thấp hơn.
Để tìm kiếm một chi phí đường dẫn tối ưu trong biểu đồ bằng cách thực hiện chiến lược tìm kiếm có thông tin, các nút hứa hẹn nhất n được chèn vào hàm heuristic h (n). Sau đó, hàm trả về một số thực không âm là chi phí đường dẫn gần đúng được tính từ nút n đến nút đích.
Ở đây, phần quan trọng nhất của kỹ thuật thông tin là hàm heuristic tạo điều kiện thuận lợi trong việc truyền đạt kiến thức bổ sung về vấn đề cho thuật toán. Kết quả là, nó giúp tìm đường đến mục tiêu thông qua các nút lân cận khác nhau. Có nhiều thuật toán khác nhau dựa trên tìm kiếm được thông báo như tìm kiếm theo chiều sâu heuristic, tìm kiếm theo chiều rộng heuristic, tìm kiếm A *, vân vân. Bây giờ chúng ta hãy tìm hiểu sâu heuristic - tìm kiếm đầu tiên.
Độ sâu tìm kiếm đầu tiên
Tương tự như phương pháp tìm kiếm theo chiều sâu được đưa ra bên dưới tìm kiếm theo chiều sâu heuristic trước tiên chọn một đường dẫn nhưng đi qua tất cả các đường dẫn từ đường dẫn đã chọn trước khi chọn đường dẫn khác. Tuy nhiên, nó chọn con đường tốt nhất tại địa phương. Trong trường hợp giá trị heuristic nhỏ nhất là ưu tiên cho biên giới, thì nó được gọi là tìm kiếm đầu tiên tốt nhất.
Một thuật toán tìm kiếm thông báo khác là tìm kiếm A * kết hợp khái niệm chi phí thấp nhất và tìm kiếm đầu tiên tốt nhất. Phương pháp này xem xét cả chi phí đường dẫn và thông tin heuristic trong quá trình tìm kiếm và chọn đường dẫn sẽ được mở rộng. Tổng chi phí đường dẫn ước tính được sử dụng cho mỗi đường dẫn nằm ở biên giới từ điểm bắt đầu đến nút đích. Do đó, nó sử dụng hai hàm cùng một lúc - cost (p) là chi phí của đường dẫn được khám phá và h (p) là giá trị ước tính của chi phí đường dẫn từ nút bắt đầu đến nút mục tiêu.
Định nghĩa tìm kiếm không xác định
Tìm kiếm không xác định khác với tìm kiếm có thông tin theo cách nó chỉ cung cấp định nghĩa vấn đề nhưng không có thêm bước nào để tìm giải pháp cho vấn đề. Mục tiêu chính của tìm kiếm không xác định là phân biệt giữa trạng thái mục tiêu và không nhắm mục tiêu và nó hoàn toàn bỏ qua đích đến mà nó đang hướng tới trong đường dẫn cho đến khi phát hiện ra mục tiêu và báo cáo người kế nhiệm. Chiến lược này còn được gọi là tìm kiếm mù.
Có nhiều thuật toán tìm kiếm khác nhau trong danh mục này, chẳng hạn như tìm kiếm theo chiều sâu, tìm kiếm chi phí thống nhất, tìm kiếm theo chiều rộng, v.v. Bây giờ chúng ta hãy hiểu khái niệm đằng sau tìm kiếm không xác định với sự trợ giúp của tìm kiếm theo chiều sâu.
Độ sâu tìm kiếm đầu tiên
Trong tìm kiếm đầu tiên chuyên sâu, một ngăn xếp cuối cùng ra trước được sử dụng để thêm và loại bỏ các nút. Mỗi lần chỉ có một nút được thêm hoặc xóa và phần tử đầu tiên được xóa khỏi biên giới của ngăn xếp sẽ là phần tử cuối cùng được thêm vào ngăn xếp. Bằng cách sử dụng ngăn xếp ở biên giới, kết quả là việc tìm kiếm các đường dẫn được tiến hành theo chiều sâu. Khi một đường dẫn ngắn nhất và tối ưu được tìm kiếm bằng cách sử dụng tìm kiếm theo chiều sâu, đường dẫn được tạo bởi các nút lân cận sẽ được hoàn thành trước ngay cả khi nó không phải là đường mong muốn. Sau đó, đường dẫn thay thế được tìm kiếm thông qua quay lui.
Nói cách khác, thuật toán chọn phương án đầu tiên tại mỗi nút sau đó quay lại chỗ khác cho đến khi nó đi qua tất cả các đường dẫn từ lựa chọn đầu tiên. Điều này cũng đặt ra một vấn đề trong đó việc tìm kiếm có thể dừng lại do các vòng lặp (chu kỳ) vô hạn có trong biểu đồ.
Sự khác biệt chính giữa Tìm kiếm có hiểu biết và không có thông tin
- Các kỹ thuật tìm kiếm thông báo trước đây sử dụng kiến thức để tìm ra giải pháp. Mặt khác, kỹ thuật tìm kiếm không xác định sau này không sử dụng kiến thức. Nói một cách đơn giản, không có thêm thông tin nào được cung cấp về giải pháp.
- Hiệu quả của tìm kiếm thông báo tốt hơn so với tìm kiếm không được thông báo.
- Tìm kiếm không xác định tiêu tốn nhiều thời gian và chi phí hơn vì nó không có manh mối về giải pháp so với tìm kiếm thông báo.
- Tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng và tìm kiếm đầu tiên có chi phí thấp nhất là các thuật toán thuộc danh mục tìm kiếm không xác định. Ngược lại, tìm kiếm có thông tin bao gồm các thuật toán như tìm kiếm theo chiều sâu, tìm kiếm theo chiều rộng đầu tiên và tìm kiếm A *.
Phần kết luận
Tìm kiếm được thông báo cung cấp hướng liên quan đến giải pháp trong khi trong tìm kiếm không có thông tin, không có gợi ý nào được đưa ra liên quan đến giải pháp. Điều này làm cho tìm kiếm không xác định dài hơn khi thuật toán được thực hiện.
