Có máy giải thuật dựa vào giải thuật tìm kiếm tốt nhất đầu tiên

Published thg 1 13, 2019 11:38 SA 8 min read

This post hasn't been updated for 2 years

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai thuật toán này lại khiến không ít người cảm thấy bối rối khi lần đầu tìm hiểu, đơn giản vì nhìn về "tinh thần chung" hai thuật toán này khá giống nhau, ví dụ: "cả hai đều đánh giá chi phí và lựa chọn node tiếp theo với mục tiêu chi phí đường đi là thấp nhất". Vậy bài viết này chúng ta cùng tìm hiểu kỹ hơn để phân biệt hai thuật toán này nhé!

Có máy giải thuật dựa vào giải thuật tìm kiếm tốt nhất đầu tiên

Để hiểu về UCS và Best First Search, trước tiên chúng ta nên ôn tập qua hai khái niệm tìm kiếm mù và tìm kiếm kinh nghiệm.

Tìm kiếm mù

Chiến lược tìm kiếm mù là kỹ thuật tìm kiếm mà trong đó chúng ta không có hiểu biết gì về các đối tượng để có hướng dẫn tìm kiếm mà chỉ đơn thuần xem xét các đối tượng theo một hệ thống nào đó để phát hiện ra đối tượng cần tìm.

Tìm kiếm kinh nghiệm

Chiến lược tìm kiếm kinh nghiệm (tìm kiếm heuristic) là kỹ thuật tìm kiếm dựa vào kinh nghiệm và sự hiểu biết của chúng ta về vấn đề cần giải quyết để xây dựng nên hàm đánh giá hướng dẫn sự tìm kiếm.

Tiếp theo, cùng xem lại hai thuật toán gây mông lung nào!!

Thuật toán UCS

Thuật toán UCS là một thuật toán duyệt, tìm kiếm trên một cấu trúc cây, hoặc đồ thị có trọng số (chi phí). Việc tìm kiếm bắt đầu tại nút gốc và tiếp tục bằng cách duyệt các nút tiếp theo với trọng số hay chi phí thấp nhất tính từ nút gốc.
Mã giả:

begin procedure UniformCostSearch(Graph, root, goal) node:= root, cost = 0 frontier:= priority queue containing node only explored:= empty set do if frontier is empty return failure node:= frontier.pop() if node is goal return solution explored.add(node) for each of node's neighbors n if n is not in explored if n is not in frontier frontier.add(n) else if n is in frontier with higher cost replace existing node with n

Ví dụ cách hoạt động:
Hình 1. Đồ thị ví dụ cách hoạt động UCS

Có máy giải thuật dựa vào giải thuật tìm kiếm tốt nhất đầu tiên

Cho đồ thị như hình trên, nút gốc là A, duyệt và tìm đường đi đến G với chi phí thấp nhất. Bảng dưới đấy mô tả các bước duyệt đồ thị Hình 1:

Có máy giải thuật dựa vào giải thuật tìm kiếm tốt nhất đầu tiên

Trong đó: [*] Nút được chọn để duyệt cho bước tiếp theo.

[**] B không được thêm vào hàng đợi vì nó đã nằm trong tập đã xét.