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
Show 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é! Để 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ệmChiế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 UCSThuậ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. Ví dụ cách hoạt động: 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: 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. Thuật toán Best First SearchTrong tìm kiếm kinh nghiệm, chúng ta dùng hàm đánh giá để hướng dẫn tìm kiếm. Tìm kiếm tốt nhất - đầu tiên (Best First Search) là tìm kiếm theo bề rộng (Breadth First Search) được hướng dẫn bởi hàm đánh giá. Tư tưởng của thuật toán này là 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 có giá trị của hàm đánh giá là thấp nhất so với các nút còn lại nằm trong hàng đợi. Ví dụ cách hoạt động: Cho đồ thị như hình trên, nút gốc là A, duyệt và tìm đường đi tốt nhất đến B. Cây dưới đây mô tả các bước duyệt đồ thị Hình 2: Đầu tiên phát triển đỉnh A sinh ra các đỉnh kề là C, D và E. Trong ba đỉnh này, đỉnh D có giá trị hàm đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra F, I. Trong số các đỉnh chưa được phát triển C, E, F, I thì đỉnh E có giá trị đánh giá nhỏ nhất, nó được chọn để phát triển và sinh ra các đỉnh G, K. Trong số các đỉnh chưa được phát triển thì G tốt nhất, phát triển G sinh ra B, H. Đến đây ta đã đạt tới trạng thái kết thúc. Trong thủ tục này, chúng ta sử dụng danh sách L để lưu các trạng thái chờ phát triển, danh sách được sắp theo thứ tự tăng dần của hàm đánh giá sao cho trạng thái có giá trị hàm đánh giá nhỏ nhất ở đầu danh sách. So sánh hai thuật toánTa có thể thấy cả hai thuật toán UCS và Best First Search đều sử dụng hàng đợi ưu tiên để lưu danh sách các node chờ duyệt, và đây có lẽ là nguyên nhân mấu chốt dẫn đến việc gây nhầm lẫn giữa hai thuật toán. Qua mỗi bước duyệt, các node còn lại trong danh sách đều được so sánh để sắp xếp lại và chọn ra node "được cho là" có chi phí thấp nhất. Nhưng sự khác nhau ở hai thuật toán có vẻ cũng nằm ở đây. Trước khi sắp xếp lại danh sách các node, UCS vì không có hàm đánh giá nên nó cần tự thân vận động:
Trong khi Best First Search thì không phải làm gì cả, vì nó đã có hàm đánh giá ngay tại node rồi. Bên cạnh đó, chúng ta cũng nhận thấy rằng Best First Search nồng nặc mùi greedy (chiến lược tham ăn) .
Với d, m là độ sâu của cây cần duyệt và mỗi trạng thái khi được phát triển sẽ sinh ra b trạng thái kề (b được gọi là nhân tố nhánh). Bài viết hơi dài, hẹn gặp lại các bạn trong một bài viết khác All Rights Reserved |