CHƯƠNG 1: GIỚI THIỆU 1.1 Trí tuệ nhân tạo là gì? Trí tuệ nhân tạo (AI) là khả năng của máy tính để thực hiện các nhiệm vụ mà trước đây chỉ có con người mới có thể làm được. AI đã và đang được ứng dụng trong nhiều lĩnh vực khác nhau của cuộc sống, bao gồm công nghiệp, y tế, tài chính, giáo dục, và logistics.2 Lịch sử của trí tuệ nhân tạo 1956: Hội nghị Dartmouth được tổ chức, đánh dấu sự ra đời của ngành khoa học trí tuệ nhân tạo. 1957: Herbert Simon và Allen Newell tạo ra chương trình Logic Theorist, có thể chứng minh các định lý toán học. 1959: Marvin Minsky và Seymour Papert tạo ra Perceptron, một mô hình học máy đơn giản.
1960: John McCarthy tạo ra ngôn ngữ lập trình Lisp, được sử dụng rộng rãi trong AI. 1970: Mùa đông AI đầu tiên xảy ra, do sự thất vọng của các nhà nghiên cứu về thiếu hụt đột phá. 1980: Mùa đông AI thứ hai xảy ra, do sự thất bại của một số dự án AI lớn. 1990: Sự phát triển của các công nghệ mới, như học máy và xử lý ngôn ngữ tự nhiên, đã dẫn đến sự hồi sinh của AI.
2000: AI bắt đầu được ứng dụng trong nhiều lĩnh vực khác nhau của cuộc sống. 2023: AI tiếp tục phát triển và có tiềm năng to lớn để thay đổi thế giới.3 Các lĩnh vực của trí tuệ nhân tạo Lập luận, suy diễn tự động: máy tính có thể rút ra kết luận mới từ những giả thiết đã cho. Biểu diễn tri thức: máy tính có thể lưu trữ và xử lý tri thức. Lập kế hoạch: máy tính có thể xác định dãy hành động cần thực hiện để đạt được mục đích.
Học máy: máy tính có thể học hỏi từ dữ liệu. Xử lý ngôn ngữ tự nhiên: máy tính có thể hiểu và xử lý ngôn ngữ tự nhiên. Hệ chuyên gia: máy tính có thể đưa ra kết luận dựa trên lượng thông tin lớn. Robotics: máy tính có thể điều khiển robot.
4 CHƯƠNG 2: BÀI TOÁN VÀ PHƯƠNG PHÁP TÌM KIẾM LỜI GIẢI 2.1 Bài toán và các thành phần của bài toán Một bài toán là một câu hỏi hoặc vấn đề cần được giải quyết. Một bài toán có thể được mô tả bằng các thành phần sau: Trạng thái: Một đại diện cho một trạng thái của bài toán. Trạng thái có thể được biểu diễn dưới nhiều dạng khác nhau, tùy thuộc vào bài toán cụ thể. Ví dụ, trong bài toán tìm kiếm đường đi ngắn nhất giữa hai điểm, trạng thái có thể được biểu diễn bằng một đỉnh trong đồ thị.
Trạng thái đầu: Trạng thái ban đầu của bài toán. Trạng thái đầu là trạng thái mà bài toán bắt đầu. Trạng thái đích: Trạng thái cần đạt được của bài toán. Trạng thái đích là trạng thái mà bài toán cần đạt được để giải quyết.
Phép chuyển trạng thái: Một thao tác chuyển từ một trạng thái này sang một trạng thái khác. Phép chuyển trạng thái có thể được biểu diễn bằng một hàm hoặc một thuật toán. Chi phí: Một số thực thể đánh giá giá trị của một phép chuyển trạng thái. Chi phí có thể được sử dụng để đánh giá chất lượng của một lời giải.
Bài toán đong nước Sử dụng ba can 3 lít, 5 lít và 9 lít, làm thế nào để đong được 7 lít nước. Bài toán này được phát biểu lại theo 5 thành phần như sau: - Trạng thái: Gọi số nước có trong 3 can lần lượt là a, b, c (a ≤ 3, b ≤ 5, c ≤ 9), khi đó bộ ba (a, b, c) là trạng thái của bài toán - Trạng thái đầu: (0, 0, 0) // cả ba can đều rỗng - Trạng thái đích (-, -, 7) // can thứ 3 chứa 7 lít nước - Phép chuyển trạng thái: từ trạng thái (a,b,c) có thể chuyển sang trạng thái (x,y,z) thông qua các thao tác như làm rỗng 1 can, chuyển từ can này sang can kia đến khi hết nước ở can nguồn hoặc can đích bị đầy. - Chi phí mỗi phép chuyển trạng thái: mỗi phép chuyển trạng thái có chi phí là 1. Bài toán tìm đường đi Một ôtô robot tìm đường đi từ thành phố Arad đến thành phố Bucharest.
Biết rằng xe robot này không có bản đồ đầy đủ như trên hình vẽ trên, nhưng khi nó đến một thành phố mới, nó có bộ cảm biến đọc được biển chỉ đường đến các thành lân cận, trên biển chỉ đường có khoảng cách. Bài toán tìm đường có thể phát biểu theo 5 thành phần như sau: - Trạng thái: vị trí của ôtô robot (tên thành phố) - Trạng thái: vị trí của ôtô robot (tên thành phố) - Trạng thái đích: Thành phố Bucharest - Phép chuyển trạng thái: từ thành phố sang thành phố lân cận - Chi phí: khoảng cách giữa 2 thành phố trong phép chuyển trạng thái Lời giải của bài toán là dãy các phép chuyển từ trạng thái đầu đến trạng thái đích, hay là đường đi từ thành phố đầu đến thành phố đích. Một ví dụ của lời giải bài toán là: Arad Æ Sibiu Æ Fagaras Æ Bucharest.2 Giải thuật tổng quát tìm kiếm lời giải a. Không gian trạng thái của bài toán Mỗi bài toán với 5 thành phần như mô tả ở trên, chúng ta có thể xây dựng được một cấu trúc đồ thị với các nút là các trạng thái của bài toán, các cung là phép chuyển trạng thái.
Đồ thị này được gọi là không gian trạng thái của bài toán. Không gian trạng thái có thể là vô hạn hoặc hữu hạn. Ví dụ, với bài toán di chuyển 8 số trên bàn cờ, không gian trạng thái có số lượng là 8! (8 giai thừa) trạng thái. Lời giải của bài toán là một đường đi trong không gian trạng thái có điểm đầu là trạng thái đầu và điểm cuối là trạng thái đích.
Nếu không gian trạng thái của bài toán là nhỏ, có thể liệt kê và lưu vừa trong bộ nhớ của máy tính thì việc tìm đường đi trong không gian trạng thái có thể áp dụng các thuật toán tìm đường đi trong lý thuyết đồ thị. Tuy nhiên, trong rất nhiều trường hợp, không gian trạng thái của bài toán là rất lớn, việc duyệt toàn bộ không gian trạng thái là không thể. Trong môn học Trí tuệ nhân tạo này, chúng ta sẽ tìm hiểu các phương pháp tìm kiếm lời giải trong các bài toán có không gian trạng thái lớn. Giải thuật tổng quát tìm kiếm lời giải của bài toán Với các bài toán có 5 thành phần ở trên, chúng ta có giải thuật chung để tìm kiếm lời giải của bài toán.
Ý tưởng là sinh ra các lời giải tiềm năng và kiểm tra chúng có phải là lời giải thực sự của bài toán. Một lời giải tiềm năng là một đường đi trong không gian trạng thái của bài toán có nút đầu là trạng thái đầu và mỗi cung của đường đi là một phép chuyển hợp lệ giữa các trạng thái kề với cung đó. Lời giải thực sự của bài toán là lời giải tiềm năng có nút cuối cùng là trạng thái đích. Các lời giải tiềm năng là các đường đi có cùng nút đầu tiên và dãy các cung là dãy các phép chuyển hợp lệ từ trạng thái đầu đó.
Các lời giải tiềm năng có thể tổ chức theo cây, gốc của cây là trạng thái đầu, cây được phát triển bằng cách bổ sung vào các nút liền kề với trạng thái đầu, sau đó liên tiếp bổ sung vào các con của các nút lá, … Lược đồ chung để tìm lời giải của bài toán 4 thành phần trên là xây dựng cây lời giải tiểm năng (hay là cây tìm kiếm) và kiểm tra lời giải tiềm năng có là lời giải thực sự của bài toán hay không. Các bước của giải thuật chung là như sau: xây dựng cây tìm kiếm mà nút gốc là trạng thái đầu, lặp lại 2 bước: kiểm tra xem trạng thái đang xét có là trạng thái đích không, nếu là trạng thái đích thì thông báo lời giải, nếu không thì mở rộng cây tìm kiếm bằng cách bổ sung các nút con là các 7 trạng thái láng giềng của trạng thái đang xét. Giải thuật chung được trình bày trong bảng sau: Đầu vào của giải thuật là bài toán (problem) với 5 thành phần (biểu diễn trạng thái tổng quát, trạng thái đầu, trạng thái đích, phép chuyển trạng thái, chi phí phép chuyển trạng thái) và một chiến lược tìm kiếm (strategy); đầu ra của giải thuật là một lời giải của bài toán hoặc giá trị failure nếu bài toán không có lời giải. Giải thuật sinh ra cây các lời giải tiềm năng, nút gốc là trạng thái đầu của bài toán, mở rộng cây theo chiến lược (strategy) đã định trước đến khi cây chứa nút trạng thái đích hoặc không thể mở rộng cây được nữa Trong giải thuật chung này, chiến lược tìm kiếm (strategy) sẽ quyết định việc chọn nút lá nào trong số nút lá của cây để mở rộng cây tìm kiếm, ví dụ như nút lá nào xuất hiện trong cây sớm hơn thì được chọn trước để phát triển cây (đây là chiến lược tìm kiếm theo chiều rộng), hoặc nút lá nào xuất hiện sau thì được chọn để mở rộng cây (đây là chiến lược tìm kiếm theo chiều sâu).
Chiến lược tìm kiếm có thể được cài đặt thông qua một cấu trúc dữ liệu để đưa vào và lấy ra trạng thái lá của cây tìm kiếm. Hai cấu trúc dữ liệu cơ bản là hàng đợi và ngăn xếp. Hàng đợi sẽ lưu các trạng thái lá của cây và trạng thái nào được đưa vào hàng đợi trước sẽ được lấy ra trước, còn ngăn xếp là cấu trúc dữ liệu lưu trạng thái lá của cây tìm kiếm và việc chọn nút lá của cây sẽ theo kiểu vào trước ra sau. Bảng dưới đây là chi tiết hóa thuật toán tìm kiếm lời giải ở trên với chiến lược tìm kiếm được thể hiện thông qua cấu trúc dữ liệu hàng đợi (queue) hoặc ngăn xếp (stack).
Trong giải thuật chi tiết 8 hơn này, cây tìm kiếm được biểu diễn bằng mảng một chiều father, trong đó father(i) là chỉ nút cha của nút i. Thủ tục path(node, father) dùng để lần ngược đường đi từ trạng thái node về nút gốc (trạng thái đầu) (node được truyền giá trị là trạng thái đích khi thủ tục path được gọi). Cây tìm kiếm Trong quá trình tìm kiếm lời giải, chúng ta thường áp dụng một chiến lược để sinh ra các lời giải tiềm năng. Các lời giải tiềm năng được tổ chức thành cây mà gốc là trạng thái đầu của bài toán, các mức tiếp theo của cây là các nút kề với các nút ở mức trước.
Thông thường thì cây tìm kiếm được mở rộng đến nó chứa trạng thái đích là dừng.