Giáo trình Trí tuệ nhân tạo (Phần 1) - Phạm Thọ Hoàn

46 trang cucquyet12 9170

Download

Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Trí tuệ nhân tạo (Phần 1) - Phạm Thọ Hoàn", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

giao_trinh_tri_tue_nhan_tao_phan_1_pham_tho_hoan.pdf

Nội dung text: Giáo trình Trí tuệ nhân tạo (Phần 1) - Phạm Thọ Hoàn

Giáo trình TRÍ TUỆ NHÂN TẠO ARTIFICIAL INTELLIGENCE Phạm Thọ Hoàn, Phạm Thị Anh Lê Khoa Công nghệ thông tin Trường Đại học Sư phạm Hà Nội Hà nội, 2011
MỤC LỤC Chương 1 – Giới thiệu 5 1. Trí tuệ nhân tạo là gì? 5 2. Lịch sử 6 3. Các lĩnh vực của AI 7 4. Nội dung môn học 9 Chương 2 – Bài toán và phương pháp tìm kiếm lời giải 10 1. Bài toán và các thành phần của bài toán 10 2. Giải thuật tổng quát tìm kiếm lời giải 14 3. Đánh giá giải thuật tìm kiếm 17 4. Các giải thuật tìm kiếm không có thông tin phản hồi (tìm kiếm mù) 18 Chương 3 –Các phương pháp tìm kiếm heuristic 25 1. Giải thuật tìm kiếm tốt nhất đầu tiên (best first search) 25 2. Các biến thể của giải thuật best first search 28 3. Các giải thuật khác 31 Chương 4 – Các giải thuật tìm kiếm lời giải cho trò chơi 37 1. Cây trò chơi đầy đủ 37 2. Giải thuật Minimax 39 3. Giải thuật Minimax với độ sâu hạn chế 41 4. Giải thuật Minimax với cắt tỉa alpha-beta 44 Chương 5 – Các phương pháp tìm kiếm lời giải thỏa mãn các ràng buộc 47 1. Các bài toán thỏa mãn các ràng buộc 47 2. Giải thuật quay lui vét cạn 50
3. Các cải tiến của giải thuật quay lui 51 4. Các giải thuật tối ưu địa phương 54 Chương 6 – Các phương pháp lập luận trên logic mệnh đề 55 1. Lập luận và Logic 55 2. Logic mệnh đề: cú pháp, ngữ nghĩa 55 3. Bài toán lập luận và các giải thuật lập luận trên logic mệnh đề 58 4. Câu dạng chuẩn hội và luật phân giải 60 5. Câu dạng Horn và tam đoạn luận 63 6. Thuật toán suy diễn dựa trên bảng giá trị chân lý 65 7. Thuật toán suy diễn dựa trên luật phân giải 65 8. Thuật toán suy diễn tiến, lùi dựa trên các câu Horn 67 9. Kết chương 70 Chương 7 – Các phương pháp lập luận trên logic cấp một 72 1. Cú pháp – ngữ nghĩa 74 2. Lập luận trong logic vị từ cấp một 78 3. Phép đồng nhất hai vị từ, thuật giải đồng nhất 80 4. Câu dạng chuẩn hội, luật phân giải tổng quát 82 5. Câu dạng Horn và tam đoạn luận tổng quát trong logic cấp 1 84 6. Giải thuật suy diễn phân giải 86 7. Thuật toán suy diễn tiến dựa trên câu Horn 89 8. Thuật toán suy diễn lùi dựa trên câu Horn 91 Chương 8 – Prolog 92 1. Lập trình logic, môi trường lập trình SWI Prolog 92 2. Ngôn ngữ Prolog cơ bản, chương trình Prolog 95
3. Câu truy vấn 97 4. Vị từ phi logic (câu phi logic) 97 5. Trả lời truy vấn, quay lui, cắt, phủ định 98 6. Vị từ đệ qui 104 7. Cấu trúc dữ liệu trong Prolog 105 8. Thuật toán suy diễn trong Prolog 106 Chương 9 – Lập luận với tri thức không chắc chắn 107 Chương 10 – Học mạng nơron nhân tạo 108
Chương 1 – Giới thiệu 1. Trí tuệ nhân tạo là gì? Để hiểu trí tuệ nhân tạo (artificial intelligence) là gì chúng ta bắt đầu với khái niệm sự bay nhân tạo (flying machines), tức là cái máy bay. Đã từ lâu, loài người mong muốn làm ra một cái máy mà có thể di chuyển được trên không trung mà không phụ thuộc vào địa hình ở dưới mặt đất, hay nói cách khác là máy có thể bay được. Không có gì ngạc nhiên khi những ý tưởng đầu tiên làm máy bay là từ nghiên cứu cách con chim bay. Những chiếc máy biết bay được thiết kế theo nguyên lý “vỗ cánh” như con chim chỉ có thể bay được quãng đường rất ngắn và lịch sử hàng không thực sự sang một trang mới kể từ anh em nhà Wright thiết kế máy bay dựa trên các nguyên lý của khí động lực học (aerodynamics). Các máy bay hiện nay, như đã thấy, có sức trở rất lớn và bay được quãng đường có thể vòng quanh thế giới. Nó không nhất thiết phải có nguyên lý bay của con chim nhưng vẫn bay được như chim (dáng vẻ), và còn tốt hơn chim. Quay lại câu hỏi Trí tuệ nhân tạo là gì. Trí tuệ nhân tạo là trí thông minh của máy do con người tạo ra. Ngay từ khi chiếc máy tính điện tử đầu tiên ra đời, các nhà khoa học máy tính đã hướng đến phát hiển hệ thống máy tính (gồm cả phần cứng và phần mềm) sao cho nó có khả năng thông minh như loài người. Mặc dù cho đến nay, theo quan niệm của người viết, ước mơ này vẫn còn xa mới thành hiện thực, tuy vậy những thành tựu đạt được cũng không hề nhỏ: chúng ta đã làm được các hệ thống (phần mềm chơi cờ vua chạy trên siêu máy tinh GeneBlue) có thể thắng được vua cờ thế giới; chúng ta đã làm được các phần mềm có thể chứng minh được các bài toán hình học; v.v. Hay nói cách khác, trong một số lĩnh vực, máy tính có thể thực hiện tốt hơn hoặc tương đương con người (tất nhiên không phải tất cả các lĩnh vực). Đó chính là các hệ thống thông minh. Có nhiều cách tiếp cận để làm ra trí thông minh của máy (hay là trí tuệ nhân tạo), chẳng hạn là nghiên cứu cách bộ não người sản sinh ra trí thông minh của loài người như
thế nào rồi ta bắt chước nguyên lý đó, nhưng cũng có những cách khác sử dụng nguyên lý hoàn toàn khác với cách sản sinh ra trí thông minh của loài người mà vẫn làm ra cái máy thông minh như hoặc hơn người; cũng giống như máy bay hiện nay bay tốt hơn con chim do nó có cơ chế bay không phải là giống như cơ chế bay của con chim. Như vậy, trí tuệ nhân tạo ở đây là nói đến khả năng của máy khi thực hiện các công việc mà con người thường phải xử lý; và khi dáng vẻ ứng xử hoặc kết quả thực hiện của máy là tốt hơn hoặc tương đương với con người thì ta gọi đó là máy thông minh hay máy đó có trí thông minh. Hay nói cách khác, đánh giá sự thông minh của máy không phải dựa trên nguyên lý nó thực hiện nhiệm vụ đó có giống cách con người thực hiện hay không mà dựa trên kết quả hoặc dáng vẻ ứng xử bên ngoài của nó có giống với kết quả hoặc dáng vẻ ứng xử của con người hay không. Các nhiệm vụ của con người thường xuyên phải thực hiện là: giải bài toán (tìm kiếm, chứng minh, lập luận), học, giao tiếp, thể hiện cảm xúc, thích nghi với môi trường xung quanh, v.v., và dựa trên kết quả thực hiện các nhiệm vụ đó để kết luận rằng một ai đó có là thông minh hay không. Môn học Trí tuệ nhân tạo nhằm cung cấp các phương pháp luận để làm ra hệ thống có khả năng thực hiện các nhiệm vụ đó: giải toán, học, giao tiếp, v.v. bất kể cách nó làm có như con người hay không mà là kết quả đạt được hoặc dáng vẻ bên ngoài như con người. Trong môn học này, chúng ta sẽ tìm hiểu các phương pháp để làm cho máy tính biết cách giải bài toán, biết cách lập luận, biết cách học, v.v. 2. Lịch sử Vào năm 1943, Warren McCulioch và Walter Pitts bắt đầu thực hiện nghiên cứu ba cơ sở lý thuyết cơ bản: triết học cơ bản và chức năng của các noron thần kinh; phân tích các mệnh đề logic; và lý thuyết dự đoán của Turing. Các tác giả đã nghiên cứu đề xuât mô hình noron nhân tạo, mỗi noron đặc trưng bởi hai trạng thái “bật”, “tắt” và phát hiện mạng noron có khả năng học.
Thuật ngữ “Trí tuệ nhân tạo” (Artificial Intelligence - AI) được thiết lập bởi John McCarthy tại Hội thảo đầu tiên về chủ đề này vào mùa hè năm 1956. Đồng thời, ông cũng đề xuất ngôn ngữ lập trình Lisp – một trong những ngôn ngữ lập trình hàm tiêu biểu, được sử dụng trong lĩnh vực AI. Sau đó, Alan Turing đưa ra "Turing test" như là một phương pháp kiểm chứng hành vi thông minh. Thập kỷ 60, 70 Joel Moses viết chương trình Macsyma - chương trình toán học sử dụng cơ sở tri thức đầu tiên thành công. Marvin Minsky và Seymour Papert đưa ra các chứng minh đầu tiên về giới hạn của các mạng nơ-ron đơn giản. Ngôn ngữ lập trình logic Prolog ra đời và được phát triển bởi Alain Colmerauer. Ted Shortliffe xây dựng thành công một số hệ chuyên gia đầu tiên trợ giúp chẩn đoán trong y học, các hệ thống này sử dụng ngôn ngữ luật để biểu diễn tri thức và suy diễn. Vào đầu những năm 1980, những nghiên cứu thành công liên quan đến AI như các hệ chuyên gia (expert systems) – một dạng của chương trình AI mô phỏng tri thức và các kỹ năng phân tích của một hoặc nhiều chuyên gia con người Vào những năm 1990 và đầu thế kỷ 21, AI đã đạt được những thành tựu to lớn nhất, AI được áp dụng trong logic, khai phá dữ liệu, chẩn đoán y học và nhiều lĩnh vực ứng dụng khác trong công nghiệp. Sự thành công dựa vào nhiều yếu tố: tăng khả năng tính toán của máy tính, tập trung giải quyết các bài toán con cụ thể, xây dựng các mối quan hệ giữa AI và các lĩnh vực khác giải quyết các bài toán tương tự, và một sự chuyển giao mới của các nhà nghiên cứu cho các phương pháp toán học vững chắc và chuẩn khoa học chính xác. 3. Các lĩnh vực của AI ¾ Lập luận, suy diễn tự động: Khái niệm lập luận (reasoning), và suy diễn (reference) được sử dụng rất phổ biến trong lĩnh vực AI. Lập luận là suy diễn logic, dùng để chỉ một tiến trình rút ra kết luận (tri thức mới) từ những giả thiết đã cho (được biểu diễn dưới dạng cơ sở tri thức). Như vậy, để thực hiện lập luận người ta cần có các phương pháp lưu trữ cơ sở tri thức và các thủ tục lập luận trên cơ sở tri thức đó.
¾ Biểu diễn tri thức: Muốn máy tính có thể lưu trữ và xử lý tri thức thì cần có các phương pháp biểu diễn tri thức. Các phương pháp biểu diễn tri thức ở đây bao gồm các ngôn ngữ biểu diễn và các kỹ thuật xử lý tri thức. Một ngôn ngữ biểu diễn tri thức được đánh giá là “tốt” nếu nó có tính biểu đạt cao và các tính hiệu quả của thuật toán lập luận trên ngôn ngữ đó. Tính biểu đạt của ngôn ngữ thể hiện khả năng biểu diễn một phạm vi rộng lớn các thông tin trong một miền ứng dụng. Tính hiệu quả của các thuật toán lập luận thể hiện chi phí về thời gian và không gian dành cho việc lập luận. Tuy nhiên, hai yếu tố này dường như đối nghịch nhau, tức là nếu ngôn ngữ có tính biểu đạt cao thì thuật toán lập luận trên đó sẽ có độ phức tạp lớn (tính hiệu quả thấp) và ngược lại (ngôn ngữ đơn giản, có tính biểu đạt thấp thì thuật toán lập luận trên đó sẽ có hiệu quả cao). Do đó, một thách thức lớn trong lĩnh vực AI là xây dựng các ngôn ngữ biểu diễn tri thức mà có thể cân bằng hai yếu tố này, tức là ngôn ngữ có tính biểu đạt đủ tốt (tùy theo từng ứng dụng) và có thể lập luận hiệu quả. ¾ Lập kế hoạch: khả năng suy ra các mục đích cần đạt được đối với các nhiệm vụ đưa ra, và xác định dãy các hành động cần thực hiện để đạt được mục đích đó. ¾ Học máy: là một lĩnh vực nghiên cứu của AI đang được phát triển mạnh mẽ và có nhiều ứng dụng trong các lĩnh vực khác nhau như khai phá dữ liệu, khám phá tri thức, ¾ Xử lý ngôn ngữ tự nhiên: là một nhánh của AI, tập trung vào các ứng dụng trên ngôn ngữ của con người. Các ứng dụng trong nhận dạng tiếng nói, nhận dạng chữ viết, dịch tự động, tìm kiếm thông tin, ¾ Hệ chuyên gia: cung cấp các hệ thống có khả năng suy luận để đưa ra những kết luận. Các hệ chuyên gia có khả năng xử lý lượng thông tin lớn và cung cấp các kết luận dựa trên những thông tin đó. Có rất nhiều hệ chuyên gia nổi tiếng như các hệ chuyên gia y học MYCIN, đoán nhận cấu trúc phân tử từ công thức hóa học DENDRAL, ¾ Robotics
¾ 4. Nội dung môn học Giáo trình này được viết với các nội dung nhập môn về AI cho các sinh viên chuyên ngành Tin học và Công nghệ thông tin. Các tác giả có tham khảo một số tài liệu, giáo trình của các trường Đại học Quốc gia Hà nội, Đại học Bách khoa Hà nội, Nội dung gồm các phần sau: Chương 1. Giới thiệu: trình bày tổng quan về AI, lịch sử ra đời và phát triển và các lính vực ứng dụng của AI. Chương 2. Các phương pháp tìm kiếm lời giải: trình bày các kỹ thuật tìm kiếm cơ bản được áp dụng để giải quyết các vấn đề và được áp dụng rộng rãi trong các lĩnh vực của trí tuệ nhân tạo. Chương 3. Các giải thuật tìm kiếm lời giải cho trò chơi: trình bày một số kỹ thuật tìm kiếm trong các trò chơi có đối thủ. Chương 4. Các phương pháp lập luận trên logic mệnh đề: trình bày cú pháp, ngữ nghĩa của logic mệnh đề và một số thuật toán lập luận trên logic mệnh đề. Chương 5. Các phương pháp lập luận trên logic vị từ cấp một: trình bày cú pháp, ngữ nghĩa của logic vị từ cấp một và một số thuật toán lập luận cơ bản trên logic vị từ cấp một. Chương 6. Prolog: Giới thiệu chung về ngôn ngữ Prolog, cú pháp, ngữ nghĩa và cấu trúc chương trình trong Prolog, một số phiên bản mới của Prolog như SWI Prolog, Chương 7. Lập luận với tri thức không chắc chắn: Giới thiệu về tri thức không chắc chắn và một số cách tiếp cận biểu diễn và xử lý tri thức không chắc chắn. Chương 8. Học mạng noron nhân tạo: Giới thiệu về phương pháp và các kỹ thuật cơ bản trong lập luận sử dụng mạng noron nhân tạo.
Chương 2 – Bài toán và phương pháp tìm kiếm lời giải 1. Bài toán và các thành phần của bài toán Chương này giới thiệu các giải thuật máy tính có thể giải các bài toán mà thông thường đòi hỏi trí thông minh của con người, như bài toán đong nước, bài toán 8 sô trên bàn cờ, bài toán tìm đường như mô tả bên dưới đây. Để thiết kế giải thuật chung giải các bài toán này, chúng ta nên phát biểu bài toán theo dạng 5 thành phần: Trạng thái bài toán, trạng thái đầu, trạng thái đích, các phép chuyển trạng thái, lược đồ chi phí các phép chuyển trạng thái (viết gọn là chi phí). a. Bài toán đong nước 5 l 9 l 3 l 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.
Một lời giải của bài toán là một dãy các phép chuyển trạng thái (đường đi) từ trạng thái đầu đến trạng thái đích. Bảng dưới đây là 2 lời giải của bài toán trên: a b c Å Đầu Æ a b c 0 0 0 0 0 0 3 0 0 0 5 0 0 0 3 3 2 0 3 0 3 3 0 2 0 0 6 3 5 2 3 0 6 Đích Æ 3 0 7 0 3 6 Lời giải 2 (chi phí: 5) 3 3 6 1 5 6 0 5 7 Å Đích Lời giải 1 (chi phí: 9) b. Bài toán di chuyển 8 số trên bàn cờ
Trạng thái đầu Trạng thái đích Cho bàn cờ kích thước 3 x 3, trên bàn cờ có 8 quân cờ đánh số từ 1 đến 8 (hình vẽ). Trên bàn cờ có một ô trống. Chúng ta có thể chuyển một quân cờ có chung cạnh với ô trống sang ô trống. Hãy tìm dãy các phép chuyển để từ trạng thái ban đầu về trạng thái mà các quan cờ được xếp theo trật tự như Trạng thái đích của hình trên. Bài toán di chuyển 8 số trên bàn cờ có thể phát biểu dưới dạng 5 thành phần như sau: - Biểu diễn trạng thái: mảng 2 chiều kích thước 3x3, phần tử của mảng lưu số hiệu quân cờ (từ 0 đến 9, 0 là vị trí trống). Cũng có thể biểu diễn trạng thái bàn cờ bằng mảng một chiều gồm 9 phần tử: ba phần tử đầu tiên biểu diễn các ô thuộc dòng đầu tiên của bàn cờ, ba phần tử tiếp biểu diễn các quân cờ thuộc dòng thứ hai, ba phần tử cuối cùng biểu diễn các quân cờ thuộc dòng cuối cùng. Ở đây chúng tôi sử dụng mảng hai chiều 3x3 để cho giống với bàn cờ trên thực tế. - Trạng thái đầu (hình vẽ trên) - Trạng thái đích (hình vẽ trên) - Phép chuyển trạng thái: đổi chỗ ô có số hiệu 0 với một trong các ô có cùng cạnh. - Chi phí: mỗi phép chuyển có chi phí 1. 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. Một lời giải của bài toán là: UP, UP, RIGHT, DOWN, LEFT, UP, RIGHT, RIGHT, DOWN,
LEFT, LEFT, UP, RIGHT, DOWN, RIGHT, DOWN (chú ý: up, down, right, left là biểu diễn sự dịch chuyển ô trống lên trên, xuống dưới, sang phải, sang trái) c. 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 đầu: Thành phố Arad - 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. b. 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 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. Function General_Search(problem, strategy) returns a solution, or failure cây-tìm-kiếm Å trạng-thái-đầu; while (1) { if (cây-tìm-kiếm không thể mở rộng được nữa) then return failure nút-lá Å Chọn-1-nút-lá(cây-tìm-kiếm, strategy) if (node-lá là trạng-thái-đích) then return Đường-đi(trạng-thái-đầu, nút-lá) else mở-rộng(cây-tìm-kiếm, các-trạng-thái-kề(nút-lá)) } 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 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). Function General_Search(problem, Queue/Stack) returns a solution, or failure Queue/Stack Å make_queue/make_stack(make-node(initial-state[problem])); father(initial-state[problem]) = empty; while (1) if Queue/Stack is empty then return failure; node = pop(Queue/Stack) ; if test(node,Goal[problem]) then return path(node,father); expand-nodes Åadjacent-nodes(node, Operators[problem]); push(Queue/Stack, expand-nodes ); foreach ex-node in expand-nodes father(ex-node) = node; end
Function path(node,father[]) : print the solution n Å node while (n # empty) cout<< n <<“ < ” ; n = father[n]; end c. 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. 3. Đánh giá giải thuật tìm kiếm Một giải thuật tìm kiếm lời giải của bài toán phụ thuộc rất nhiều vào chiến lược tìm kiếm (hay là cấu trúc dữ liệu để lưu các nút lá của cây trong quá trình tìm kiếm). Để đánh giá giải thuật tìm kiếm người ta đưa ra 4 tiêu chí sau: 1. Tính đầy đủ: giải thuật có tìm được lời giải của bài toán không nếu bài toán tồn tại lời giải? 2. Độ phức tạp thời gian: thời gian của giải thuật có kích cỡ như thế nào đối với bài toán? 3. Độ phức tạp không gian: Kích cỡ của bộ nhớ cần cho giải thuật? Trong giải thuật tổng quát ở trên, kích cỡ bộ nhớ chủ yếu phụ thuộc vào cấu trúc dữ liệu lưu các trạng thái lá của cây tìm kiếm 4. Tính tối ưu: Giải thuật có tìm ra lời giải có chi phí tối ưu (nhỏ nhất hoặc lớn nhất tùy theo ngữ cảnh của bài toán)?
Độ phức tạp thời gian và độ phức tạp không gian của giải thuật tìm kiếm lời giải của bài toán có thể đánh giá dựa trên kích thước đầu vào của giải thuật. Các tham số kích thước đầu vào có thể là: - b – nhân tố nhánh của cây tìm kiếm: số nhánh tối đa của một nút, hay là số phép chuyển trạng thái tối đa của một trạng thái tổng quát - d – độ sâu của lời giải có chi phí nhỏ nhất - m – độ sâu tối đa của cây tìm kiếm (m có thể là vô hạn) Trong các giải thuật tìm kiếm lời giải đề cập đến ở chương này, chúng ta sẽ đánh giá ưu, nhược điểm của từng giải thuật dựa trên 4 tiêu chí trên. 4. Các giải thuật tìm kiếm không có thông tin phản hồi (tìm kiếm mù) Các giải thuật tìm kiếm không sử dụng thông tin phản hồi (hay là giải thuật tìm kiếm mù) là các giải thuật chỉ sử dụng thông tin từ 5 thành phần cơ bản của bài toá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í). Ý tưởng chung cơ bản của các giải thuật này là sinh ra cây lời giải tiềm năng (cây tìm kiếm) một cách có hệ thống (không bỏ sót và không lặp lại). Phần này sẽ giới thiệu các giải thuật tìm kiếm theo chiều rộng, tìm kiếm theo chiều sâu, tìm kiếm theo chiều sâu có giới hạn, tìm kiếm sâu dần. Các giải thuật này đều theo giải thuật chung đã giới thiệu bên trên, chỉ khác nhau ở chiến lược tìm kiếm hay là cấu trúc dữ liệu để lưu giữ và lấy ra các nút lá của cây tìm kiếm. a. Tìm kiếm theo chiều rộng Giải thuật tìm kiếm lời giải theo chiều rộng là cài đặt cụ thể của giải thuật chung tìm kiếm lời giải, trong đó có sử dụng cấu trúc dữ liệu kiểu hàng đợi (queue) để lưu giữ các trạng thái nút lá của cây tìm kiếm. Các nút lá sinh ra trong quá trình thực thi giải thuật sẽ được cập nhật vào một hàng đợi theo nguyên tắc nút nào được đưa vào hàng đợi trước sẽ được lấy ra trước trong quá trình mở rộng cây. Chi tiết của giải thuật được cho trong bảng bên dưới.
Chúng ta sẽ minh họa việc tìm kiếm lời giải bằng giải thuật tìm kiếm theo chiều rộng bằng ví dụ cụ thể như sau. Giả sử bài toán có không gian các trạng thái đầy đủ như hình vẽ ngay sau bảng giải thuật (trang sau), với trạng thái đầu là S, trạng thái đích là G và các phép chuyển trạng thái là các cung nối giữa các trạng thái. Giải thuật bắt đầu xét với hàng đợi chứa trạng thái đầu S, lấy trạng thái ở đầu hàng đợi ra kiểm tra xem nó có là trạng thái đích, nếu là đích thì in lời giải, nếu không thì bổ sung các trạng thái con của nó vào hàng đợi. Function Breadth-Search(problem, Queue) returns a solution, or failure Queue Å make-queue(make-node(initial-state[problem])); father(initial-state[problem]) = empty; while (1) if Queue is empty then return failure; node = pop(Queue) ; if test(node,Goal[problem]) then return path(node,father); expand-nodes Åadjacent-nodes(node, Operators[problem]); push(Queue, expand-nodes ); foreach ex-node in expand-nodes father(ex-node) = node; end Không gian đầy đủ các trạng thái của bài toán
Bảng phía dưới là diễn biến các biến chính của giải thuật: biến trạng thái đang xét – node, biến hàng đợi – Queue, biến lưu thông tin về cây tìm kiếm – Father. Giải thuật kết thúc với 8 vòng lặp khi trạng thái đang xét node = G và khi đó lời giải của bài toán là đường đi G Å B Å S. node Queue Father S S A, B, C Father[A,B,C]=S A B, C, D, E Father[D,E]=A B C,D,E,G Father[G]=B C D, E, G, F Father[F]=C D E,G, F, H Father[H]=D E G, F, H G F, H Cây tìm kiếm của giải thuật theo chiều rộng Giá trị các biến trong giải thuật theo chiều rộng Đánh giá giải thuật tìm kiếm theo chiều rộng: 9 Tính đầy đủ: giải thuật sẽ cho lời giải của bài toán nếu bài toán tồn tại lời giải và nhân tố nhánh b là hữu hạn 9 Độ phức tạp thời gian: 1+b+b2+ +bd (số vòng lặp khi gặp trạng thái đích) = O(bd) 9 Độ phức tạp không gian: số lượng ô nhớ tối đa sử dụng trong giải thuật (chủ yếu là biến Queue, xem hình vẽ dưới): bd 9 Tính tối ưu: giải thuật tìm kiếm theo chiều rộng sẽ tìm ra lời giải với ít trạng thái trung gian nhất.
d m b G Hàng đợi trong giải thuật tìm kiếm theo chiều rộng chỉ chứa các nút lá của cây tìm kiếm, vì vậy có kích thước là bd. b. Tìm kiếm theo chiều sâu Giải thuật tìm kiếm theo chiều sâu hoàn toàn tương tự như giải thuật tìm kiếm theo chiều rộng, chỉ khác ở chỗ thay vì sử dụng cấu trúc dữ liệu hàng đợi, ta sử dụng cấu trúc dữ liệu ngăn xếp (Stack) để lưu giữ các trạng thái lá của cây tìm kiếm. Đối với cấu trúc dữ liệu ngăn xếp, các trạng thái đưa vào sau cùng sẽ được lấy ra trước để mở rộng cây tìm kiếm. Giải thuật và diễn biến các biến chính trong giải thuật được trình bày trong các bảng và hình vẽ dưới đây. Kết quả của giải thuật là lời giải G Å E Å A Å S.
Function Depth-Search(problem, Stack) returns a solution, or failure Stack Å make-queue(make-node(initial-state[problem])); father(initial-state[problem]) = empty; while (1) if Stack is empty then return failure; node = pop(Stack) ; if test(node,Goal[problem]) then return path(node,father); expand-nodes Åadjacent-nodes(node, Operators[problem]); push(Stack, expand-nodes ); foreach ex-node in expand-nodes father(ex-node) = node; end node Stack father S S A, B, C Father[A,B,C]=S A D, E, B, C Father[D,E]=A D H, E, B, C Father[H]=D H E, B, C E G, B, C Father[G]=E G Giá trị các biến trong giải thuật theo chiều sâu Cây tìm kiếm của giải thuật theo chiều Đánh giá giải thuật tìm kiếm theo chiều sâu: 9 Tính đầy đủ: giải thuật không chắc chắn cho lời giải của bài toán trong trường hợp không gian trạng thái của bài toán là vô hạn
9 Độ phức tạp thời gian: O(bm) 9 Độ phức tạp không gian: O(b.m) 9 Tính tối ưu: giải thuật tìm kiếm theo chiều sâu không cho lời giải tối ưu. c. Tìm kiếm theo chiều sâu có giới hạn Giải thuật tìm kiếm theo chiều sâu ở trên có ưu điểm là nó có thể sinh ra lời giải nhanh chóng mà không tốn kém bộ nhớ của máy tính. Tuy nhiên nếu không gian trạng thái của bài toán là vô hạn thì rất có thể nó không tìm được lời giải của bài toán khi hướng tìm kiếm không chứa trạng thái đích. Để khắc phục nhược điểm này, chúng ta có thể đặt giới hạn độ sâu trong giải thuật: nếu độ sâu của trạng thái đang xét vượt quá ngưỡng nào đó thì chúng ta không bổ sung các nút kề với trạng thái này nữa mà chuyển sang hướng tìm kiếm khác. Chi tiết của giải thuật được cho trong bảng dưới đây, trong đó chúng ta đưa thêm biến mảng một chiều depth[i] lưu độ sâu của trạng thái i. Function Depth-Limitted-Search(problem, maxDepth) returns a solution, or failure Stack Å make-queue(make-node(initial-state[problem])); father(initial-state[problem]) = empty; depth(initial-state[problem]) = 0; while (1) if Stack is empty then return failure; node = pop(Stack) ; if test(node,Goal[problem]) then return path(node,father); if (depth(node) < maxDepth) expand-nodes Åadjacent-nodes(node, Operators[problem]); push(Stack, expand-nodes ); foreach ex-node in expand-nodes father(ex-node) = node; end
d. Tìm kiếm sâu dần Giải thuật tìm kiếm với chiều sâu có giới hạn ở trên phụ thuộc vào giới hạn độ sâu lựa chọn ban đầu. Nếu biết trước trạng thái đích sẽ xuất hiện trong phạm vi độ sâu nào đó của cây tìm kiếm thì chúng ta đặt giới hạn độ sâu đó cho giải thuật. Tuy nhiên nếu chọn độ sâu tối đa không phù hợp, giải thuật tìm kiếm theo chiều sâu có giới hạn sẽ không tìm được lời giải của bài toán. Chúng ta có thể gọi thực hiện giải thuật tìm kiếm lời giải ở độ sâu khác nhau, từ bé đến lớn. Giải thuật bổ sung như sau: Function Iterative-deepening-Search(problem) returns a solution, or failure for depth = 0 to ∞ do result Å Depth-Limited-Search(problem, depth) if result succeeds then return result end return failure
Chương 3 –Các phương pháp tìm kiếm heuristic 1. Giải thuật tìm kiếm tốt nhất đầu tiên (best first search) Các giải thuật trong mục 4 ở trên có chung đặc điểm là tìm kiếm lời giải một cách có hệ thống: xây dựng tất cả không gian lời giải tiềm năng theo cách vét cạn, không bỏ sót và không lặp lại. Trong rất nhiều trường hợp, các giải thuật như vậy không khả thi vì không gian trạng thái bài toán quá lớn, tốc độ xử lý và bộ nhớ của máy tính không cho phép duyệt các lời giải tiềm năng. Để hạn chế không gian cây các lời giải tiềm năng, chúng ta đưa ra một hàm định hướng việc mở rộng cây tìm kiếm. Theo cách này, chúng ta sẽ mở rộng cây theo các nút lá có nhiều tiềm năng chứa trạng thái đích hơn các nút lá khác. Ví dụ, đối với bài toán 8 số, chúng ta đưa ra một hàm định hướng mở rộng cây như sau: giả sử n là một trạng thái bàn cờ (một sự sắp xếp 8 quân cờ trên bàn cờ 3x3), hàm định hướng h định nghĩa như sau: h(n) = tổng khoảng cách Manhatan các vị trí của từng quân cờ trên bàn cờ n với vị trí của nó trên bàn cờ đích. Chẳng hạn, nếu n là trạng thái đầu như trong hình của mục 1.b, h(n) có thể xác định như sau: Quân cờ Vị trí trên n Vị trí trên bàn Khoảng cách (số lần dịch cờ đích chuyển khi bàn cờ không có quân cờ khác) Trạng thái n là trạng thái đầu của bài toán 8 số trong mục 1.b 1 (3,3) (1,3) 2 2 (2,3) (2,3) 0 3 (3,2) (3,3) 1
4 (1,1) (1,2) 1 5 (1,3) (2,2) 2 6 (3,1) (3,2) 1 7 (1,2) (1,1) 1 8 (2,1) (2,1) 0 h(n) = 2 + 0 + 1 + 1 + 2 + 1 + 1 + 0 = 8 Hàm h(n) như mô tả ở trên phản ánh sự “khác nhau” giữa trạng thái n với trạng thái đích, h(n) càng nhỏ thì n càng “giống” với trạng thái đích, khi n trùng với trạng thái đích thì h(n) = 0. Khi không gian bài toán quá lớn, việc mở rộng cây theo chiến lược theo chiều rộng hoặc theo chiều sâu dẫn đến cây tìm kiếm quá lớn mà không chứa lời giải của bài toán. Khi đó chúng ta cần mở rộng cây theo hướng các nút lá có nhiều triển vọng chứa trạng thái đích, và hàm h(n) sẽ giúp chúng ta mở rộng cây. Chúng ta sẽ mở rộng cây theo hướng các nút lá có hàm h(n) nhỏ nhất. Khi đó h được gọi là thông tin phản hồi của quá trình mở rộng cây là có hợp lý hay không (vì thế mà các phương pháp tìm kiếm trong mục này gọi là tìm kiếm có phản hồi - informed search, chúng cũng có tên là tìm kiếm heuristic - dựa trên hàm đánh giá hợp lý h). Để mở rộng cây theo nút lá có giá trị h nhỏ nhất, chúng ta sử dụng một cấu trúc dữ liệu là danh sách (list) có sắp xếp theo giá trị h. Giải thuật chi tiết được trình bày trong bảng sau (được gọi là giải thuật Best-First-Search):
Function Best-First-Search(problem, list, h) returns a solution, or failure list Å make-list(make-node(initial-state[problem])); father(initial-state[problem]) = empty; while (1) if list is empty then return failure; node = pop(list) ; // node with max/min h if test(node,Goal[problem]) then return path(node,father); expand-nodes Åadjacent-nodes(node, Operators[problem]); push(list, expand-nodes ,h); foreach ex-node in expand-nodes father(ex-node) = node; end Function push(list, expand-nodes ,h); Chèn các nodes trong expand-nodes vào list sao cho mảng list sắp theo thứ tự tăng/giảm theo hàm h Chú ý rằng, cấu trúc giải thuật này giống với các giải thuật tìm kiếm theo chiều rộng hay theo chiều sâu, chỉ khác ở chỗ, thay vì sử dụng hàng đợi hay ngăn xếp để lưu giữ các trạng thái lá của cây tìm kiếm, chúng ta sử dụng danh sách sắp xếp theo giá trị hàm h. Danh sách sắp xếp tăng hay giảm phụ thuộc vào hàm h và ngữ cảnh của bài toán, ví dụ bài toán 8 số và hàm h định nghĩa ở trên, danh sách cần sắp xếp theo thứ tự tăng dần để khi lấy phần tử ở đầu danh sách ta cẽ được nút lá “gần” với đích nhất. Hình vẽ sau minh họa việc mở rộng cây tìm kiếm khi sử dụng giải thuật trên:
Cây có gốc là trạng thái đầu với giá trị h(đầu) = 8. Từ trạng thái gốc có hai phép chuyển: chuyển ô trống đổi vị trí cho ô số 7 (hàm h giảm đi 1) và đổi vị trí ô trống cho ô số 8 (hàm h tăng lên 1). Lúc này danh sách sắp xếp có 2 nút lá tương ứng với hai trạng thái có hàm h=7 và h=9. Trong 2 nút lá này, giải thuật sẽ chọn nút có giá trị hàm h nhỏ hơn (h=7) để mở rộng cây. Tiếp tục mở rộng cây theo hướng nút lá có giá trị h nhỏ nhất (trong trường hợp có nhiều nút lá cùng có giá trị nhỏ nhất thì chọn nút lá nào xuất hiện trước) thì ta được một phần của cây như trong hình vẽ trên. 2. Các biến thể của giải thuật best first search Ý tưởng của giải thuật tìm kiếm tốt nhất đầu tiên (best first search) là mở rộng cây tìm kiếm theo hướng ưu tiên các nút lá có triển vọng chứa trạng thái đích (dựa trên hàm đánh giá h). Giải thuật best-first-search có các biến thể sau: - Khi hàm h(n) là chi phí của dãy phép chuyển từ trạng thái đầu đến trạng thái n thì giải thuật best-first-search có tên gọi khác là giải thuật tìm kiếm đều (uniform search). Trong
trường hợp này, cây tìm kiếm sẽ mở rộng đều về tất cả các hướng theo vết dầu loang từ trạng thái đầu. Khi hàm chi phí của dãy phép chuyển là số các đỉnh trung gian thì giải thuật uniform search trở thành giải thuật tìm kiếm theo chiều rộng. Giải thuật uniform search sẽ cho lời giải với chi phí nhỏ nhất, tuy nhiên cây tìm kiếm sinh ra trong giải thuật này thường có kích thước rất lớn. - Khi h(n) là ước lượng chi phí/khoảng cách từ n đến đích (ví dụ như khoảng cách Manhatan trong bài toán 8 số ở trên) thì giải thuật best-first-search được gọi là giải thuật tham ăn (greedy search). Giải thuật tham ăn sẽ chọn nút lá n “gần” đến đích nhất trong số các nút lá của cây tìm kiếm để mở rộng cây, và nó không quan tâm đến chi phí từ trạng thái đầu đến n. Do vậy giải thuật có xu hướng cho ra kết quả trong thời gian nhanh nhất, nhưng không phải lúc nào cũng là lời giải ngắn nhất. - Khi h(n) = f(n) + g(n), trong đó f(n) là hàm chi phí/khoảng cách từ trạng thái đầu đến n và g(n) là hàm ước lượng chi phí/khoảng cách từ n đến trạng thái đích, và nếu g(n) là ước lượng dưới của hàm chi phí/khoảng cách thực sự từ n đến trạng thái đích thì giải thuật best-first-search được gọi là giải thuật A*. Giải thuật A* là giải thuật trung hòa giữa hai giải thuật uniform và giải thuật greedy ở trên. A* cho lời giải có chi phí nhỏ nhất (bạn đọc có thể tìm hiểu chứng minh điều này ở các tài liệu khác) và cây tìm kiếm có kích thước vừa phải.
Ví dụ, đối với bài toán tìm đường đi từ thành phố Arad đến thành phố Bucharest đã mô tả trong 1.b, nếu chúng ta sử dụng khoảng cách Ơclit (khoảng cách theo đường chim bay) từ mỗi thành phố đến đích (xem hình vẽ trên) thì các giải thuật uniform, greedy và A* sẽ cho các cây tìm kiếm như sau: Một phần cây tìm kiếm của giải thuật Uniform search
Cây tìm kiếm của giải thuật Greedy search Cây tìm kiếm của giải thuật A* 3. Các giải thuật khác * Tìm kiếm leo đồi:
Ý tưởng: Tìm kiếm theo chiều sâu kết hợp với hàm đánh giá. Mở rộng trạng thái hiện tại và đánh giá các trạng thái con của nó bằng hàm đánh giá heuristic. Tại mỗi bước, nút lá “tốt nhất” sẽ được chọn để đi tiếp. Procedure Hill-Climbing_search; Begin 1. Khởi tạo ngăn xếp S chỉ chứa trạng thái đầu; 2. Loop do 2.1 If S rỗng then {thông báo thất bại; stop}; 2.2 Lấy trạng thái u ở đầu ngăn xếp S; 2.3 If u là trạng thái kết thúc then {thông báo thành công; stop}; 2.4 For mỗi trạng thái v kề u do đặt v vào danh sách L; 2.5 Sắp xếp L theo thứ tự tăng dần của hàm đánh giá sao cho trạng thái tốt nhất ở đầu danh sách L; 2.6 Chuyển danh sách Lvào ngăn xếp S; End; Ví dụ : Với ví dụ đồ thị không gian trạng thái như hình 2.2 thì cây tìm kiếm leo đồi tương ứng như hình 2.4 :
A 20 C 15 E 7 6 D F I 10 8 B G 0 5 Cây tìm kiếm leo đồi Hạn chế của thuật toán : - Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ: + Lời giải tìm được không tối ưu + Không tìm được lời giải mặc dù có tồn tại lời giải - Giải thuật có thể gặp vòng lặp vô hạn do không lưu giữ thông tin về các trạng thái đã duyệt. * Tìm kiếm Beam Để hạn chế không gian tìm kiếm, người ta đưa ra phương pháp tìm kiếm Beam. Đây là phương pháp tìm kiếm theo chiều rộng nhưng có hạn chế số đỉnh phát triển ở mỗi mức. Trong tìm kiếm theo chiều rộng, tại mỗi mức ta phát triển tất cả các đỉnh, còn tìm kiếm Beam thì chọn k đỉnh tốt nhất để phát triển. Các đỉnh này được xác định bởi hàm đánh giá. Ví dụ, với đồ thì không gian trạng thái như hình 2.2 và lấy k=2 thì cây tìm kiếm Beam như hình 2.5. Các đỉnh được chọn ở mỗi mức là các đỉnh được tô màu đỏ:
A 20 C 15 E 7 6 D K 12 F I G 10 8 5 B 0 5 G B H 0 3 Cây tìm kiếm Beam * Tìm kiếm nhánh cận Ý tưởng : thuật toán tìm kiếm leo đồi kết hợp với hàm đánh giá f(u). Tại mỗi bước, khi phát triển trạng thái u, chọn trạng thái con v tốt nhất (f(v) nhỏ nhất) của u để phát triển ở bước sau. Quá trình tiếp tục như vậy cho đến khi gặp trạng thái w là đích, hoặc w không có đỉnh kề, hoặc w có f(w) lớn hơn độ dài đường đi tối ưu tạm thời (đường đi đầy đủ ngắn nhất trong số những đường đi đầy đủ đã tìm được). Trong các trường hợp này, chúng ta không phát triển đỉnh w nữa, tức là cắt bỏ những nhánh xuất phát từ w, và quay lên cha của w để tiếp tục đi xuống trạng thái tốt nhất trong số những trạng thái còn lại chưa được phát triển. Procedure Branch-and-Bound; Begin 1. Khởi tạo ngăn xếp S chỉ chứa trạng thái đầu; Gán giá trị ban đầu cho cost; /*cost là giá trị đường đi tối ưu tạm thời*/ 2. Loop do 2.1 If S rỗng then {thông báo thất bại; stop}; 2.2 Lấy trạng thái u ở đầu ngăn xếp S;
2.3 If u là trạng thái kết thúc then if g(u) cost then quay lại 2.1; 2.5 For mỗi trạng thái v kề u do {g(v) ←g(u)+k(u,v); f(v) ←g(v) +h(v); đặt v vào danh sách L1}; 2.6 Sắp xếp L theo thứ tự tăng dần của hàm f; 2.7 Chuyển danh sách Lvào ngăn xếp S; End; Ví dụ : Với đồ thị không gian trạng thái như hình 2.7, đỉnh xuất phát A và đỉnh đích B. Áp dụng thuật toán nhánh – cận, ta xây dựng được cây tìm kiếm như hình 2.9 và giá trị của hàm f tại các đỉnh được tính như bảng 2.2: Đỉnh phát Đỉnh con g(v) f(v) Đỉnh triển (u) (v) chọn A C 9 9+15=24 D 7 7+6=13 D E 13 13+8=21 F 20 20+7=27 14 D H 7+8=15 15+10=25 A E 7+4=11 11+8=19 E 27 E K 11+4=15 15+2=17 K F I 11+3=14 14+4=18 I K B 15+6=21 21+0=21 21 24 C 13 D E B cost := 21 I K 14+9=23 23+2=25 B 14+5=19 19+0=19 B 25 H B cost := 19 E 19 Tính giá trị hàm f cho thuật toán nhánh-cận 17 K I 18 21 B 19 B K 25 Cây tìm kiếm nhánh-cận
Nhận xét : Thuật toán nhánh-cận cũng là thuật toán đầy đủ và tối ưu nếu h(u) là hàm đánh giá thấp và có độ dài các cung không nhỏ hơn một số dương δ nào đó
Chương 4 – Các giải thuật tìm kiếm lời giải cho trò chơi Chương trình chơi cờ đầu tiên được viết bởi Claude Shannon vào năm 1950 đã là một minh chứng cho khả năng máy tính có thể làm được những việc đòi hỏi trí thông minh của con người. Từ đó người ta nghiên cứu các chiến lược chơi cho máy tình với các trò chơi có đối thủ (có hai người tham gia). Việc giải quyết bài toán này có thể đưa về bài toán tìm kiếm trong không gian trạng thái, tức là tìm một chiến lược chọn các nước đi hợp lệ cho máy tính. Tuy nhiên, vấn đề tìm kiếm ở đây phức tạp hơn so với vấn đề tìm kiếm trong chương trước, vì người chơi không biết trước đối thủ sẽ chọn nước đi nào tiếp theo. Chương này sẽ trình bày một số chiến lược tìm kiếm phổ biến như Minimax, phương pháp cắt cụt α-β. 1. Cây trò chơi đầy đủ Các trò chơi có đối thủ có các đặc điểm: hai người thay phiên nhau đưa ra các nước đi tuân theo các luật của trò chơi (các nước đi hợp lệ), các luật này là như nhau đối với cả hai người chơi, chẳng hạn các trò chơi cờ: cờ vua, cờ tướng, cờ ca rô (tic-tăc-toe), . Ví dụ, trong chơi cờ vua, một người điều khiển quân Trắng và một người điều khiển quân Đen. Người chơi có thể lựa chọn các nước đi theo các luật với các quân tốt, xe, mã, Luật đi quân tốt Trắng, xe Trắng, mã Trắng, giống luật đi quân tốt Đen, xe Đen, mã Đen, Hơn nữa, cả hai người chơi đều biết đầy đủ các thông tin về tình thế cuộc chơi. Thực hiện trò chơi là người chơi tìm kiếm nước đi tốt nhất trong số rất nhiều nước đi hợp lệ, tại mỗi lượt chơi của mình, sao cho sau một dãy nước đi đã thực hiện người chơi phải thắng cuộc. Vấn đề chơi cờ có thể được biểu diễn trong không gian trạng thái, ở đó, mỗi trạng thái là một tình thế của cuộc chơi (sự sắp xếp các quân cờ trên bàn cờ): - Trạng thái xuất phát là sự sắp xếp các quân cờ của hai bên khi bắt đầu cuộc chơi (chưa ai đưa ra nước đi) - Các toán tử biến đổi trạng thái là các nước đi hợp lệ
- Các trạng thái kết thúc là các tình thế mà cuộc chơi dừng, thường được xác định bởi một số điều kiện dừng (chẳng hạn, quân Trắng thắng hoặc quân Đen thắng hoặc hai bên hòa nhau) - Hàm kết cuộc: mang giá trị tương ứng với mỗi trạng thái kết thúc. Chẳng hạn, trong cờ vua, hàm kết cuộc có giá trị là 1 tại các trạng thái mà Trắng thắng, -1 tại các trạng thái mà Trắng thua và 0 tại các trạng thái hai bên hòa nhau. Trong các trò chơi tính điểm khác thì hàm kết cuộc có thể nhận các giá trị nguyên trong đoạn [-m, m], với m là một số nguyên dương nào đó. Như vậy, trong các trò chơi có đối thủ, người chơi (điều khiển quân Trắng – gọi tắt là Trắng) luôn tìm một dãy các nước đi xen kẽ với các nước đi của đối thủ (điều khiển quân Đen – gọi tắt là Đen) để tạo thành một đường đi từ trạng thái ban đầu đến trạng thái kết thúc là thắng cho Trắng. Không gian tìm kiếm đối với các trò chơi này có thể được biểu diễn bởi cây trò chơi như sau: gốc của cây ứng với trạng thái xuất phát, các đỉnh trên cây tương ứng với các trạng thái của bàn cờ, các cung (u, v) nếu có biến đổi từ trạng thái u đến trạng thái v. Các đỉnh trên cây được gán nhãn là đỉnh Trắng (Đen) ứng với trạng thái mà quân Trắng (Đen) đưa ra nước đi. Nếu một đỉnh u được gán nhãn là Trắng (Đen) thì các đỉnh con v của nó là tất cả các trạng thái nhận được từ u do Trắng (Đen) thực hiện một nước đi hợp lệ nào đó. Do đó, các đỉnh trên cùng một mức của cây đều có nhãn là Trắng hoặc đều có nhãn là Đen, các lá của cây ứng với trạng thái kết thúc. Ví dụ: trò chơi Dodgem: Có hai quân Trắng và hai quân Đen được xếp vào bàn cờ 3x3. Ban đầu các quân cờ được xếp như hình bên. Quân Đen có thể đi đến ô trống bên phải, ở trên hoặc ở dưới. Quân Trắng có thể đi đến ô trống bên trên, bên trái hoặc bên phải. Quân Đen nếu ở cột ngoài cùng bên phải có thể đi ra khỏi bàn cờ, quân Trắng nếu ở hàng trên cùng có thể Trò chơi Dodgem đi ra khỏi bàn cờ. Ai đưa được cả hai quân của mình ra khỏi bàn cờ hoặc tạo ra tình thế mà đối phương không đi được là thắng cuộc.
Đen Trắng Đen Cây trò chơi Dodgem với Đen đi trước 2. Giải thuật Minimax Quá trình chơi cờ là quá trình mà Trắng và Đen thay phiên nhau đưa ra các nước đi hợp lệ cho đến khi dẫn đến trạng thái kết thúc cuộc chơi. Quá trình này biểu diễn bởi đường đi từ nút gốc tới nút lá trên cây trò chơi. Giả sử tại một đỉnh u nào đó trên đường đi, nếu u là đỉnh Trắng (Đen) thì cần chọn một nước đi nào đó đến một trong các đỉnh con Đen (Trắng) v của u. Tại đỉnh Đen (Trắng) v sẽ chọn đi tiếp đến một đỉnh con Trắng (Đen) w của v. Quá trình này tiếp tục cho đến khi đạt đến một đỉnh lá của cây. Chiến lược tìm nước đi của Trắng hay Đen là luôn tìm những nước đi dẫn tới trạng thái tốt nhất cho mình và tồi nhất cho đối thủ. Giả sử Trắng cần tìm nước đi tại đỉnh u, nước đi tối ưu cho Trắng là nước đi dẫn tới đỉnh con v sao cho v là tốt nhất trong số các đỉnh con của u. Đến lượt Đen chọn nước đi từ v, Đen cũng chọn nước đi tốt nhất cho mình. Để chọn nước đi tối ưu cho Trắng tại đỉnh u, cần xác định giá trị các đỉnh của cây trò chơi gốc u. Giá trị của các đỉnh lá ứng với giá trị của hàm kết cuộc. Đỉnh có giá trị càng lớn càng tốt cho Trắng, đỉnh có giá trị càng nhỏ càng tốt cho Đen. Để xác định giá trị các đỉnh của cây trò chơi gốc u, ta đi từ mức thấp nhất (các đỉnh lá) lên gốc u. Giả sử cần xác định giá trị của đỉnh v mà các đỉnh con của nó đã xác định. Khi đó, nếu v là đỉnh Trắng
thì giá trị của nó là giá trị lớn nhất trong các đỉnh con, nếu v là đỉnh Đen thì giá trị của nó là giá trị nhỏ nhất trong các đỉnh con. Sau đây là thủ tục chọn nước đi cho Trắng tại đỉnh u Minimax(u, v), trong đó v là đỉnh con được chọn của u: Procedure Minimax(u, v); begin val ←-∝; for mỗi w là đỉnh con của u do if val(u) <= MinVal(w) then {val ← MinVal(w); v ← w} end; Function MinVal(u); {hàm xác định giá trị cho các đỉnh Đen} begin if u là đỉnh kết thúc then MinVal(u) ← f(u) else MinVal(u) ← min{MaxVal(v) | v là đỉnh con của u} end; Function MaxVal(u); { hàm xác định giá trị cho các đỉnh Trắng} begin if u là đỉnh kết thúc then MaxVal(u) ← f(u) else MaxVal(u) ← max{MinVal(v) | v là đỉnh con của u} end; Trong các thủ tục và hàm trên, f(u) là giá trị của hàm kết cuộc tại đỉnh kết thúc u. Thuật toán Minimax là thuật toán tìm kiếm theo chiều sâu. Về lý thuyết, chiến lược Minimax cho phép tìm nước đi tối ưu cho Trắng. Tuy nhiên trong thực tế, ta không có đủ thời gian để tính toán nước đi tối ưu này. Bởi vì thuật toán tính toán trên toàn bộ cây trò
chơi (xem xét tất cả các đỉnh của cây theo kiểu vét cạn). Trong các trò chơi hay thì kích thước của cây trò chơi là cực lớn. Chẳng hạn, trong cờ vua, chỉ tính đến độ sâu 40 thì cây trò chơi đã có đến 10120 đỉnh. Nếu cây có độ cao m và tại mỗi đỉnh có b nước đi thì độ phức tạp về thời gian của thuật toán Minimax là O(bm). Trong thực tế, các trò chơi đều có giới hạn về thời gian. Do đó, để có thể tìm nhanh nước đi tốt (không phải tối ưu) thay vì sử dụng hàm kết cuộc và xét tất cả các đỉnh của cây trò chơi, ta sử dụng hàm đánh giá và chỉ xem xét một bộ phận của cây trò chơi. 3. Giải thuật Minimax với độ sâu hạn chế a) Hàm đánh giá Hàm đánh giá eval cho mỗi đỉnh u là đánh giá “mức độ lợi thế” của trạng thái u. Giá trị của eval(u) là số dương càng lớn thì trạng thái u càng có lợi cho Trắng, giá trị của eval(u) là số dương càng nhỏ thì trạng thái u càng có lợi cho Đen, eval(u)=0 thì trạng thái u không có lợi cho đối thủ nào, eval(u)=+∝ thì u là trạng thái thắng cuộc cho Trắng, eval(u)=-∝ thì u là trạng thái thắng cuộc cho Đen. Hàm đánh giá đóng vai trò rất quan trọng trong các trò chơi, nếu hàm đánh giá tốt sẽ định hướng chính xác việc lựa chọn các nước đi tốt. Việc thiết kế hàm đánh giá phụ thuộc vào nhiều yếu tố: các quân cờ còn lại của hai bên, sự bố trí các quân cờ này, Để đưa ra hàm đánh giá chính xác đòi hỏi nhiều thời gian tính toán, tuy nhiên, trong thực tế người chơi bị giới hạn thời gian đưa ra nước đi. Vì vậy, việc đưa ra hàm đánh giá phụ thuộc vào kinh nghiệm của người chơi. Sau đây là một số ví dụ về cách xây dựng hàm đánh giá: Ví dụ 1: Hàm đánh giá cho cờ vua. Mỗi loại quân được gán một giá trị số phù hợp với “sức mạnh” của nó. Chẳng hạn, quân tốt Trắng (Đen) được gán giá trị 1 (-1), mã hoặc tượng Trắng (Đen) được gán giá trị 3 (-3), xe Trắng (Đen) được gán giá trị 5 (-5) và hậu Trắng (Đen) được gán giá trị 9 (-9). Hàm đánh giá của một trạng thái được tính bằng cách lấy tổng giá trị của tất cả các quân cờ trong trạng thái đó. Hàm đánh giá này được gọi là hàm tuyến tính có trọng số, vì có thể biểu diễn dưới dạng:
s1w1 + s2w2 + + snwn Trong đó, wi là giá trị của quân cờ loại i, si là số quân loại đó. Đây là cách đánh giá đơn giản, vì nó không tính đến sự bố trí của các quân cờ, các mối tương quan giữa chúng. Ví dụ 2: Hàm đánh giá trạng thái trong trò chơi Dodgem. Mỗi quân Trắng được gán giá trị tương ứng với các vị trí trên bàn cờ như trong hình bên trái. Mỗi quân Đen được gán giá trị ở các vị trí tương ứng nhu hình bên phải: 30 35 40 -10 -25 -40 15 20 25 -5 -20 -35 0 5 10 0 -15 -30 Ngoài ra, nếu quân Trắng cản trực tiếp một quân Đen, nó được thêm 40 điểm, nếu cản gián tiếp được thêm 30 điểm (xem hình dưới). Tương tự, nếu quân Đen cản trực tiếp quân Trắng nó được thêm -40 điểm, cản gián tiếp được thêm -30 điểm. Trắng cản trực tiếp Đen Trắng cản gián tiếp Đen được thêm 40 điểm được thêm 30 điểm Áp dụng cách tính hàm đánh giá nêu trên, ta tính được giá trị của các trạng thái ở các hình dưới như sau:
Giá trị hàm đánh giá:75= Giá trị hàm đánh giá:-5= (-10+0+5+10)+(40+30) (-25+0+20+10)+(-40+30) b) Thuật toán Để hạn chế không gian tìm kiếm, khi xác định nước đi cho Trắng tại u, ta chỉ xem xét cây gốc u tại độ cao h nào đó. Áp dụng thủ tục Minimax cho cây trò chơi gốc u, độ cao h và sử dụng hàm đánh giá để xác định giá trị cho các lá của cây. Procedure Minimax(u, v, h); begin val ←-∝; for mỗi w là đỉnh con của u do if val(u) <= MinVal(w, h-1) then {val ← MinVal(w, h-1); v ← w} end; Function MinVal(u, h); {hàm xác định giá trị cho các đỉnh Đen} begin if u là đỉnh kết thúc or h = 0 then MinVal(u, h) ← eval(u) else MinVal(u, h) ← min{MaxVal(v, h-1) | v là đỉnh con của u} end; Function MaxVal(u, h); { hàm xác định giá trị cho các đỉnh Trắng} begin if u là đỉnh kết thúc or h =0 then MaxVal(u, h) ← eval(u) else MaxVal(u, h) ← max{MinVal(v, h-1) | v là đỉnh con của u} end;
4. Giải thuật Minimax với cắt tỉa alpha-beta Trong chiến lược Minimax với độ sâu hạn chế thì số đỉnh của cây trò chơi phải xét vẫn còn rất lớn với h>=3. Khi đánh giá đỉnh u tới độ sâu h, thuật toán Minimax đòi hỏi phải đánh giá tất cả các đỉnh của cây gốc u với độ sâu h. Tuy nhiên, phương pháp cắt cụt alpha-beta cho phép cắt bỏ những nhánh không cần thiết cho việc đánh giá đỉnh u. Phương pháp này làm giảm bớt số đỉnh phải xét mà không ảnh hưởng đến kết quả đánh giá đỉnh u. Ý tưởng: Giả sử tại thời điểm hiện tại đang ở đỉnh Trắng a, đỉnh a có anh em là v đã được đánh giá. Giả sử cha của đỉnh a là b, b có anh em là u đã được đánh giá, và cha của b là c như hình sau: c max u b min v a max Cắt bỏ cây con gốc a nếu eval(u)>eval(v) Khi đó ta có giá trị đỉnh Trắng c ít nhất là giá trị của u, giá trị của đỉnh Đen b nhiều nhất là giá trị của v. Do đó, nếu eval(u) > eval(v) ta không cần đi xuống để đánh giá đỉnh a nữa mà vẫn không ảnh hưởng đến đánh giá đỉnh c. Hay nói cách khác, ta có thể cắt bỏ cây con gốc a. Lập luận tương tự cho trường hợp a là đỉnh Đen, trường hợp này nếu eval(u)<eval(v) ta cũng cắt bỏ cây con gốc a. Để cài đặt kỹ thuật này, đối với các đỉnh nằm trên đường đi từ gốc tới đỉnh hiện thời, ta sử dụng tham số α để ghi lại giá trị lớn nhất trong các giá trị của các đỉnh con đã đánh giá
của một đỉnh Trắng, tham số β để ghi lại giá trị nhỏ nhất trong các giá trị của các đỉnh con đã đánh giá của một đỉnh Đen. Thuật toán: Procedure Alpha_beta(u, v); begin α←-∝; β←-∝; for mỗi w là đỉnh con của u do if α = β then exit}; /*cắt bỏ các cây con từ các đỉnh v còn lại */ MinVal(u, α, β) ← β; end; Function MaxVal(u, α, β); { hàm xác định giá trị cho các đỉnh Trắng} begin if u là đỉnh kết thúc or là lá của cây hạn chế then MaxVal(u, α, β) ← eval(u) Else for mỗi đỉnh v là con của u do
α ← max{α, MinVal(v, α, β)} ; If α >= β then exit}; /*cắt bỏ các cây con từ các đỉnh v còn lại */ MaxVal(u, α, β) ← α end;