[Cẩm nang AI] Các thuật toán tìm kiếm phổ biến trong AI

Trong phần này của cẩm nang AI, chúng ta sẽ nghiên cứu về các thuật toán tìm kiếm phổ biến trong trí tuệ nhân tạo AI. Bên cạnh đó, chúng ta sẽ cùng xem qua các kỹ thuật, phương pháp và thuật toán tìm kiếm phổ biến nhất. Để bạn dễ hiểu hơn, Viettel IDC sẽ sử dụng các ví dụ và hình ảnh đi kèm.

Trong thuật toán nhân tạo AI, để giải quyết vấn đề, chúng ta sử dụng kỹ thuật tìm kiếm. Các thuật toán tìm kiếm sẽ giúp bạn tìm kiếm một vị trí cụ thể dễ dàng như trong các trò chơi.

 

Thuật toán trong AI

Thuật toán tìm đường cho tác nhân đơn lẻ (Single Agent Pathfinding Problems)

Có nhiều loại trò chơi khác nhau. Chẳng hạn như 3X3, 4X4 là những ví dụ cho các thuật toán tìm kiếm đường dẫn đơn tác nhân. Vì chúng bao gồm một ma trận có nhiều ô với một ô trống.

 

Trong thuật toán này, bạn cần phải sắp xếp các ô bằng cách trượt một ô theo chiều dọc hoặc chiều ngang vào một không gian trống, kèm theo đó là thực hiện một số mục tiêu nhất định.

 

Một số ví dụ cụ thể cho thuật toán này là trò chơi giải đố bằng khối lập phương Rubik.

Thuật toán tìm kiếm bằng thuật ngữ (Search Algorithms Terminology)

I. Sự cố không gian (Problem Space)

Hiểu đơn giản, đây là môi trường mà việc tìm kiếm diễn ra (nói cách khác, đây là một tập hợp gồm các trạng thái và các toán tử có tác dụng thay đổi các trạng thái đó)

 

II. Trường hợp sự cố (Problem Instance)

Đây là kết quả của trạng thái ban đầu + trạng thái mục tiêu.

 

III. Biểu đồ không gian sự cố (Problem Space Graph)

Chúng tôi sử dụng phần này để thể hiện các trạng thái đang gặp phải vấn đề. Ngoài ra, chúng tôi sử dụng các nút để hiển thị trạng thái. Lúc đó, các toán tử được hiển thị bằng các cạnh.

 

IV. Chiều sâu của một vấn đề

Chúng ta có thể xác định độ dài của đường đi ngắn nhất.

 

V. Sự phức tạp của không gian

Chúng ta có thể tính toán về chúng tương tự với như số lượng nút tối đa được lưu trữ trong bộ nhớ.

 

VI. Sự phức tạp của thời gian

Khái niệm này được định nghĩa là số lượng nút tối đa được tạo.

 

VII. Sự chấp nhận

Chúng ta có thể xem nó như một thuộc tính của thuật toán, chúng ta sử dụng thuộc này tính để tìm ra một giải pháp tối ưu nhất.

 

VIII. Yếu tố phân nhánh 

Chúng ta có thể xem nó như là tổng số lượng nút con trung bình, trong biểu đồ không gian của bài toán.

 

IX. Chiều sâu

Độ dài của đường đi ngắn nhất từ ​​trạng thái ban đầu đến trạng thái mục tiêu.

Chiến lược tìm kiếm Brute-Force

Chiến lược này không yêu cầu bất kỳ kiến ​​thức về miền cụ thể nào. Vì vậy, đây là một chiến lược rất đơn giản. Do đó, chiến lược này sẽ hoạt động rất ổn định và nhanh chóng, với số trạng thái có thể xảy ra là rất ít. 

 

Yêu cầu đối với thuật toán Brute Force:

     - Mô tả trạng thái

     - Tập hợp các toán tử hợp lệ

     - Trạng thái ban đầu

     - Mô tả trạng thái mục tiêu

Thuật toán tìm kiếm theo chiều rộng trong AI (Breadth-First Search Algorithm)

Đầu tiên, chúng ta phải tìm kiếm từ nút gốc, sau đó sẽ thông qua các nút lân cận rồi chuyển sang cấp độ tiếp theo của các nút. Cho đến khi tìm ra giải pháp, chúng ta hãy tạo theo từng cây một. Giải thuật tìm kiếm theo chiều rộng này được thực hiện bằng cách sử dụng cấu trúc dữ liệu hàng đợi FIFO. Phương pháp này sẽ cung cấp đường dẫn ngắn nhất để tìm đến giải pháp.

 

FIFO là viết tắt của First in First Out - Nhập trước xuất trước.

 

Nếu hệ số phân nhánh (số nút con trung bình của một nút nhất định) = b và độ sâu = d thì số nút ở mức d = bd.

 

Tổng số nút được tạo trong trường hợp xấu nhất là b + b2 + b3 +… + bd.

 

Nhược điểm của mô hình này:

    - Chúng sẽ tiêu tốn rất nhiều không gian trong bộ nhớ, vì mỗi cấp độ của các nút đều sẽ được lưu lại để tạo cấp độ tiếp theo.

    - Độ phức tạp của mô hình này phụ thuộc vào số lượng nút. Mô hình FIFO có thể kiểm tra các nút trùng lặp

.

Thuật toán tìm kiếm theo chiều sâu trong AI (Depth-First Search Algorithm in AI)

Thuật toán này được xây dựng dựa trên khái niệm LIFO (viết tắt của Last In First Out - nhập sau xuất trước). Ngoài ra, mô hình thuật toán này được thực hiện trong đệ quy với cấu trúc dữ liệu ngăn xếp LIFO. Do đó, chúng được sử dụng để tạo cùng một tập hợp các nút như phương thức Breadth-First, chỉ khác về thứ tự.

 

Vì đường dẫn được lưu trữ lại sau mỗi lần lặp lại từ nút gốc đến nút lá, do đó, tổng hợp các nút sẽ tuyến tính với các yêu cầu về không gian, với hệ số phân nhánh b và chiều sâu là m, không gian lưu trữ là bm.

 

Nhược điểm:

    - Vì thuật toán có thể không kết thúc và tiếp tục vô hạn trên một con đường, do đó, một giải pháp cho vấn đề này là chọn độ sâu đã bị cắt.

    - Nếu điểm cắt lý tưởng là d và nếu điểm cắt đã chọn nhỏ hơn d, thì thuật toán này có thể sẽ thất bại và bị sai.

    - Nếu giới hạn đã chọn lớn hơn d, thì thời gian thực hiện sẽ tăng lên.

    - Độ phức tạp của nó phụ thuộc vào số lượng đường dẫn. Nó không thể kiểm tra các nút trùng lặp.

Thuật toán tìm kiếm hai chiều trong AI (Bidirectional Search Algorithm in AI)

Thuật toán này sẽ tìm kiếm về phía trước từ trạng thái ban đầu và lùi lại về sau từ trạng thái mục tiêu, cho đến khi cả hai gặp nhau để xác định một trạng thái chung thì thuật toán sẽ dừng.

 

Bên cạnh đó, đường dẫn của trạng thái ban đầu được nối với đường dẫn nghịch đảo của trạng thái mục tiêu. Mỗi một lần tìm kiếm chỉ được thực hiện tối đa một nửa tổng số đường dẫn.

Thuật toán tìm kiếm chi phí thống nhất trong AI (Uniform Cost Search Algorithm in AI)

Thuật toán này sẽ thực hiện sắp xếp theo cách tăng chi phí của đường dẫn đến một nút. Ngoài ra, thuật toán tìm kiếm chi phí thống nhất trong AI sẽ luôn luôn mở rộng nút có chi phí thấp nhất. Ta có thể nói nó khá giống với tìm kiếm Breadth-First, nếu mỗi lần chuyển đổi có cùng chi phí.

Thuật toán này sẽ khám phá các con đường theo thứ tự tăng dần của chi phí.

Nhược điểm:

    - Có thể có nhiều đường đi dài với chi phí ≤ C *.

    - Thuật toán tìm kiếm này sẽ phải khám phá tất cả các con đường.

Thuật toán tìm kiếm theo chiều sâu dần

Để thực hiện tìm kiếm này, chúng ta cần làm theo các bước: thực hiện tìm kiếm theo chiều sâu từ lúc bắt đầu đến cấp độ 1, và sau đó thực hiện tìm kiếm theo chiều sâu hoàn chỉnh đến cấp độ 2.

Hơn nữa, chúng ta phải tiếp tục quá trình tìm kiếm cho đến khi tìm ra giải pháp. Chúng ta phải tạo các nút liên tục cho đến khi các nút đơn được tạo ra. Ngoài ra, thuật toán này chỉ lưu ngăn xếp các nút.

Ngay sau khi chúng ta tìm thấy lời giải ở độ sâu d, thuật toán sẽ kết thúc, số nút được tạo ra ở độ sâu d là bd và ở độ sâu d-1 là bd-1.

Thuật toán tìm kiếm theo độ sâu

Thuật toán chiến lược tìm kiếm với tri thức bổ sung (Informed (Heuristic) Search Strategies)

Để tăng hiệu quả của thuật toán tìm kiếm, chúng ta cần bổ sung kiến ​​thức về vấn đề cụ thể. Chúng ta sẽ sử dụng điều này để giải quyết các vấn đề lớn, trong đó chúng ta sẽ có rất nhiều trạng thái có thể xảy ra.

I. Các chức năng đánh giá Heuristic

Heuristic được hiểu là các sự phỏng đoán, ước chừng. Chúng ta sẽ sử dụng hàm này để tính toán đường đi giữa hai trạng thái, trong đó, hàm này sẽ tạo ra một trò chơi xếp hình trượt (sliding-tiles games). Lúc đó, chúng ta phải tính toán bằng cách tính số hàng. Ngoài ra, các bước di chuyển của mỗi ô sẽ được thực hiện từ trạng thái mục tiêu của nó, và bạn nhớ là hãy thêm số lần di chuyển này cho tất cả các ô nhé!

II. Tìm kiếm Heuristic thuần túy

Theo thứ tự, nếu giá trị của các nút Heuristic các nút sẽ mở rộng, chúng sẽ tạo hai danh sách:

    - Đầu tiên, danh sách đóng của các nút đã được mở rộng

    - Thứ hai, một danh sách mở được tạo, mặc dù đó có thể là các nút bất ngờ

Một nút có giá trị Heuristic tối thiểu sẽ được mở rộng trong mỗi lần lặp. Ngoài ra, tất cả các nút con của nó sẽ được tạo và đặt trong danh sách đóng. Chúng tôi áp dụng hàm Heuristic này cho các nút con, do đó, tới cuối cùng, chúng ta phải đặt nó trong danh sách mở, theo giá trị Heuristic. Mặc dù vậy, chúng ta phải lưu con đường ngắn nhất và  loại bỏ những con đường dài hơn.

Thuật toán tìm kiếm A * trong AI

Chúng tôi có thể nói rằng A * Search là hình thức tốt nhất của tìm kiếm  theo lựa chọn tốt nhất (Best First Search). Ngoài ra, chúng còn giúp chúng ta tránh mở rộng các con đường, gây tốn kém. 

 

f (n) = g (n) + h (n)

 

Trong đó:

    - g (n) là chi phí để đến được nút

    - h (n), ước tính chi phí để đi từ nút đến mục tiêu

    - f (n) nó được định nghĩa là tổng chi phí ước tính của con đường từ n đến mục tiêu. Ngoài ra, chúng ta sẽ sử dụng hàng đợi ưu tiên bằng cách tăng f (n) để triển khai nó.

Thuật toán tìm kiếm đầu tiên tốt nhất của Greedy trong AI

Nút gần nhất với mục tiêu sẽ được mở rộng đầu tiên, mặc dù việc giải thích các nút phụ thuộc vào f (n) = h (n). Chúng ta sẽ thực hiện nó bằng cách sử dụng hàng đợi ưu tiên.

 

Nhược điểm: Chúng có thể bị mắc kẹt trong các vòng lặp, đây không phải là lựa chọn tối ưu.

Thuật toán tìm kiếm cục bộ trong AI

Đây là một trong các thuật toán tìm kiếm phổ biến cả trong hiện tại hoặc có thể là ở tương lai.

I. Giải thuật leo đồi trong AI (Hill-Climbing Search Algorithm in AI)

Chúng ta có thể bắt đầu thuật toán này với một giải pháp tùy ý cho một vấn đề. Ngoài ra, đây là một thuật toán lặp đi lặp lại. Do đó, thuật toán sẽ cố gắng tìm ra giải pháp tốt hơn bằng một phần tử duy nhất của giải pháp.

 

Mặc dù vậy, chúng tôi coi một thay đổi gia tăng giống như một giải pháp mới, tương tự như việc thay đổi sẽ tạo ra một giải pháp tốt hơn. Hơn nữa, chúng ta phải lặp lại phương pháp này liên tục cho đến khi không có cải tiến nào nữa.

 

Hàm này của bài toán sẽ luôn luôn trả về trạng thái là cực đại cục bộ:

 

inputs: problem, a problem

local variables: current, a node

neighbor, a node

current <-Make_Node(Initial-State[problem])

loop

do neighbor <- a highest_valued successor of current

if Value[neighbor] ≤ Value[current] then

return State[current]

current <- neighbor

end

II. Thuật toán tìm kiếm chùm cục bộ trong AI (Local Beam Search Algorithm in AI)

Trong thuật toán này, chúng ta phải giữ k số trạng thái tại bất kỳ thời điểm nào. Khi bắt đầu, chúng ta phải tạo các trạng thái một cách ngẫu nhiên. Hơn nữa, với hàm mục tiêu, chúng ta phải tính toán con số kế thừa của k trạng thái này. Cuối cùng, chúng sẽ dừng lại nếu bất kỳ giá trị kế thừa nào là giá trị lớn nhất của hàm mục tiêu.

 

Nếu không, chúng ta phải đặt (k trạng thái ban đầu và k số trạng thái kế tiếp của các trạng thái = 2k) trong một nhóm. Một nhóm sau đó được sắp xếp theo số. Hơn nữa, chúng ta phải chọn k trạng thái cao nhất làm trạng thái ban đầu mới. Quá trình này sẽ tiếp tục liên tục cho đến khi đạt đến giá trị lớn nhất .

 

function BeamSearch( problem, k), returns a solution state.

start with k randomly generated states

loop

generate all successors of all k states

if any of the states = solution, then return the state

else select the k best successors

end

Giải thuật luyện thép trong AI (Simulated Annealing Algorithm)

Quá trình này là làm nóng và làm lạnh một kim loại để thay đổi cấu trúc bên trong của nó. Việc thực hiện các hành động này để sửa đổi các đặc tính vật lý của nó được gọi là quá trình ủ. Ngay sau khi kim loại nguội đi, nó sẽ hình thành một cấu trúc mới. Lúc đó, kim loại sẽ giữ nguyên các đặc tính mới thu được của nó, mặc dù chúng ta phải làm cho nhiệt độ thay đổi trong quá trình ủ mô phỏng.

Đầu tiên, chúng ta phải cài đặt nhiệt độ cao. Sau đó, để nó được "nguội" từ từ với thuật toán lặp lại liên tục. Hơn nữa, nếu có nhiệt độ cao, thuật toán sẽ chấp nhận các giải pháp kém hơn với tần số cao.

Start

Initialize k = 0; L = integer number of variables;

From i → j, search the performance difference Δ.

If Δ <= 0 then accept else if exp(-Δ/T(k)) > random(0,1) then accept;

Repeat steps 1 and 2 for L(k) steps.

k = k + 1;

Repeat steps 1 through 4 till the criteria matches.

End

Ví dụ cụ thể: Thuật toán tìm đường du lịch ngắn và tiết kiệm nhất

Mục tiêu chính của vấn đề này là tìm một tour du lịch giá rẻ. Chúng ta có thể thực hiện điều này bằng cách cùng nhau bắt đầu từ một thành phố, thăm tất cả các thành phố trên đường đi một lần và kết thúc tại cùng một thành phố xuất phát.

Start

Find out all (n -1)! Possible solutions, where n is the total number of cities.

Further, determine the minimum cost by finding out the cost of each of these (n -1)! solutions.

Finally, keep the one with the minimum cost.

End

 

Thuật toán tìm kiếm con đường du lịch ngắn và tiết kiệm nhất

Phần kết luận

Trong phần cẩm nang AI này, chúng ta đã cùng nhau nghiên cứu về một số thuật toán tìm kiếm phổ biến trong AI. Ngoài ra, chúng ta đã cùng nhau tìm hiểu về các kỹ thuật đằng sau những phương pháp này cũng như cách sử dụng thực tế của nó. 

 

 

>> Xem tiếp: Bài 15: Artificial Neural Network là gì? Cấu trúc, cách hoạt động và ứng dụng của mô hình này

>> Xem lại: Bài 13: Thành phần và ứng dụng của Robot AI

 

 

 

Để tìm hiểu thêm về giải pháp Giám sát & Ứng dụng AI, vui lòng liên hệ đến Viettel IDC:

 

- Hotline: 1800.8088 (miễn phí cước gọi)

- Fanpage: https://www.facebook.com/viettelidc

- Website: https://viettelidc.com.vn