Tìm Hiểu Về Các Thuật Toán Tìm Kiếm: UCS, A*, và Học Máy

Thuật toán tìm kiếm đóng vai trò cốt lõi trong hệ thống trí tuệ nhân tạo. Hệ thống tiếp nhận bài toán dưới dạng không gian trạng thái. 73 trang.

• Đề tài: Tìm Hiểu Các Thuật Toán Tìm Kiếm Trong Trí Tuệ Nhân Tạo

Mục lục chi tiết

• 1. Chương 1: Search
• 1.1. UCS
• 1.2. Greedy Best first search
• 1.3. A*
• 1.4. CSP
• 1.5. GSP1
• 1.6. GTS1
• 1.7. GSP2
• 1.8. GTS2
• 2. Chương 2: Tri thức + lập luận
• 2.1. Logic mệnh đề
• 2.2. CM các hệ logic
• 2.3. Logic bậc nhất
• 2.4. Lập luận ko chắc chắn
• 3. Chương 3: Học máy
• 3.1. Các pp học máy
• 3.2. Học qua logic
• 3.3. Học từ quan sát
• 3.4. Hunt (xem học từ quan sát trước)
• 3.5. ID3 (Quinlan)
• 3.6. Mạng ngữ nghĩa
• 3.7. Mạng noron nhân tạo

Tóm tắt

I. Tổng quan về các thuật toán tìm kiếm trong trí tuệ nhân tạo

Thuật toán tìm kiếm đóng vai trò cốt lõi trong hệ thống trí tuệ nhân tạo. Hệ thống tiếp nhận bài toán dưới dạng không gian trạng thái. Mỗi trạng thái đại diện cho một cấu hình cụ thể của môi trường. Các hành động hợp lệ giúp chuyển đổi giữa các trạng thái khác nhau. Mục tiêu cuối cùng là xác định chuỗi hành động dẫn tới trạng thái đích với chi phí thấp nhất. Nhóm thuật toán tìm kiếm cơ bản chia thành hai loại chính gồm tìm kiếm mù và tìm kiếm có thông tin. Tìm kiếm mù hoạt động không cần thông tin phụ trợ về khoảng cách tới đích. Ngược lại, tìm kiếm có thông tin sử dụng hàm heuristic để định hướng đường đi. Quá trình duyệt trạng thái thường tổ chức dưới dạng cây tìm kiếm hoặc đồ thị. Hàng đợi ưu tiên quản lý danh sách các nút chờ mở rộng theo mức độ ưu tiên. Thuật toán đánh giá chất lượng dựa trên bốn tiêu chí gồm tính đầy đủ, độ phức tạp thời gian, độ phức tạp không gian và tính tối ưu. Việc lựa chọn phương pháp tìm kiếm phù hợp ảnh hưởng trực tiếp đến hiệu năng của toàn bộ hệ thống trí tuệ nhân tạo.

1.1. Thuật toán tìm kiếm chi phí đồng nhất UCS

Thuật toán Uniform Cost Search mở rộng nút có chi phí đường đi thấp nhất từ trạng thái gốc. Thuật toán sử dụng cấu trúc hàng đợi ưu tiên để lưu trữ các trạng thái biên. Mỗi nút gán giá trị chi phí tích lũy g(n) từ điểm khởi đầu. Thuật toán kiểm tra điều kiện đích khi lấy nút ra khỏi hàng đợi thay vì lúc tạo nút. Cơ chế này đảm bảo tìm thấy đường đi tối ưu nếu chi phí mỗi bước lớn hơn một ngưỡng dương cố định. Khi áp dụng cho đồ thị giao thông thực tế, UCS duyệt các nút theo bán kính chi phí tăng dần. Thuật toán có tính đầy đủ và đạt giải pháp tối ưu toàn cục. Tuy nhiên, mức độ tiêu tốn bộ nhớ của UCS tăng theo cấp số nhân khi không gian tìm kiếm mở rộng quá lớn.

1.2. Thuật toán tìm kiếm tham lam Greedy Best First

Thuật toán Greedy Best-First Search lựa chọn trạng thái kế tiếp dựa hoàn toàn vào hàm ước lượng khoảng cách h(n). Hàm heuristic dự đoán khoảng cách ngắn nhất từ trạng thái hiện tại đến trạng thái mục tiêu. Thuật toán luôn ưu tiên mở rộng nút có giá trị h(n) nhỏ nhất. Phương pháp này giúp tác nhân tiến nhanh về phía đích trong điều kiện thuận lợi. Tốc độ thực thi của thuật toán thường vượt trội so với các phương pháp tìm kiếm mù. Dẫu vậy, Greedy Best-First Search dễ rơi vào bẫy tối ưu cục bộ hoặc vòng lặp vô hạn trên đồ thị có chu trình. Thuật toán không đảm bảo tính tối ưu vì bỏ qua chi phí thực tế g(n) đã tích lũy từ điểm xuất phát. Đường đi tìm được đôi khi có tổng chi phí rất cao.

II. Thách thức lớn của thuật toán tìm kiếm trong trí tuệ nhân tạo

Quá trình giải quyết bài toán phức tạp bằng thuật toán tìm kiếm đối mặt với nhiều trở ngại kỹ thuật lớn. Thách thức hàng đầu xuất phát từ sự bùng nổ tổ hợp trong không gian trạng thái. Khi số lượng hành động và độ sâu bài toán tăng lên, số lượng nhánh phát triển theo hàm mũ. Bộ nhớ hệ thống nhanh chóng cạn kiệt trước khi thuật toán tiếp cận trạng thái mục tiêu. Độ trễ tính toán gia tăng nghiêm trọng, cản trở các tác vụ đòi hỏi phản hồi thời gian thực. Bên cạnh hạn chế tài nguyên phần cứng, việc xây dựng hàm đánh giá chuẩn xác đòi hỏi độ chính xác toán học khắt khe. Nếu hàm ước lượng sai lệch, thuật toán dễ đi lạc hướng hoặc bỏ qua đường đi tối ưu. Đồ thị chứa các chu trình lặp lại khiến tác nhân tiêu tốn năng lượng xử lý vô ích. Thêm vào đó, thông tin môi trường trong nhiều bài toán thực tế thường thiếu sót hoặc nhiễu loạn. Các ràng buộc phức tạp giữa các biến khiến việc tìm kiếm lời giải khả thi trở nên khó khăn. Những rào cản này buộc các nhà nghiên cứu phải phát triển các nguyên lý kiểm soát nhánh tìm kiếm thông minh hơn.

2.1. Hiện tượng bùng nổ tổ hợp trạng thái và giới hạn bộ nhớ

Hiện tượng bùng nổ không gian trạng thái xảy ra khi hệ số phân nhánh b và độ sâu d tăng cao. Số lượng nút cần kiểm tra đạt ngưỡng b mũ d. Thuật toán tìm kiếm theo chiều rộng hoặc chi phí đồng nhất phải lưu toàn bộ các nút biên trong RAM. Khi không gian tìm kiếm mở rộng hàng triệu trạng thái, máy tính lập tức quá tải bộ nhớ. Hiện tượng nghẽn cổ chai xuất hiện khiến quá trình xử lý dừng lại trước khi tìm ra kết quả. Tác nhân không thể hoàn thành nhiệm vụ nếu thiếu cơ chế cắt tỉa nhánh cây. Do đó, việc giới hạn phạm vi duyệt và tối ưu dung lượng lưu trữ là yêu cầu sống còn cho các bài toán quy mô lớn.

2.2. Nguy cơ thiếu nhất quán của hàm ước lượng Heuristic

Hàm heuristic h(n) đóng vai trò kim chỉ nam trong tìm kiếm có thông tin. Tuy vậy, việc thiết kế hàm heuristic thỏa mãn tính chấp nhận được và tính nhất quán rất phức tạp. Tính chấp nhận được đòi hỏi giá trị h(n) không bao giờ đánh giá cao hơn chi phí thực tế tới đích. Tính nhất quán yêu cầu hàm thỏa mãn bất đẳng thức tam giác giữa các nút kế tiếp. Nếu hàm ước lượng vi phạm tính nhất quán, thuật toán A* trên đồ thị có thể trả về đường đi dưới chuẩn. Hệ thống buộc phải mở rộng lại các nút đã duyệt, dẫn đến lãng phí thời gian tính toán. Sai số heuristic làm lệch hướng đi tối ưu và phá vỡ tính đúng đắn của toàn bộ thuật toán.

III. Giải pháp tối ưu cho thuật toán tìm kiếm trong trí tuệ nhân tạo

Để khắc phục tình trạng bùng nổ tổ hợp, trí tuệ nhân tạo kết hợp chi phí thực tế với tri thức bổ trợ. Thuật toán tìm kiếm A* là giải pháp tiêu biểu cho bài toán tìm đường đi ngắn nhất. Thuật toán tính toán hàm lượng giá f(n) bằng tổng chi phí đã đi g(n) và khoảng cách ước lượng h(n). Khi hàm heuristic thỏa mãn tính chấp nhận được trên cây hoặc tính nhất quán trên đồ thị, A* luôn tìm ra giải pháp tối ưu toàn cục. Thuật toán loại bỏ các nhánh kém tiềm năng, giảm thiểu đáng kể số lượng trạng thái cần duyệt. Đối với các bài toán có nhiều điều kiện ràng buộc ngặt nghèo, mô hình CSP cung cấp khung giải pháp chặt chẽ. Hệ thống biểu diễn bài toán dưới dạng tập hợp biến số, miền giá trị và các điều kiện ràng buộc. Các chiến lược thông minh như MRV ưu tiên chọn biến có ít giá trị khả dĩ nhất. Trong khi đó, heuristic Degree chọn biến có nhiều mối liên kết nhất để sớm phát hiện xung đột. Kỹ thuật lan truyền ràng buộc liên tục thu hẹp không gian tìm kiếm thông qua kiểm tra tính nhất quán cung. Sự phối hợp giữa thuật toán tìm kiếm và tri thức logic nâng cao hiệu suất xử lý vượt trội.

3.1. Thuật toán tìm kiếm A kết hợp hàm đánh giá toàn diện

Thuật toán A* mở rộng nút dựa trên hàm đánh giá f(n) = g(n) + h(n). Trong đó g(n) là chi phí chính xác từ điểm xuất phát đến nút hiện tại. Giá trị h(n) là ước tính chi phí tối thiểu từ nút hiện tại đến đích. Thuật toán duy trì hai tập hợp gồm danh sách mở chứa các nút chờ duyệt và danh sách đóng chứa các nút đã mở rộng. Nhờ kết hợp cả quá khứ lẫn tương lai, A* chỉ tập trung duyệt các trạng thái hứa hẹn nhất. Nếu hàm h(n) nhất quán, thuật toán không bao giờ cần mở rộng lại một trạng thái trong danh sách đóng. A* đạt hiệu quả tối đa về số lượng nút cần mở rộng để tìm ra giải pháp tối ưu.

3.2. Phương pháp giải bài toán thỏa mãn ràng buộc CSP

Bài toán thỏa mãn ràng buộc định nghĩa mục tiêu bằng việc gán giá trị hợp lệ cho mọi biến số. Thuật toán quay lui là kỹ thuật nền tảng để giải quyết CSP. Để tăng tốc độ, hệ thống tích hợp phương pháp MRV nhằm ưu tiên gán giá trị cho biến có ít lựa chọn còn lại nhất. Chiến lược này kích hoạt thất bại sớm nếu bài toán rơi vào ngõ cụt. Tiếp theo, kỹ thuật Degree Heuristic phá vỡ thế cân bằng bằng cách chọn biến ràng buộc với nhiều biến chưa gán nhất. Đồng thời, thuật toán AC-3 kiểm tra tính nhất quán cung để loại bỏ các giá trị không hợp lệ khỏi miền xác định. Nhờ đó, không gian tìm kiếm được tinh giản nhanh chóng và chính xác.

IV. Ứng dụng thực tế của thuật toán tìm kiếm trong trí tuệ nhân tạo

Các thuật toán tìm kiếm tạo tiền đề vững chắc cho hàng loạt ứng dụng thông minh trong đời sống hiện đại. Trong ngành giao thông vận tải, thuật toán dẫn đường xử lý dữ liệu bản đồ phức tạp để điều phối phương tiện tránh tắc nghẽn. Các hệ thống định vị vệ tinh GPS liên tục áp dụng biến thể A* nhằm vạch ra lộ trình di chuyển tối ưu với chi phí năng lượng thấp nhất. Bên cạnh vận tải, kỹ thuật giải bài toán thỏa mãn ràng buộc CSP đóng vai trò then chốt trong điều phối lịch trình bay và bố trí dây chuyền sản xuất công nghiệp. Ngành công nghiệp trò chơi điện tử vận dụng thuật toán tìm kiếm để lập trình trí thông minh cho các nhân vật giả lập, giúp nhân vật điều hướng mượt mà trong môi trường ảo 3D. Hơn thế nữa, xu hướng kết hợp thuật toán tìm kiếm cổ điển với học máy đang mở ra hướng phát triển đột phá. Mạng nơ-ron học các hàm heuristic tự động từ dữ liệu thực tế, giảm thiểu thời gian tính toán thủ công. Sự tiến hóa liên tục của các phương pháp tìm kiếm khẳng định vị trí trung tâm của lĩnh vực này trong sự phát triển tương lai của trí tuệ nhân tạo toàn cầu.

4.1. Ứng dụng điều hướng lộ trình và logistics thông minh

Các ứng dụng bản đồ số phụ thuộc hoàn toàn vào thuật toán tìm kiếm để xử lý lưu lượng giao thông theo thời gian thực. Hệ thống coi mỗi giao lộ là một nút và mỗi tuyến đường là một cung có trọng số. Trọng số thay đổi linh hoạt dựa vào độ dài quãng đường và mật độ phương tiện. Thuật toán tìm kiếm A* quét qua hàng triệu cung đường trong vài mili giây để đưa ra lộ trình ngắn nhất. Trong lĩnh vực hậu cần, kỹ thuật tìm kiếm giúp tối ưu hóa luồng hàng hóa và tuyến xe giao hàng. Các doanh nghiệp thương mại điện tử cắt giảm đáng kể nhiên liệu và thời gian vận chuyển nhờ các giải pháp định tuyến thông minh này.

4.2. Tích hợp giải thuật tìm kiếm với mô hình học máy

Sự kết hợp giữa giải thuật tìm kiếm truyền thống và học máy tạo nên bước nhảy vọt trong công nghệ trí tuệ nhân tạo. Thay vì thiết kế hàm heuristic thủ công, các kỹ sư sử dụng mạng nơ-ron sâu để ước lượng chi phí chính xác hơn. Thuật toán tìm kiếm cây Monte Carlo kết hợp mạng học sâu đã mang lại chiến thắng lịch sử trong các trò chơi cờ phức tạp như Cờ vây. Ngoài ra, học tăng cường tận dụng cấu trúc không gian trạng thái từ thuật toán tìm kiếm để rèn luyện chính sách hành động tối ưu cho robot tự hành. Sự cộng hưởng này giải quyết triệt để hạn chế về độ phức tạp tính toán và nâng cao khả năng khái quát hóa của hệ thống.

Nội dung chính

Tổng quan về giáo trình

Tài liệu "Tìm Hiểu Các Thuật Toán Tìm Kiếm Trong Trí Tuệ Nhân Tạo" là đề cương bài giảng và tài liệu học tập chuẩn hóa thuộc khối kiến thức cơ sở ngành và chuyên ngành của chương trình đào tạo Khoa học Máy tính, Kỹ thuật Phần mềm và Công nghệ Thông tin ở bậc đại học. Căn cứ vào các chỉ dấu nội dung và cấu trúc trình bày, giáo trình được thiết kế theo định hướng tiếp cận CDIO (Conceive – Design – Implement – Operate), nhằm chuẩn hóa năng lực giải quyết vấn đề bằng tính toán của sinh viên.

Mục tiêu học tập (learning outcomes) của tài liệu tập trung vào ba trọng tâm:

1. Nắm vững bản chất toán học và cơ chế vận hành của các thuật toán tìm kiếm không gian trạng thái từ cơ bản đến nâng cao.
2. Nắm vững phương pháp biểu diễn tri thức và cơ chế suy diễn hình thức thông qua hệ thống logic mệnh đề, logic bậc nhất và logic mờ.
3. Tiếp cận các nguyên lý căn bản của học máy, phân loại mô hình học và xử lý các bài toán quyết định dựa trên dữ liệu.

Cấu trúc giáo trình đi theo lộ trình sư phạm chặt chẽ: khởi đầu từ việc mô hình hóa không gian trạng thái và thuật toán tìm kiếm, tiến đến bài toán thỏa mãn ràng buộc (CSP), biểu diễn tri thức thông qua các hệ thống suy luận logic hình thức, xử lý tri thức không chắc chắn bằng tập mờ, và kết thúc ở các mô hình học thích nghi. Điểm đặc thù của tài liệu là phương pháp tiếp cận trực diện vào cơ chế thực thi thuật toán: mỗi mô hình lý thuyết đều đi kèm công thức toán học tường minh, cấu trúc dữ liệu tương ứng (như hàng đợi ưu tiên PQ), và các kịch bản truy vết từng bước (trace execution) trên các đồ thị bài toán kinh điển.

---

Nội dung kiến thức cốt lõi

Các chương và chủ đề chính

Tài liệu được phân chia thành các cụm chuyên đề logic với tính liên kết tuần tự:

[Tìm kiếm không gian trạng thái & Heuristic] 
[Bài toán thỏa mãn ràng buộc (CSP)] 
[Tri thức & Lập luận Logic (Mệnh đề & Bậc nhất)] 
[Lập luận trong môi trường không chắc chắn (Fuzzy Logic)] 
[Nhập môn Học máy (Machine Learning)]

1. Không gian tìm kiếm và thuật toán tìm kiếm (Search Strategies)

• Tìm kiếm mù (Uninformed Search): Thuật toán tìm kiếm chi phí đồng nhất (Uniform Cost Search - UCS), theo dõi trạng thái hàng đợi ưu tiên PQ (Priority Queue). Điển hình là bài toán tìm đường trên bản đồ Romania từ đỉnh xuất phát Arad đến đích Bucharest với tổng chi phí tối ưu là 418 thông qua hành trình Arad – Sibiu – Rimnicu Vilcea – Pitesti – Bucharest.
• Tìm kiếm Heuristic có thông tin (Informed Search):
  • Greedy Best-First Search (GBFS) với hàm đánh giá $f(n) = h(n)$.
  • Thuật toán A* với hàm đánh giá $f(n) = g(n) + h(n)$.
  • Điều kiện chuẩn của heuristic: Tính chấp nhận được (Admissible: $h(n) \le h^*(n)$) và tính nhất quán (Consistent/Monotonicity: $h(n) \le c(n, a, n') + h(n')$ tuân theo bất đẳng thức tam giác). Mọi heuristic nhất quán đều chấp nhận được.
  • Các giải thuật tìm kiếm cục bộ và heuristic bổ trợ: Giải thuật Leo đồi (Hill Climbing), GTS1 và GTS2 (Greedy Traveling Salesman) giải bài toán người bán hàng với chi phí cực tiểu hóa qua các chu trình xuất phát khác nhau.
  • Ứng dụng giải các bài toán kinh điển: Bài toán 8-puzzle với hàm khoảng cách Manhattan $|x_{\text{đích}} - x_n| + |y_{\text{đích}} - y_n|$ và hàm số ô sai vị trí $h_1(a,b) = \sum \delta(a_{ij}, b_{ij})$; Bài toán Tháp Hà Nội với số bước chuyển tối ưu $2^n - 1$.

2. Bài toán thỏa mãn ràng buộc (Constraint Satisfaction Problems - CSP)

• Định nghĩa hình thức: Tập biến ($X$), miền giá trị ($D$), tập ràng buộc ($C$) dạng tường minh hoặc ngầm định.
• Các kỹ thuật Heuristic chọn biến và giá trị: MRV (Minimum Remaining Values - ưu tiên chọn biến có miền giá trị còn lại nhỏ nhất) và DH (Degree Heuristic - chọn biến tham gia vào nhiều ràng buộc nhất).
• Đặc tả và đồ thị hóa ràng buộc: Mô hình hóa bài toán lập thời khóa biểu thực tế cho 5 lớp học ($C_1, C_2, C_3, C_4, C_5$) và 3 giáo sư ($A, B, C$) dựa trên xung đột thời gian giảng dạy ($C_1 \neq C_2, C_2 \neq C_3, C_2 \neq C_4, C_3 \neq C_4$), lý giải ưu thế tính toán khi cấu trúc đồ thị suy biến về dạng cây.

3. Tri thức và lập luận bằng Logic mệnh đề (Propositional Logic)

• Cú pháp và ngữ nghĩa: Công thức dạng chuẩn (WFF), bảng chân trị, khái niệm thỏa mãn được (satisfiable) và hợp lệ (valid).
• Độ ưu tiên toán tử logic: Thứ tự thực thi chuẩn từ cao xuống thấp: Phủ định ($\neg$), Hội ($\wedge$), Tuyển ($\vee$), Kéo theo ($\Rightarrow$), Tương đương ($\Leftrightarrow$).
• Quan hệ suy dẫn (Entailment): $KB \models \alpha$ khi và chỉ khi mọi mô hình làm cho cơ sở tri thức $KB$ đúng cũng làm cho $\alpha$ đúng.
• Hệ thống luật suy diễn tự nhiên: Modus Ponens, Modus Tollens, And-Introduction, And-Elimination.
• Mệnh đề Horn và suy diễn tiến (Forward Chaining): Dạng hội của các literal với tối đa một literal khẳng định ($\neg A \vee \neg B \vee C \equiv A \wedge B \Rightarrow C$).
• Chuyển đổi dạng hội chuẩn (CNF): Khử toán tử kéo theo, áp dụng luật De Morgan, phân phối phép tuyển qua phép hội.
• Cơ chế chứng minh: Thuật giải hợp giải Robinson (Resolution refutation) chứng minh phản chứng $KB \wedge \neg \alpha \vdash \text{False}$; Thuật giải Vương Hạo (Wang's algorithm / Harvard method) thông qua tách dòng biến đổi tương đương ngữ nghĩa.

4. Logic bậc nhất (First-Order Logic - FOL)

• Cú pháp mở rộng: Hằng, biến, hàm, ký hiệu vị từ (predicates), lượng từ với mọi ($\forall$) và tồn tại ($\exists$).
• Kỹ thuật chuẩn hóa: Dạng mệnh đề (Clausal form), kỹ thuật Skolem hóa (Skolemization) để khử lượng từ tồn tại bằng hằng hoặc hàm Skolem, bỏ lượng từ phổ quát.
• Cơ chế hợp giải bậc nhất: Phép thế cơ sở, giải thuật đồng nhất (Unification) và tìm phép đồng nhất tổng quát nhất (Most General Unifier - MGU). Minh họa qua bài toán suy luận quan hệ họ hàng (cha, con, ông nội) và bài toán logic câu đố Jack - Tuna - Curiosity.

5. Lập luận không chắc chắn và Logic mờ (Fuzzy Logic)

• Lý thuyết tập mờ: Hàm liên thuộc $\mu_A(x) \in [0, 1]$, vết cắt alpha ($\alpha$-cut), các vùng tập lồi (core), vùng hỗ trợ (support), vùng biên (boundary), biến ngôn ngữ.
• Toán tử mờ: Các phép bù mờ (chuẩn $1-a$, ngưỡng, cosin, Sugeno), phép giao mờ (T-norm: min, tích đại số, bounded difference), phép hội mờ (S-norm: max, tổng đại số, bounded sum).
• Hệ suy diễn mờ: Quy trình 4 bước gồm Mờ hóa (Fuzzification) $\to$ Ước lượng luật (Rule evaluation) $\to$ Tổng hợp (Aggregating) $\to$ Giải mờ (Defuzzification) bằng phương pháp trọng tâm (Centroid).
• Hai mô hình mờ chính: Mô hình Mamdani (kết luận dạng tập mờ) và mô hình Sugeno bậc không (Zero-order Sugeno: kết luận là hằng số hoặc hàm xác định).

6. Tổng quan về Học máy (Machine Learning)

• Định nghĩa của Herbert Simon: Hệ thống học là hệ thống thực hiện các biến đổi thích nghi nhằm cải thiện hiệu quả xử lý tác vụ tương tự trong các chu kỳ sau.
• Ba mô hình học máy: Học có giám sát (Supervised learning), Học không giám sát (Unsupervised learning), và Học tăng cường (Reinforcement learning).
• Cấp độ nhận thức học máy: Cấp độ ghi nhớ (dự đoán lại mẫu đã thấy) minh họa bằng tập dữ liệu dự báo thời tiết chơi Tennis (Play Tennis với các thuộc tính: Quang cảnh, Nhiệt độ, Độ ẩm, Gió).
• Các phương pháp được định vị: Cây quyết định ID3 của Quinlan, thuật toán Hunt, Mạng ngữ nghĩa và Mạng nơ-ron nhân tạo.

Kiến thức nền tảng được xây dựng

Tài liệu củng cố nền tảng toán rời rạc thông qua lý thuyết đồ thị và ma trận quan hệ; xây dựng tư duy logic hình thức nghiêm ngặt thông qua cú pháp và ngữ nghĩa toán học; đồng thời cung cấp nền tảng giải tích và đại số mờ để mô hình hóa sự bất định trong các hệ thống thông minh.

Kỹ năng phát triển

• Kỹ năng kỹ thuật: Lập trình giải thuật tìm kiếm trạng thái, chuyển đổi biểu thức logic về dạng chuẩn hội CNF, thực hiện các phép thế và hợp nhất MGU trên cây cú pháp.
• Kỹ năng phân tích: Đánh giá tính chấp nhận được và tính nhất quán của hàm Heuristic, phân tích độ phức tạp thời gian/không gian dựa trên nhánh rẽ ($b$) và độ sâu ($d$), đặc tả ràng buộc ngầm định của các bài toán phân bổ tài nguyên.
• Kỹ năng giải quyết vấn đề: Chuyển dịch bài toán thực tế (lập lịch biểu, điều hướng đường đi, bài toán suy diễn tri thức) thành bài toán quy chuẩn của Trí tuệ Nhân tạo.

---

Phương pháp giảng dạy và học tập

Giáo trình triển khai phương pháp sư phạm diễn dịch kết hợp quy nạp, đặt trọng tâm vào việc phân tích các ca giải mẫu (worked examples) trước khi giao bài tập thực hành.

Bài tập và kịch bản ví dụ

Giáo trình thiết kế chuỗi bài toán mẫu đóng vai trò tiêu chuẩn kiểm thử (benchmarks):

• Bài toán không gian tìm kiếm: Bản đồ Romania cung cấp bảng khoảng cách đường chim bay đến Bucharest (như Sibiu: 253, Fagaras: 176, Pitesti: 100) để sinh viên tính toán từng bước giá trị $f(n)$ của giải thuật A* và GBFS.
• Bài toán biến đổi trạng thái: Trò chơi 8-puzzle và Tháp Hà Nội giúp người học trực quan hóa cây tìm kiếm không gian trạng thái.
• Bài tập quy chuẩn CSP: Bài toán phân chia 5 lớp học và 3 giáo sư yêu cầu sinh viên phát biểu biến, miền giá trị và vẽ đồ thị xung đột.

Phương pháp suy luận hình thức

Người học được rèn luyện quy trình biến đổi hình thức qua từng bảng bước giải:

• Bảng suy diễn tự nhiên gồm 7 bước chứng minh công thức mục tiêu $S$ từ các tiền đề $P \wedge Q$, $P \Rightarrow R$, $Q \wedge R \Rightarrow S$.
• Bảng thuật giải Robinson và Vương Hạo theo dõi việc triệt tiêu từng cặp literal đối ngẫu cho đến khi sinh ra mệnh đề rỗng hoặc đạt trạng thái chứng minh xong.
• Quy trình 4 bước của suy diễn mờ với bài toán ước lượng rủi ro dự án (project_funding, project_staffing $\to$ risk).

Phương pháp đánh giá và tự học

Hình thức kiểm tra được thiết kế theo thang điểm định lượng rõ ràng (ví dụ: Question 2 (0.5pt), Question 3 (0.5pt) về kiểm tra tính admissible và consistent của đồ thị có hướng). Mỗi câu hỏi yêu cầu giải thích ngắn gọn, chỉ đích danh điểm vi phạm (như vi phạm tính nhất quán tại đỉnh $S$ hoặc đỉnh $B$). Người học cần tự viết lại quá trình mở đỉnh (list of expanded states) và đường đi kết quả (path returned) để đối chiếu trực tiếp với bảng đáp án chuẩn.

---

Điểm nổi bật và cập nhật

1. Tính gắn kết với chuẩn đào tạo CDIO: Tài liệu tích hợp các nhãn chuẩn hóa CDIO xuyên suốt các slide bài giảng, bảo đảm nội dung bám sát cấu trúc đào tạo chuẩn hóa quốc tế của khối ngành kỹ thuật.
2. Cân bằng giữa AI cổ điển (Symbolic AI) và Tiếp cận mờ/học máy: Giáo trình kết nối liền mạch từ các phương pháp xử lý logic tất định (logic mệnh đề, logic bậc nhất, thuật giải Robinson, Vương Hạo) sang các phương pháp tính toán mềm (Soft Computing: logic mờ Mamdani/Sugeno) và các mô hình học quy nạp (Herbert Simon, Quinlan ID3).
3. Hệ thống hóa các thuật toán tối ưu cục bộ và Heuristic đặc thù: Ngoài A* và GBFS tiêu chuẩn, tài liệu đưa vào các biến thể GTS1 và GTS2 cho bài toán chu trình người bán hàng, minh họa rõ nét cách chọn đỉnh xuất phát ảnh hưởng trực tiếp đến chất lượng chu trình và chi phí nghiệm.
4. Minh họa bài toán thực tế bằng đồ thị: Sử dụng các kịch bản thực tiễn gần gũi như bài toán lập thời khóa biểu phòng học của khoa công nghệ thông tin để giảng dạy lý thuyết CSP, thay vì chỉ dùng bài toán tô màu đồ thị trừu tượng.

---

Đối tượng sử dụng giáo trình

• Sinh viên đại học: Giáo trình phục vụ trực tiếp cho sinh viên năm thứ hai hoặc năm thứ ba chuyên ngành Khoa học Máy tính, Kỹ thuật Phần mềm, Hệ thống Thông tin và Trí tuệ Nhân tạo.
• Điều kiện tiên quyết (Prerequisites):
  • Toán rời rạc (lý thuyết đồ thị, đại số mệnh đề, quan hệ).
  • Cấu trúc dữ liệu và Giải thuật (hàng đợi ưu tiên, cây, đồ thị, độ phức tạp thuật toán).
  • Kỹ năng lập trình cơ bản (C++ hoặc Python để hiện thực hóa thuật toán).
• Giảng viên: Sử dụng tài liệu làm đề cương bài giảng chuẩn, cung cấp khung bài tập ví dụ trên lớp và ngân hàng câu hỏi kiểm tra tự luận từng phần (0.5 – 1.0 điểm).
• Người tự học và nghiên cứu viên: Tài liệu cung cấp bản tóm tắt công thức toán học, quy tắc biến đổi CNF, giải thuật tìm MGU và công thức toán tử mờ để tra cứu nhanh khi thiết kế các hệ thống chuyên gia hoặc thuật toán tìm kiếm.

---

Câu hỏi thường gặp

1. Giáo trình này tập trung vào AI cổ điển hay AI hiện đại?

Tài liệu bao quát nền tảng của AI cổ điển (Symbolic AI: tìm kiếm không gian trạng thái, CSP, logic suy diễn) và mở rộng sang tính toán bất định (Fuzzy Logic) cùng các khái niệm nền tảng của AI hiện đại (Machine Learning: Supervised, Unsupervised, Reinforcement Learning, ID3).

2. Cần chuẩn bị kiến thức nền tảng nào trước khi học tài liệu này?

Người học cần nắm chắc cấu trúc dữ liệu đồ thị, hàng đợi ưu tiên, các phép toán đại số Boole cơ bản và nguyên lý đệ quy. Kiến thức về giải tích cơ bản và đại số tuyến tính sẽ hỗ trợ việc tiếp cận phần suy diễn mờ và học máy.

3. Sự khác biệt cốt lõi giữa hai thuật toán tìm kiếm GBFS và A* là gì?

GBFS chỉ dựa trên hàm heuristic ước lượng chi phí đến đích $f(n) = h(n)$, dễ bị rơi vào bẫy tối ưu cục bộ. Trong khi đó, A* kết hợp thêm chi phí thực tế đã tích lũy từ gốc $g(n)$ theo công thức $f(n) = g(n) + h(n)$, đảm bảo tìm ra đường đi tối ưu nếu heuristic thỏa mãn điều kiện chấp nhận được (admissible).

4. Heuristic thế nào thì được coi là chấp nhận được (admissible) và nhất quán (consistent)?

Heuristic là chấp nhận được nếu nó không bao giờ đánh giá chi phí cao hơn chi phí thực tế tối ưu ($h(n) \le h^*(n)$). Heuristic là nhất quán nếu với mọi trạng thái $n$ và trạng thái kế tiếp $n'$ tạo bởi hành động $a$, ta có $h(n) \le c(n, a, n') + h(n')$. Tính nhất quán luôn kéo theo tính chấp nhận được.

5. Vì sao bài toán CSP có cấu trúc cây lại được ưu tiên giải quyết hơn đồ thị tổng quát?

CSP có cấu trúc cây (không có chu trình) có thể được giải quyết trong thời gian tuyến tính $O(n \cdot d^2)$ bằng thuật toán tương thích hướng (directional arc consistency), loại bỏ hoàn toàn hiện tượng bùng nổ tổ hợp quay lui (backtracking) thường gặp trên đồ thị ràng buộc có chu trình.

---

Kết luận

Tài liệu "Tìm Hiểu Các Thuật Toán Tìm Kiếm Trong Trí Tuệ Nhân Tạo" là một bản mô tả đề cương học thuật chặt chẽ, xác lập đầy đủ lộ trình kiến thức từ kỹ thuật tìm kiếm trạng thái, giải quyết bài toán ràng buộc, lập luận suy diễn hình thức cho đến suy luận mờ và học máy thích nghi. Lộ trình học tập đề xuất là nắm vững cơ chế tìm kiếm đồ thị trước khi chuyển sang kỹ thuật biểu diễn tri thức bằng logic và hệ mờ. Sinh viên cần bổ sung thêm các giáo trình tham khảo chuyên sâu về Trí tuệ Nhân tạo của Russell & Norvig cùng tài liệu thực hành thuật toán Machine Learning của Tom Mitchell để hoàn thiện kỹ năng hiện thực hóa mã nguồn trên máy tính.

Trích đoạn nội dung tài liệu

Search UCS Greedy Best first search A* CSP GSP1 GTS1 GSP2 GTS2 2.Tri thức + lập luận Logic mệnh đề CM các hệ logic Logic bậc nhất Lập luận ko chắc chắn 3. Học máy Các pp học máy Học qua logic Học từ quan sát Hunt (xem học từ quan sát trước) ID3 (Quinlan) Mạng ngữ nghĩa Mạng noron nhân tạo SEARCH Tìm kiếm mù UCS: - Ơn b+b—¬ oo 23 32 41 48 65 67 54 54 70 72 BÀI TẬP VÍ DỤ Eforie 94 Ï= BÀI TẬP VÍ DỤ “ÔN XS PQ = {((Arad, 0 TU CN CỬ a ees PQ= tee rent _75), (Timisoara, 118), (Sibiu, 140)} P= 4" ¥ PQ = {(Timisoara, 118), (Sibiu, 140), (Oradea, 146)} = dom = PQ = {((Sibiu, 140), (Oradea, 146), (Lugoj, 229)} a) {(Oradea, 146), (Rimnicu Vilcea, 220), (Lugoj, 229), (Faragas, PQ = {(Rimnicu Vilcea, 220), (Lugoj, 229), (Faragas, 239)} PQ = {(Lugoj, 229), (Faragas, 239), (Pitesti, 317), (Craiova, 366)} PQ = {(Faragas, 239), (Mehadia, 299), (Pitesti, 317), (Craiova, 366)} PQ = {(Mahadia, 299), (Pitesti, 317), (Craiova, 366), (Bucharest, 450)} PQ = {(Pitesti, 317), (Craiova, 366), (Dobreta, 374), (Bucharest, 450)} PQ = {((Craiova, 366), (Dobreta, 374), (Bucharest, 418)} PQ = {(Dobreta, 374), (Bucharest, 418)} PQ = {(Bucharest, 418)} PQ={} Arad — Sibiu — Rimnucu Vilcea — Pitesti + Bucharest. Chi phi: 418 (tim kiém Heuristic) Best-first search: tìm kiếm theo f(n), f(n) được xác định tuỳ thuộc vào loại thuật toán Gready Best-First search: f(n) = h(n) Greedy best-first search: An example (d) After expanding Fagaras Arad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Drobeta 242 Pitesti 100 Eforie 161 Rimnicu Vilcea 193 Fagaras 176 Sibiu 253 Giurgiu 1 Timisoara 329 Hirsova 151 Urziceni 80. lasi 22 Vaslui 199 Drabeta BH 120 " Gian Lugoj 244 Zerind 374 Craiova 17 Figure A simplified road map of part of Romania A* Search: f(n) = g(n) + h(n) h(n) chap nhận được: h(n) <= h*(n) h(n) nhat quan: nr) IS Consistent 1 Tor every noge n, every successor n OI n generated by any action a, h(n) < c(n,a,n’) + h(’) c(na,n’) h(n’) Triangle inequality Every consistent heuristic is also admissible.0pt) Consider the following search problem, represented as a graph.

The initial state is S and the only goal state is G. Assume ties resolve in such a way that states with earlier alphabetical order are expanded first. For each of the following search strategies, work out the list of expanded states as well as the path returned. Heuristic _ - DI EG 1/10/10 Algorithms | List of expanded states Path returned GBFS SAG SG A‘ SADBCG S$ ACG (graph search) SADBDG S BDG (tree search) Question 2 (0.5pt) Is the heuristic given in Question 1 admissible? Briefly explain.

Point out where the inadmissibility happens if there is any. TO TO sẽ Question 3 (0.5pt) Is the heuristic given in Question 1 consistent? Briefly explain. Point out where the inconsistency happens if there is any. The inconsistency happens at node S, 3.Or at node B.

Các bài toán thoả mãn ràng buộc CSP: MRV=3 DH=0 MRV = minimum remain values (chon bé nhat) DH = degree heuristic (chọn lớn nhất) CSP đồ thi: Giải Họ và tên: Mã số SV: Ngày: 1. Lập thời khóa biễu môn học k Bạn được giao nhiệm vụ lập thời khóa biểu cho các lớp Khoa bọc máy tính được tổ chức vào Thử hai, Thứ tự, và Thứ sáu. Có 5 lớp tổ chức vào những ngày này và 3 giáo sư sẽ giảng dạy các lớp đó, Mỗi giáo sự chỉ có thể giảng một lớp tại một thời điểm, Các lớp bao gồm. kớp 1 - Nhập môn lập trình: 08:00 — 09:00 sáng.

Lớp 2~ Nhập môn Trí tuệ nhận tạo; 08:30 — 09:30 sáng. Lớp 3 Xử lý ngôn ngữ tự nhiên: 09:00 - 10:00 sang. kớp 4 - Thị giác máy tính: 09:00 — 10:00 sáng. Lớp 5— Học máy: 10:30 — 11:30 sang Các giáo sự bao gồm 1.

Giáo sự A: đủ tiêu chuẩn dạy Lớp 1, 2 và 5 2. Giáo sự B: đủ tiêu chuẩn dạy Lớp 3, 4 và 5 3. Giáo sự C: đủ tiêu chuẩn dạy Lớp 1, 3 và 4 1. Phát biểu bài toán thỏa mãn ràng buộc (CSP).

Giả sử mỗi lớp là một biến, chỉ ra các miền giá tri và rang buds. Rang buộc cần được đặc tả một cách quy chuẩn và chính xác, và ràng buộc có thể ở dạng. tiềm ẳn thay vÌ tường minh. Vẽ đồ thi ràng buộc tượng ứng với CSP đang cần giải quyết.

CSP cia ban gần nhự có cấu trúc cây. Giải thích ngắn gọn (trong vòng 1 cậu) vì sao chúng ta ưa thich giải CSP có cầu trúc cây hơn? ao. Xây dựng vấn đề này như là một vấn đề CSP, trong đó mỗi lớp là một biến, nêu rõ các miễn. và các rằng buộc, các ràng buộc nên cụ thể và có thẻ là ngâm định.

Giải; Gọi các lớp là C1, C2, C3, C4 và C5. Ta có: =Ị C2 C4 Cúc ràng buộc: Cl#C2 C2#C3 C2#C4 C3#C4 b. Vệ đồ thị biểu diễn sự ràng buộc này. ứng với 6 OHO © GTS1 : (Greedy Traveling Saleman).

Ï= Vi DU GTS1 Khởi đầu: Tour ;= Ø,/Cost := 0, V := 1 Chon W = 2: Tour = {(1,2)}, Cost = 1 -' Chọn W = 4: Tour = {(1,2), (2,4)}, Cost = 4 | Chon W = 3: Tour = {(1,2), (2,4), (4,3)}, Cost = 5 _| Chon W = 5: Tour = {(1,2), (2,4), (4,3), (3,5)}, Cost = 7 Trở về: Tour = {(1,2), (2,4), (4,3), (3,5), (5,1)}, Cost = 1 Chu trình: 1 —› 2 —> 4 —› 3 —› 5 i phi l{13. ) l| -_ Chu trình: 1 —› 2 —> 5 —> 4 —› 3 — 1, chỉ phí là 11 a. GTS2: Ï= VÍ DỤ GTS2 —' Chọn P= 3 đỉnh xuất phát khác nhau, kết quả thực hiện của thuật toán là: 1 Chọn xuất phát từ thành phốC† =_ Chu trình:(1 >> 2 > 4 > 3 — 5 — 1, chỉ phí là 13. O Chon xuat phat tir thanh phố 2: = Chu trìnWfZj—› 1 —› 3 —» 4 —> 5 —> 2, chỉ phí là 11.

Chọn xuất phát từ thành phố ro « Chu trinhk}— 3 > §> 251-4, chi phí là 13. Cost(4)=13 ) = Cost=11<13=Cost(4) _ Vậy lời giải tốt nhất là xuất phát từ thành phó 2 với chi phí là 22 Leo déi 10 i cdio +9 N puzzle, heuristic trong hình »@ © 6 © vi DU + 4 ae Ta | Tớã độ x của ầích — Tọa độ x của n| +| Tọa độ y của đích — Tọa độ y của n| 1.) 2)8)3 z|s|3 1|6|4 1|®|4Ì sa 12345678 ils 7/5 LÌ 11000101 h=5, f“6 h=5, f=6 2 h,(a,b)= 3`ð(a,,b,) 2z|s|3 II io 1/4 14 e2 1 if a, #b, s 7|6|5 7 #/a,h) (eek. 2|1|14 714 1814 7Ì|6|5 6|5 76 7Ì|6|5 h=3, f=6 h=4, f=7 h=2} f= h=4, #7 Tháp hà nội A >(1 NC) >.—wmÙ-»ín s 3 4) + H_n NO) + `“ 12 Ï~ Ví dụ Bài toán Tháp Hà nội(11) 1 Tổng quát: n — đĩa (Tháp). s Số lần dịch chuyển: 2n-1 (Đệ qui) (2) _ Xét n=2.

4L || = lIl+ Xét tại c: A BC a ieee 0: 4+ it | h=2, f=2 1 to; hín)=. ; :0 LT LL ae ‘ h=3, fea m—. LfT1iITIL ” h=2, f=4 h=3, f=5 — LT (LTD h=2, f=5 h=3»=6 Lrzoz+2 | Tri thức và biểu diễn tri thức Logic mệnh đề 13 fi GIỚI THIỆU LOGIC ogie2'Khoa học về(ập luận, chứng minh và suy nghĩ Coates suy d diễn” | 68 di cụ để biễu diễn và xử lý tri thức của con người - Logic là một ngôn ngữ hình thức đề biễu diễn thông tin dưới dạng các kết luận có thể được đưa ra: Logic = Syntax + Semantics H Cú pháp (syntax): để xác định các mệnh đề (sentences) trong một ngôn ngữ H Ngữ nghĩa (semantics): để xác định “ý nghĩa" của các mệnh đề trong một ngôn ngữ “ Xác định sự đúng đắn của một mệnh đề | Vi du: Trong ngôn ngữ của toán học = (x+2 2 y) la mot ménh dé; —_ (x+y > {)) không phải là một mệnh đề 4 —___——@-o=~——""_ | 14 fi CU PHAP CUA MOT LOGIC Cú pháp = Ngôn ngữ + Ly thuyết chứng minh | Ng6n ngi (Language) {symbols O Cac ky hié pols), biéu thireéxpressions) , thuật ngữ <(terms), công thứeff6rm hợp lệ Lý thuyết chứng minh (Proof theory) H Tập hợp các luật suy diễn cho phép chứng minh (suy luận ra) các biểu thức — H Ví dụ: Luật suy diễn any plus zero - any ' Một định lý (theorem) là một mệnh đề logic cần chứng minh Việc chứng minh một định lý không cần phải xác định ngữ nghĩa (interpretation) của các ký hiệu! TT Syntax 15 fi~ NGU’ NGHIA CUA MOT LOGIC Ngữ nghĩa = Ý nghĩa (diễn giải) của các ký hiệu H ví dụ c * Kone) nghĩa là 1 Ñ) — “_I(plus) nghĩa là phép cộng(ết-N x N —› N - l(equal) nghĩa là phép so sánh bằng = : N xN —› {frue, false} = Kone plus one equal two) nghĩa là true Nếu diễn giải của một biểu thức là đúng (true), chúng ta nói rằng phép diễn giải này là một mô hình (model) của biểu thức Một biểu thức đúng đối với bất kỳ phép diễn giải nào thì được gọi là một biểu thức đúng đắn (valid) 1= NOTA 5 Semantics Tinh bao ham 16 | Ï= TÍNH BAO HÀM Tính bao hàm có nghĩa là một cái gì đó tuân theo (bị hàm chứa ý nghĩa bởi) một cái gì khác: Cơ sở tri thức — KB: bao hàm (hàm chứa) mệnh đề š ` > 4 ` “. a ` ơ nếu và chỉ nếu ơ là đúng trong mọi mô hinh (thé giới) mà trong đó KB là đúng — Tức là: nếu KB đúng, thì q cũng phải đúng “ Ví dụ: Nếu một cơ sở tri thức KB chứa 2 mệnh đề “Đội Brasil đã thang” va "Đội Argentina đã thắng”, thì KB bao hàm mệnh đề “Đội Brasil hoặc đội Argentina đã thắng” = Vi du: Ménh dé (x+y = 4) bao hàm mệnh đề (4 = x+y) Tính bao hàm là mối quan hệ giữa các mệnh đề a ngữ nghĩa 17 Ï= CÚ PHÁP LOGIC MỆNH ĐÈ Logic mệnh đề là loại logic đơn giản nhất Cú pháp (syntax) là những gì được phép viết ra H C++: for (int ¡ = 0; ¡ < n; i++) {.} H Colorless green ideas sleep furiously.

Câu (sentenee) (còn gọi là well-formed formulas KWFF)) true va false la cac cau [1 Các biến mệnh đề là các câu: O Néia, là cdc cau thiGa) B cũng là các câu I Ñgoài ra;không nam ngon mg 10 18 Ï= ĐỘ ƯU TIÊN TOÁN TỬ E= No nhát AVBAC AV(BAC) ^ = AAB=CVD | (AAB)>(CVD) = Bs Thdp nhdt A=BVCCD (A>(BVC)<©D Luật ưu tiên cho phép các dạng viết tắt câu, nhưng chính thức chỉ có dạng đầy đủ dấu ngoặc mới hợp lệ. Các dạng nhập nhằng về cú pháp được cho phép viết tắt chỉ khi chúng tương đương ngữ nghĩa. H ABC tương đương với (A ^ B) A C và A A (BA €) DƯ.