Xin chào mọi người! Chắc hẳn ai trong giới lập trình chúng ta cũng đều gặp các bài toán liên quan đến Tìm kiếm (search, query, sort,…), vậy trong lĩnh vực trí tuệ nhân tạo người ta sử dụng những khái niệm, những thuật toán nào? Cùng mình đi tìm hiểu thêm nhé. Có visualization để mọi người hình dung =)). Show I. Phân loạiCó nhiều cách phân loại các thuật toán tìm kiếm, trong đó phổ biến hơn cả đó là chia làm 2 loại: Uninformed Search (Blind Search ?) và Informed Search (Heuristic Search ?).  “Kỳ thực trên mặt đất vốn làm gì có đường. Người ta đi mãi thì thành đường thôi.” – Lỗ Tấn Uninformed Search cũng vậy! Ta chỉ biết đích đến, còn nó ở đâu, đi như nào, bao giờ đến ta đều không biết ?, chỉ được cái là đi mãi cũng đến đích thôi. Phương pháp tìm kiếm mù có khả năng thám hiểm không gian trang thái để tìm ra trạng thái đích, tuy nhiên nó rất là không hiệu quả trong hầu hết bài toán, chậm và may rủi! Các chiến lược tìm kiếm phổ biến:
Nhắc đến DFS, BFS, hay Dijkstra thì chắc hẳn chúng ta ai cũng quá quen thuộc rồi, mình xin phép không nhắc lại, UCS sẽ có so sánh visualization ở phần sau. III. Informed Search (Heuristic Search / Tìm kiếm dựa kinh nghiệm)Đây sẽ là phần chính của blog ngày hôm nay. Vài khái niệm cơ bản:
Ta đi vào 2 thuật toán sử dụng hàm đánh giá để hiểu hơn rõ hơn nhé: Greedy Best-First-Search và A* Một ví dụ khác: A* Algorithm: UCS + Greedy Best-First-SearchKết hợp tính hiệu quả(nhanh) của G-BFS, tính tối ưu(luôn tìm ra lời giải đúng) của UCS Hàm đánh giá: f(n)=g(n) + h(n) g(n) – Chi phí từ node hiện tại tới node n h(n) – ước lượng khoảng cách từ node n -> đích UCS chỉ dùng g(n) nên chậm, G-BFS chỉ dựa h(n) nên không tối ưu f(n) – tối ưu + hiệu quả! Visualize để mọi người dễ hình dung: h(n) ở đây là Euclidean distance (Đường thẳng luôn là ngắn nhất đúng không nào ?) Dưới cùng là đường đi với h(n) = 5 * Euclidean distance . Có nhiều cách chọn hàm h(n), tuỳ cách chọn mà có thể tối ưu hoặc không. Kết luận: Heuristic không phải lúc nào cũng tìm ra giải pháp tối ưu nhất, nhưng nó có thể tìm ra một trong những giải phát tốt nhất trong thời gian ngắn với không gian bộ nhớ nhỏ. A* là một thuật toán rất thông minh, được Google Maps sử dụng trong bài toán tìm đường đi ngắn nhất thời gian thực!
Was this document helpful? Was this document helpful? Giải thuật tìm kiếm theo chiều rộng là gì? Giải thuật tìm kiếm theo chiều rộng (Breadth First Search – viết tắt là BFS) duyệt qua một đồ thị theo chiều rộng và sử dụng hàng đợi (queue) để ghi nhớ đỉnh liền kề để bắt đầu việc tìm kiếm khi không gặp được đỉnh liền kề trong bất kỳ vòng lặp nào. Như trong hình ví dụ trên, giải thuật tìm kiếm theo chiều rộng duyệt từ A tới B tới E tới F sau đó tới C, tới G và cuối cùng tới D. Giải thuật này tuân theo qui tắc: ●Qui tắc 1: Duyệt tiếp tới đỉnh liền kề mà chưa được duyệt. Đánh dấu đỉnh mà đã được duyệt. Hiển thị đỉnh đó và đẩy vào trong một hàng đợi (queue).. ●Qui tắc 2: Nếu không tìm thấy đỉnh liền kề, thì xóa đỉnh đầu tiên trong hàng đợi. ●Qui tắc 3: Lặp lại Qui tắc 1 và 2 cho tới khi hàng đợi là trống. Bảng dưới đây minh họa cách giải thuật tìm kiếm theo chiều rộng làm việc với một ví dụ đơn giản sau:
|
