Trong lĩnh vực trí tuệ nhân tạo và khoa học máy tính, thuật toán tìm kiếm giữ một vai trò quan trọng, đặc biệt là các thuật toán tìm kiếm không thông tin (Uninformed Search Algorithms). Các thuật toán này, như tên gọi của chúng, thực hiện tìm kiếm mà không có bất kỳ thông tin nào về mục tiêu ngoài cấu trúc của không gian tìm kiếm. Điều này có nghĩa là chúng không sử dụng bất kỳ dữ liệu nào có thể giúp chúng định hình hoặc ưu tiên các hướng tìm kiếm. Do đó, chúng thường được áp dụng trong các vấn đề mà không gian tìm kiếm là rõ ràng và không có thông tin hướng dẫn cụ thể.
Vai trò của các thuật toán tìm kiếm không thông tin trong trí tuệ nhân tạo là cơ bản và quan trọng. Chúng được sử dụng để giải quyết một loạt các vấn đề cơ bản, từ tìm kiếm đường đi trong bản đồ, đến sắp xếp và tổ chức dữ liệu, và thậm chí trong việc phát triển các trò chơi thông minh. Mặc dù có vẻ đơn giản, nhưng các thuật toán này là nền tảng để xây dựng các thuật toán phức tạp hơn, có sử dụng thông tin hướng dẫn, hay còn gọi là informed search algorithms.
Trong khoa học máy tính, việc hiểu và vận dụng thành thạo các thuật toán tìm kiếm không thông tin là rất quan trọng. Chúng không chỉ cung cấp nền tảng vững chắc cho việc phát triển các giải pháp tìm kiếm tiên tiến hơn mà còn giúp người học phát triển tư duy về cách giải quyết vấn đề một cách hệ thống và logic. Ngoài ra, việc hiểu biết sâu sắc về cách thức hoạt động của những thuật toán này còn mở đường cho việc nghiên cứu và phát triển trong các lĩnh vực nâng cao như học máy và xử lý ngôn ngữ tự nhiên.
Bài viết này sẽ đi sâu vào các thuật toán tìm kiếm không thông tin, bắt đầu bằng cách định nghĩa và phân loại chúng, sau đó phân tích từng loại thông qua các ví dụ cụ thể và mã giả. Đồng thời, bài viết cũng sẽ đề cập đến các ưu nhược điểm và khả năng ứng dụng của chúng trong thực tiễn.
Các Đặc Điểm Chung của Uninformed Search Algorithms
Uninformed search là một loại thuật toán tìm kiếm có mục đích chung hoạt động theo cách brute force. Các thuật toán tìm kiếm không thông tin không có thêm thông tin về trạng thái hoặc không gian tìm kiếm ngoài cách đi qua cây, vì vậy nó còn được gọi là tìm kiếm mù.
Thuật toán tìm kiếm không thông tin, hay Uninformed Search Algorithms, là một nhóm các thuật toán tìm kiếm mà không dựa vào thông tin bổ sung hay tiên đoán về kết quả tìm kiếm. Những thuật toán này hoạt động dựa trên cơ sở dữ liệu và cấu trúc hiện có mà không sử dụng bất kỳ dạng hướng dẫn hoặc đánh giá nào để ưu tiên các lựa chọn tìm kiếm. Điều này có nghĩa là chúng tiếp cận không gian tìm kiếm một cách mù quáng, thăm dò mỗi khả năng cho đến khi tìm ra giải pháp hoặc khẳng định rằng không có giải pháp.
Các thuật toán này thường được phân loại dựa trên chiến lược duyệt không gian tìm kiếm của chúng, bao gồm:
- Tìm kiếm theo Chiều Rộng (Breadth-First Search – BFS): BFS là một cách tiếp cận mà ở đó thuật toán xem xét tất cả các trạng thái cùng một cấp độ trước khi chuyển sang cấp độ tiếp theo. Điều này đảm bảo rằng nếu có giải pháp, nó sẽ được tìm thấy ở độ sâu ít nhất có thể.
- Tìm kiếm theo Chiều Sâu (Depth-First Search – DFS): Ngược lại với BFS, DFS tập trung vào việc khám phá một nhánh của không gian tìm kiếm càng sâu càng tốt trước khi quay lui và thăm dò nhánh khác. Điều này thường yêu cầu ít bộ nhớ hơn nhưng có nguy cơ mắc kẹt trong những tìm kiếm vô hạn.
- Tìm kiếm Chiều Sâu Giới Hạn (Depth-Limited Search): Đây là biến thể của DFS, nơi mà độ sâu tìm kiếm được giới hạn. Điều này giúp tránh vấn đề của DFS khi mắc kẹt trong các chu kỳ vô hạn nhưng có thể bỏ lỡ giải pháp nếu nó nằm ngoài giới hạn đặt ra.
- Tìm kiếm Chiều Sâu Lặp lại (Iterative Deepening Depth-First Search): Kết hợp ưu điểm của BFS và DFS, phương pháp này thực hiện DFS với giới hạn độ sâu tăng dần. Nó đảm bảo rằng giải pháp, nếu tồn tại, sẽ được tìm thấy ở độ sâu tối thiểu.
Các thuật toán tìm kiếm không thông tin này đều chia sẻ một số đặc điểm chung như đơn giản trong cách thực hiện, dễ hiểu, và dễ áp dụng. Tuy nhiên, do không tận dụng được thông tin hướng dẫn, chúng thường không hiệu quả trong việc giải quyết những bài toán có không gian tìm kiếm lớn. Sự đơn giản của các thuật toán này cũng là cơ sở để xây dựng và mở rộng thành các thuật toán tìm kiếm thông tin (Informed Search Algorithms), có khả năng giải quyết vấn đề một cách nhanh chóng và hiệu quả hơn.
Sau đây là các loại thuật toán tìm kiếm không được thông tin khác nhau:
Breadth-first Search:
Breadth-first Search là chiến lược tìm kiếm phổ biến nhất để duyệt qua một cây hoặc biểu đồ. Thuật toán này Breadth-first Search trong một cây hoặc biểu đồ, vì vậy nó được gọi là Breadth-first Search.
Thuật toán BFS bắt đầu tìm kiếm từ nút gốc của cây và mở rộng tất cả các nút kế thừa ở cấp hiện tại trước khi chuyển sang các nút của cấp tiếp theo.
Thuật toán Breadth-first Search là một ví dụ của thuật toán tìm kiếm đồ thị tổng quát.
Breadth-first Search được triển khai bằng cách sử dụng cấu trúc dữ liệu hàng đợi FIFO.
Thuận lợi:
- BFS sẽ cung cấp giải pháp nếu có bất kỳ giải pháp nào.
- Nếu có nhiều hơn một giải pháp cho một vấn đề nhất định, thì BFS sẽ cung cấp giải pháp tối thiểu yêu cầu số bước ít nhất.
Nhược điểm:
- Nó yêu cầu nhiều bộ nhớ vì mỗi cấp độ của cây phải được lưu vào bộ nhớ để mở rộng cấp độ tiếp theo.
- BFS cần nhiều thời gian nếu giải pháp ở xa nút gốc.
Ví dụ:
Trong cấu trúc cây dưới đây, chúng tôi đã chỉ ra sự di chuyển của cây bằng cách sử dụng thuật toán BFS từ nút gốc S đến nút mục tiêu K. Thuật toán tìm kiếm BFS đi ngang trong các lớp, vì vậy nó sẽ đi theo đường dẫn được hiển thị bằng mũi tên chấm, và đường đi ngang sẽ là:
S —> A —> B —-> C —> D —-> G —> H —> E —-> F —-> I —-> K
Time Complexity: Độ phức tạp về thời gian của thuật toán BFS có thể được tính bằng số lượng nút được duyệt trong BFS cho đến nút nông nhất. Trong đó d = độ sâu của nghiệm nông nhất và b là một nút ở mọi trạng thái.
T (b) = 1 + b2 + b3 + ……. + bd = O (bd)
Space Complexity: Độ phức tạp không gian của thuật toán BFS được cung cấp bởi kích thước bộ nhớ của biên giới là O (bd).
Completeness: BFS đã hoàn thành, có nghĩa là nếu nút mục tiêu nông nhất nằm ở độ sâu hữu hạn nào đó, thì BFS sẽ tìm ra giải pháp.
Optimality: BFS là tối ưu nếu chi phí đường dẫn là một hàm không giảm của độ sâu của nút.
Depth-first Search
Tìm kiếm theo độ sâu là một thuật toán đệ quy để duyệt qua cấu trúc dữ liệu dạng cây hoặc đồ thị.
Nó được gọi là tìm kiếm theo chiều sâu vì nó bắt đầu từ nút gốc và đi theo từng đường dẫn đến nút có độ sâu lớn nhất trước khi chuyển sang đường tiếp theo.
DFS sử dụng cấu trúc dữ liệu ngăn xếp để thực hiện nó.
Quy trình của thuật toán DFS tương tự như thuật toán BFS.
Lưu ý: Backtracking là một kỹ thuật thuật toán để tìm tất cả các giải pháp khả thi bằng cách sử dụng đệ quy.
Thuận lợi:
- DFS yêu cầu rất ít bộ nhớ vì nó chỉ cần lưu trữ một chồng các nút trên đường dẫn từ nút gốc đến nút hiện tại.
- Mất ít thời gian hơn để đến được nút mục tiêu so với thuật toán BFS (nếu nó đi đúng đường).
Bất lợi:
Có khả năng nhiều trạng thái tiếp tục tái diễn và không có gì đảm bảo cho việc tìm ra giải pháp.
Thuật toán DFS dùng để tìm kiếm sâu hơn và đôi khi nó có thể đi đến vòng lặp vô hạn.
Ví dụ:
Trong cây tìm kiếm bên dưới, chúng tôi đã hiển thị luồng tìm kiếm theo chiều sâu và nó sẽ tuân theo thứ tự như sau:
Nút gốc —> Nút trái —-> nút phải.
Nó sẽ bắt đầu tìm kiếm từ nút gốc S, và đi ngang qua A, rồi đến B, rồi D và E, sau khi đi qua E, nó sẽ dò ngược cây vì E không có nút kế thừa nào khác và vẫn không tìm thấy nút mục tiêu. Sau khi bẻ khóa ngược, nó sẽ đi ngang qua nút C và sau đó là G, và tại đây nó sẽ kết thúc khi tìm thấy nút mục tiêu.
Completeness: Thuật toán tìm kiếm DFS hoàn chỉnh trong không gian trạng thái hữu hạn vì nó sẽ mở rộng mọi nút trong cây tìm kiếm giới hạn.
Time Complexity: Độ phức tạp thời gian của DFS sẽ tương đương với nút được thuật toán duyệt qua. Nó được đưa ra bởi:
T (n) = 1+ n2 + n3 + ……… + nm = O (nm)
Trong đó, m = độ sâu tối đa của bất kỳ nút nào và giá trị này có thể lớn hơn nhiều so với d (Độ sâu nghiệm nông nhất)
Space Complexity: Thuật toán DFS chỉ cần lưu trữ một đường dẫn duy nhất từ nút gốc, do đó độ phức tạp không gian của DFS tương đương với kích thước của tập rìa, là O (bm).
Optimal: Thuật toán tìm kiếm DFS không tối ưu, vì nó có thể tạo ra một số lượng lớn các bước hoặc chi phí cao để đạt đến nút mục tiêu.
Thuật toán Depth-limited Search:
Thuật toán tìm kiếm giới hạn theo chiều sâu tương tự như tìm kiếm theo chiều sâu với giới hạn xác định trước. Depth-limited Search có thể giải quyết nhược điểm của đường dẫn vô hạn trong Depth-first Search. Trong thuật toán này, nút ở giới hạn độ sâu sẽ coi như nó không có nút kế thừa nào nữa.
Depth-limited Search có thể bị chấm dứt với hai Điều kiện thất bại:
- Giá trị lỗi tiêu chuẩn: Nó chỉ ra rằng vấn đề không có bất kỳ giải pháp nào.
- Giá trị lỗi cắt: Nó xác định không có giải pháp cho vấn đề trong một giới hạn độ sâu nhất định.
Ưu điểm
Depth-limited Search là Bộ nhớ hiệu quả.
Nhược điểm:
Depth-limited Search cũng có một nhược điểm là không đầy đủ.
Nó có thể không tối ưu nếu bài toán có nhiều hơn một giải pháp.
Ví dụ:
Completeness: Thuật toán tìm kiếm DLS hoàn tất nếu giải pháp nằm trên giới hạn độ sâu.
Time Complexity: Độ phức tạp về thời gian của thuật toán DLS là O (bℓ).
Space Complexity: Độ phức tạp không gian của thuật toán DLS là O (b × ℓ).
Optimal: Depth-limited Search có thể được xem như một trường hợp đặc biệt của DFS và nó cũng không phải là tối ưu ngay cả khi ℓ> d.
Thuật toán Uniform cost search
Tìm kiếm theo chi phí thống nhất là một thuật toán tìm kiếm được sử dụng để duyệt qua một cây hoặc đồ thị có trọng số. Thuật toán này phát huy tác dụng khi có sẵn một chi phí khác nhau cho mỗi cạnh. Mục tiêu chính của Uniform cost search là tìm đường dẫn đến nút mục tiêu có chi phí tích lũy thấp nhất. Uniform cost search mở rộng các nút theo chi phí đường dẫn của chúng tạo thành nút gốc. Nó có thể được sử dụng để giải quyết bất kỳ biểu đồ / cây nào có nhu cầu về chi phí tối ưu. Thuật toán Uniform cost search được thực hiện bởi hàng đợi ưu tiên. Nó ưu tiên tối đa cho chi phí tích lũy thấp nhất. Uniform cost search tương đương với thuật toán BFS nếu chi phí đường dẫn của tất cả các cạnh là như nhau.
Thuận lợi:
Uniform cost search là tối ưu vì ở mọi trạng thái, con đường có chi phí thấp nhất được chọn.
Nhược điểm:
Nó không quan tâm đến số bước liên quan đến việc tìm kiếm và chỉ quan tâm đến chi phí đường dẫn. Do đó thuật toán này có thể bị mắc kẹt trong một vòng lặp vô hạn.
Ví dụ:
Completeness:
Uniform cost search đã hoàn tất, chẳng hạn như nếu có giải pháp, UCS sẽ tìm ra giải pháp đó.
Time Complexity:
Gọi C * là Chi phí của giải pháp tối ưu và ε là mỗi bước để tiến gần hơn đến nút mục tiêu. Khi đó số bước là = C * / ε + 1. Ở đây chúng tôi đã lấy +1, khi chúng tôi bắt đầu từ trạng thái 0 và kết thúc đến C * / ε.
Do đó, độ phức tạp thời gian trong trường hợp xấu nhất của Tìm kiếm theo chi phí thống nhất làO (b1 + [C * / ε]) /.
Space Complexity:
Logic tương tự là đối với độ phức tạp không gian, vì vậy, độ phức tạp không gian trong trường hợp xấu nhất của Tìm kiếm theo chi phí thống nhất là O (b1 + [C * / ε]).
Optimal:
Tìm kiếm theo chi phí thống nhất luôn tối ưu vì nó chỉ chọn một đường dẫn có chi phí đường dẫn thấp nhất.
Thuật toán Iterative deepening depth-first search
Thuật toán Iterative deepening depth-first search của thuật toán DFS và BFS. Thuật toán tìm kiếm này tìm ra giới hạn độ sâu tốt nhất và thực hiện nó bằng cách tăng dần giới hạn cho đến khi tìm thấy mục tiêu.
Thuật toán này thực hiện tìm kiếm theo chiều sâu đến một “giới hạn độ sâu” nhất định và nó tiếp tục tăng giới hạn độ sâu sau mỗi lần lặp cho đến khi tìm thấy nút mục tiêu.
Thuật toán tìm kiếm này kết hợp các lợi ích của tìm kiếm nhanh trên Breadth-first search và hiệu quả bộ nhớ của tìm kiếm theo chiều sâu.
Thuật toán tìm kiếm lặp lại là tìm kiếm không có thông tin hữu ích khi không gian tìm kiếm lớn và độ sâu của nút mục tiêu là không xác định.
Thuận lợi:
Nó kết hợp các lợi ích của thuật toán tìm kiếm BFS và DFS về khả năng tìm kiếm nhanh và hiệu quả bộ nhớ.
Nhược điểm:
Hạn chế chính của IDDFS là nó lặp lại tất cả các công việc của giai đoạn trước.
Ví dụ:
Cấu trúc cây sau đang hiển thị tìm kiếm đầu tiên theo chiều sâu làm sâu thêm lặp đi lặp lại. Thuật toán IDDFS thực hiện nhiều lần lặp khác nhau cho đến khi nó không tìm thấy nút mục tiêu. Phép lặp được thực hiện bởi thuật toán được cho là:
Lặp lại lần 1 —--> A
2’và Lặp lại —-> A, B, C
Lặp lại thứ 3 ——> A, B, D, E, C, F, G
Lặp lại thứ 4 ——> A, B, D, H, I, E, C, F, K, G
Trong lần lặp thứ tư, thuật toán sẽ tìm nút mục tiêu.
Completeness:
Thuật toán này hoàn thành nếu hệ số phân nhánh là hữu hạn.
Time Complexity:
Giả sử b là hệ số phân nhánh và độ sâu là d thì độ phức tạp thời gian trong trường hợp xấu nhất là O (bd).
Space Complexity:
Độ phức tạp không gian của IDDFS sẽ là O (bd).
Optimal:
Thuật toán IDDFS là tối ưu nếu chi phí đường dẫn là một hàm không giảm của độ sâu của nút.
Thuật toán Bidirectional Search
Thuật toán Bidirectional Search chạy hai tìm kiếm đồng thời, một ở trạng thái ban đầu của biểu mẫu được gọi là tìm kiếm chuyển tiếp và từ nút mục tiêu khác được gọi là tìm kiếm ngược, để tìm nút mục tiêu. Bidirectional Search thay thế một biểu đồ tìm kiếm đơn lẻ bằng hai đồ thị con nhỏ, trong đó một đồ thị bắt đầu tìm kiếm từ đỉnh ban đầu và đồ thị khác bắt đầu từ đỉnh mục tiêu. Việc tìm kiếm dừng lại khi hai đồ thị này cắt nhau.
Bidirectional Search có thể sử dụng các kỹ thuật tìm kiếm như BFS, DFS, DLS, v.v.
Thuận lợi:
Bidirectional Search nhanh chóng.
Bidirectional Search yêu cầu ít bộ nhớ hơn
Nhược điểm:
Việc triển khai cây Bidirectional Search rất khó.
Trong Bidirectional Search, người ta nên biết trước trạng thái mục tiêu.
Ví dụ:
Trong cây tìm kiếm bên dưới, thuật toán Bidirectional Search được áp dụng. Thuật toán này chia một đồ thị / cây thành hai đồ thị con. Nó bắt đầu đi ngang từ nút 1 theo hướng tiến và bắt đầu từ nút mục tiêu 16 theo hướng lùi.
Thuật toán kết thúc tại nút 9 nơi hai tìm kiếm gặp nhau.
Completeness: Bidirectional Search sẽ hoàn tất nếu chúng tôi sử dụng BFS trong cả hai tìm kiếm.
Time Complexity: Độ phức tạp về thời gian của Bidirectional Search sử dụng BFS là O (bd).
Space Complexity: Độ phức tạp về không gian của Bidirectional Search là O (bd).
Optimal: Bidirectional Search là Tối ưu.
