Trí tuệ nhân tạo - Nguyễn Ngọc Hiếu

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo1TRÍ TUỆ NHÂN TẠONguyễn Ngọc HiếuKhoa Công nghệ Thông tinTrường Đại học VinhEmail: hieunn@gmail.comNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo2NỘI DUNGTỔNG QUAN VỀ KHOA HỌC TTNTCÁC PHƯƠNG PHÁP BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀNGÔN NGỮ TTNT PROLOGNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo3TÀI LIỆU THAM KHẢO1. Trí tuệ nhân tạo – Các phương pháp Giải quyết vấn đề và kỹ thuật xử lý tri thức (1999)Nguyễn Thanh Thuỷ2. Lập trình lôgic trong Prolog (2004) Phan Huy Khánh 3. Artificial Intelligence: A Modern Approach (2nd edition, 2002) Stuart Russell & Peter NorvigNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo4ĐÁNH GIÁTham dự bài giảng: 10%Thi giữa kỳ: 20%Thi cuối kỳ: 70%Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo5KHỐI LƯỢNG & CẤU TRÚC HỌC PHẦNSố đơn vị học trình: 3Lý thuyết: 35 tiếtThực hành, bài tập: 10 tiếtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo6TỔNG QUAN VỀ KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo7NỘI DUNGCÁC KHÁI NIỆM CƠ BẢNCÁC TIỀN ĐỀ CƠ BẢN CỦA TTNTLỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTCÁC THÀNH TỰU CỦA KHOA HỌC TTNTCÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo8CÁC KHÁI NIỆM CƠ BẢN:TTNT là gì?Trí tuệ nhân tạo là khoa học liên quan đến việc làm cho máy tính có những khả năng của trí tuệ con người, tiêu biểu như các khả năng“suy nghĩ”, “hiểu ngôn ngữ”, và biết “học tập”. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo9Intelligence: trí thông minh “ability to learn, understand and think” (Oxford dictionary)Artificial Intelligence (AI): trí thông minh nhân tạo “attempts to understand intelligent entities” “strives to build intelligent entities”(Stuart Russell & Peter Norvig)CÁC KHÁI NIỆM CƠ BẢN:TTNT là gì?Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo10CÁC KHÁI NIỆM CƠ BẢN:TTNT là gì?Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo11CÁC KHÁI NIỆM CƠ BẢN:TTNT và lập trình truyền thốngNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo12Thinking humanly(Suy nghĩ như con người)Thinking rationally(Suy nghĩ hợp lý)Acting humanly(Hành động như con người)Acting rationally(Hành động hợp lý)CÁC KHÁI NIỆM CƠ BẢN:Các yêu cầu của TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo13CÁC KHÁI NIỆM CƠ BẢN:Hành động như con người:Phép thử TuringAlan Turing (1912-1954)“Computing Machinery and Intelligence” (1950)Phép thửNgười kiểm traNgườiHệ thống TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo14Chỉ ra các lĩnh vực cần nghiên cứu trong AI: Xử lý ngôn ngữ tự nhiên: để giao tiếpBiểu diễn tri thức: để lưu trữ và phục hồi các thông tin được cung cấp trước/trong quá trình thẩm vấnSuy diễn tự động: để sử dụng các thông tin đã được lưu trữ trả lời các câu hỏi và đưa ra các kết luận mớiHọc máy: thích nghi với các tình huống mới, phát hiện và suy ra các mẫu CÁC KHÁI NIỆM CƠ BẢN:Hành động như con ngườiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo15CÁC KHÁI NIỆM CƠ BẢN:Suy nghĩ như con người: Mô hình nhận thức Con người suy nghĩ ntn ? Nhờ tâm lý học, khoa học nhận thức. Người thuộc trường phái này, yêu cầu: Chương trình chẳng những giải đúngCòn so sánh từng bước giải với sự giải của 1 người. VD: General Problem Solver (GPS), Newell & Simon. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo16CÁC KHÁI NIỆM CƠ BẢN:Suy nghĩ có lý: Luật của suy nghĩAristole: ~420 BC.Tiến trình suy nghĩ đúng là gì? Mở ra nhánh: quá trình suy luận. VD: “Socrates is a man, all men are mortal; therefore Socrates is mortal”Theo sau Aristole -> 20th: Logic hình thức (formal logic) ra đời.Hình thức hoá về mặt ký hiệu và quá trình suy diễn với các đối tượng trong thế giới tự nhiên. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo17CÁC KHÁI NIỆM CƠ BẢN:Hành động có lý Hành động có lý ~ hành động để đạt được mục tiêu. Ưu thế: Tổng quát hơn luật suy nghĩ: Xử lý thông tin không chắc chắnNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo18CÁC KHÁI NIỆM CƠ BẢN:Các phương pháp và kỹ thuậtCác phương pháp biểu diễn tri thức và kỹ thuật xử lý tri thứcCác phương pháp giải quyết vấn đềCác phương pháp HeuristicCác phương pháp họcCác ngôn ngữ TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo19CÁC KHÁI NIỆM CƠ BẢN:Các thành phần trong hệ thốngHai thành phần cơ bản:Các phương pháp biểu diễn vấn đề, các phương pháp biểu diễn tri thứcCác phương pháp tìm kiếm trong không gian bài toán, các chiến lược suy diễnNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo20NỘI DUNGCÁC KHÁI NIỆM CƠ BẢNCÁC TIỀN ĐỀ CƠ BẢN CỦA TTNTLỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTCÁC THÀNH TỰU CỦA KHOA HỌC TTNTCÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo21CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNTTTNT kế thừa nhiều ý tưởng, quan điểm và các kỹ thuật từ các ngành khoa học khácTTNTTâm lý họcNgôn ngữ học Khoa học máy tínhTriết họcToán họcCác lý thuyết của lập luận và họcCác lý thuyết xác suất logic, tạo quyết định và tính toánLàm cho TTNT trở thành hiện thựcNghiên cứu ý nghĩa và cấu trúc của ngôn ngữNghiên cứu tâm trí con ngườiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo22NỘI DUNGCÁC KHÁI NIỆM CƠ BẢNCÁC TIỀN ĐỀ CƠ BẢN CỦA TTNTLỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTCÁC THÀNH TỰU CỦA KHOA HỌC TTNTCÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo23LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTBắt đầu của AI (1943 - 1956): 1943: McCulloch & Pitts: Mô hình chuyển mạch logic.1950: Bài báo “Computing Machinery and Intelligence” của Turing.1956: McCarthy đề xuất tên gọi “Artificial Intelligence”.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo24“birth day”: Hội nghị ở Dartmouth College mùa hè 1956, do Minsky và McCarthy tổ chức, và ở đây McCarthy đề xuất tên gọi “artificial intelligence”. Có Simon và Newell trong những người tham dự.John McCarthyMarvin MinskyLỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo25Trông mong nhất (1952 - 1969): Một số chương trình TTNT thành công:Samuel’s checkers Newell & Simon’s Logic TheoristGelernter’s Geometry Theorem Prover.Thuật giải của Robinson cho lập luận logic. LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo26Thực tế (1966 − 1974): Phát hiện được các khó khăn về độ phức tạp tính toán.Quyến sách của Minsky & Papert năm 1969.Hệ thống dựa trên tri thức (1969 − 1979): 1969: DENDRAL by Buchanan et al.Đưa ra cấu trúc phân tử từ thông tin của quang phổ kế1976: MYCIN by Shortliffle.Chuẩn đoán nhiểm trùng máu 1979: PROSPECTOR by Duda et al.Chuẩn đoán vị trí khoan dầu LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo27TTNT trở thành ngành công nghiệp (1980 - 1988):Bùng nổ về các hệ chuyên gia.1981: Đề án máy tính thế hệ thứ năm của Nhật Bản.Sự trở lại của các mạng nơron và lý thuyết TTNT (1986 - nay)LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo28LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo29NỘI DUNGCÁC KHÁI NIỆM CƠ BẢNCÁC TIỀN ĐỀ CƠ BẢN CỦA TTNTLỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTCÁC THÀNH TỰU CỦA KHOA HỌC TTNTCÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo30CÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo31CÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo32CÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo33SONY AIBOCÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo34Đi bộQuayLên xuống cầu thangHonda Humanoid Robot& AsimoCÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo35CÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo36CÁC THÀNH TỰU CỦA KHOA HỌC TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo37NỘI DUNGCÁC KHÁI NIỆM CƠ BẢNCÁC TIỀN ĐỀ CƠ BẢN CỦA TTNTLỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNTCÁC THÀNH TỰU CỦA KHOA HỌC TTNTCÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo38CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo39CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo40CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo41CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo42CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo43CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo44CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo45CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo46CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo47CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo48CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo49CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo50CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo51CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo52CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo53CÁC XU HƯỚNG MỚI TRONG TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo54Một số chủ đề nghiên cứuGiải thuật di truyền và ứng dụngMạng Nơron nhân tạo và ứng dụngCông nghệ tác tử và ứng dụngKDD và ứng dụngPhân lớp - học có thầyLý thuyết tập thôCây quyết định.....Phân cụm - học không có thầyLuật kết hợp..... . .Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo55CÁC PHƯƠNG PHÁP BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo56NỘI DUNGBIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNTCÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀCÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo57BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT Giải quyết vấn đề và khoa học TTNTGiải quyết vấn đề của con ngườiPhân loại vấn đề & Các đặc trưng cơ bản của vấn đềCác thành phần cơ bản trong hệ thống giải quyết vấn đềNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo58Giải quyết vấn đề và khoa học TTNTHoạt động trí tuệ: vận dụng các kỹ thuật giải quyết vấn đềGiải quyết vấn đề: tìm kiếm trong không gian các lời giải bộ phận có thể có được.Phương pháp biểu diễn vấn đề => Phương pháp giải quyết vấn đề.VD: Biểu diễn bằng logic vị từ => Phương pháp hợp giảiVD: Biểu diễn bằng mạng ngữ nghĩa => Các thủ tục tìm kiếmNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo59Giải quyết vấn đề: duyệt-tìm kiếm trong không gian lời giải => bùng nổ tổ hợp => các thủ tục tìm kiếm HeuristicPhân chia các hệ thống TTNT:Các hệ tìm kiếm thông tin, các hệ hỏi đáp thông minhCác hệ suy diễn – tính toán: dựa vào các mô hình toán học và tri thức chuyên giaCác hệ chuyên giaGiải quyết vấn đề và khoa học TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo60Phát biểu bài toán-Xác định phương pháp bd bài toánSản sinh không gian bài toánBài toán có thể giải nhờ thuật toán đa thứcXác định lời giải nhờ các ngôn ngữ lập trìnhXác định các tri thức đặc biệt để rút gọn không gian TKXây dựng các phương pháp biểu diễn tri thức và suy diễnLựa chọn ngôn ngữ, công cụ phù hợpCác hệ giải quyết vấn đề dựa vào tri thứcBài toán (Vấn đề)ĐSCông nghệ lập trình truyền thốngCông nghệ xử lý tri thức Sơ đồ: Những khía cạnh khác nhau của TTNT Giải quyết vấn đề và khoa học TTNTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo61Giải quyết vấn đề của con người Cách giải quyết vấn đề của con người là mô hình thực tiễn quan trọng để các chuyên gia TTNT tìm cách mô phỏng lại trên máy tính quá trình giải quyết bài toán. Khoa học về nhận thức: Nghiên cứu quá trình tổ chức, lưu trữ, truy nhập, xử lý và thu nạp tri thức trong bộ não người. Tâm lý học nhận thức và khoa học điều khiển: Tạo ra các mô hình tổ chức bộ não.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo62Quá trình xử lý thông tin của con ngườiGiải quyết vấn đề của con ngườiHệ thống thụ cảmCơ quan thụ cảmBộ nhớ đệmHệ thống nhận thứcBộ nhớ dài hạnBộ nhớ làm việcBộ xử lý nhận thứcHệ thống hành độngCơ quan hành độngBộ nhớ đệmKíchthíchTrảlờiHỆ THỐNG XỬ LÝ THÔNG TIN CỦA CON NGƯỜINguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo63Giải quyết vấn đề của con người là một trường hợp riêng của quá trình xử lý thông tin trong bộ não. Đó là việc tìm cách đi từ tình huống ban đầu nào đó đến đích. Giải quyết vấn đề là một hoạt động đặc biệt của hệ thần kinh cần tới quá trình suy nghĩ, tìm kiếm trong không gian lời giải bộ phận để đi đến lời giải cuối cùng.Tuy nhiên, cần lưu ý rằng không phải mọi hoạt động xử lý thông tin đều là giải quyết vấn đề. Giải quyết vấn đề của con ngườiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo64Các chiến lược giải quyết vấn đề:Ước lượng mức độ phức tạp của vấn đề đặt ra: Nếu đơn giản, giải quyết vấn đề nhờ vào một thuật toán tiền định nào đó với các thao tác cơ sở.Nếu phức tạp, các cơ quan não tìm cách hiểu chi tiết nội dung của vấn đề để mã hoá, tìm phương pháp phù hợp.Nới lỏng một vài ràng buộc của bài toán. Giải quyết vấn đề của con ngườiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo65Các chiến lược giải quyết vấn đề:Phương pháp thử - sai: Xuất phát từ tình huống ban đầu, người ta đưa ra các tình huống mới, sau đó so sánh với các ràng buộc để tìm ra các lời giải hợp lý.Phương pháp chia bài toán thành các bài toán con: Từ bài toán phức tạp, con người chia thành các bài toán nhỏ, ít phức tạp cho đến khi gặp các bài toán sơ cấp, giải quyết được ngay.Tổng quát hoá bài toán : Chuyển các thông tin bên ngoài thành các kí hiệu làm cho bài toán dễ giải hơn. Quá trình này tạo ra một mô hình trí tuệ của bài toán, mô hình này thường được gọi không gian bài toán. Giải quyết vấn đề của con ngườiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo66Không gian bài toán bao gồm: Các dạng mẫu ký hiệu, mỗi dạng biểu diễn một trạng thái hay một tình huống bài toán. Các mối liên kết giữa các dạng mẫu ký hiệu, mỗi mối liên kết tương ứng với các phép biến đổi từ dạng này sang dạng khác.Giải quyết vấn đề của con ngườiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo67Phân loại vấn đề & Các đặc trưng cơ bản của vấn đềBài toán 1: Bài toán trò chơi n2-1 số (nN, n>2). 123456789101112131415 Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo68Bài toán 2: Bài toán Tháp Hà nộiPhân loại vấn đề & Các đặc trưng cơ bản của vấn đề321321ABCABCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo69Phân loại vấn đề:Vấn đề (bài toán) phát biểu chỉnh (well-formed problems): Là các bài toán có thể biết được hình trạng đầu, hình trạng đích và có thể quyết định khi nào vấn đề được coi là giải quyết xong. Các bài toán 1 - 2 là những vấn đề được phát biểu chỉnh. Vấn đề (bài toán) phát biểu không chỉnh (ill-formed problems): Là các vấn đề được phát biểu chưa đầy đủ, thiếu dữ kiện. Các bài toán chẩn đoán và điều trị bệnh, bài toán xác định chất lượng sản phẩm là các bài toán phát biểu không chỉnh.Phân loại vấn đề & Các đặc trưng cơ bản của vấn đềNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo70Các đặc trưng cơ bản của vấn đềBài toán có thể phân tích thành các bài toán dễ giải hơn không?Các bước giải của bài toán có thể bỏ qua hay huỷ bỏ hay không?Không gian bài toán có thể đoán trước hay không?Có tiêu chuẩn để xác định lời giải nào đó là tốt đối với bài toán không?Có cần tri thức để giải quyết bài toán hay điều khiển quá trình tìm kiếm không?Cơ sở tri thức để giải quyết bài toán có nhất quán với nội dung không?Có cần tương tác người máy trong quá trình giải quyết không? Phân loại vấn đề & Các đặc trưng cơ bản của vấn đềNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo71Các thành phần cơ bản trong hệ thống giải quyết vấn đềGiải quyết vấn đề: Biểu diễn bài toán và tìm kiếm lời giải trong không gian bài toánHệ thống giải quyết vấn đề:Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo72NỘI DUNGBIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNTCÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀCÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo73CÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀPhương pháp biểu diễn nhờ không gian trạng tháiPhương pháp qui bài toán về các bài toán conPhương pháp biểu diễn vấn đề nhờ logic hình thứcLựa chọn phương pháp biểu diễn thích hợpBiểu diễn vấn đề trong máy tínhBiểu diễn tri thức và giải quyết vấn đềNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo74Phương pháp biểu diễn nhờ KGTTTrạng thái (State) là hình trạng của bài toán Toán tử (Operator) là các phép biến đổi từ trạng thái này sang trạng thái khác Hình trạng đầu, hình trạng cuối của bài toán được gọi là trạng thái đầu, trạng thái cuối Tập tất cả các trạng thái được sinh ra do xuất phát từ trạng thái đầu và áp dụng các toán tử được gọi là không gian trạng thái (state space).Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo75Một cách biểu diễn trực quan đối với không gian trạng thái và các toán tử là sử dụng đồ thị, trong đó, các đỉnh của đồ thị tương ứng với các trạng thái còn các cung tương ứng với các toán tử VD: Bài toỏn trũ chơi n2-1 số (nN, n>2)n = 4 123456789101112131415 Phương pháp biểu diễn nhờ KGTTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo76Phương pháp biểu diễn nhờ KGTTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo77Mỗi trạng thái là một sắp xếp nào đó của các con số từ 1 đến 15 sao cho không có hai ô nào có cùng giá trịHình trạng đầu và cuối tương ứng với các trạng thái đầu và cuốiKhông gian trạng thái đạt được từ trạng thái đầu bao gồm tất cả các hình trạng được sinh ra nhờ áp dụng những phép dịch chuyển chấp nhận được của ô trốngĐối với bài toán này số trạng thái chấp nhận được xấp xỉ (1/2). 16 !  10.5.1012 Các toán tử chính là các phép biến đổi từ trạng thái này sang trạng thái khác bao gồm: dịch ô trống sang phải, sang trái, lên trên, xuống dưới. Đối với một số trạng thái có một số toán tử không áp dụng được.Lời giải của bài toán có thể nhận được nhờ sử dụng quá trình tìm kiếm sau: áp dụng các toán tử vào trạng thái đầu để nhận được những trạng thái mới, sau đó áp dụng các toán tử vào các trạng thái mới này và cứ như vậy cho đến khi đạt đến trạng thái đích.Phương pháp biểu diễn nhờ KGTTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo78Phương pháp qui bài toán về các bài toán conTách bài toán thành các bài toán con sao cho lời giải của tập các bài toán con cho phép xác định lời giải của bài toán ban đầu.Cách tiếp cận này dẫn đến phương pháp biểu diễn vấn đề bằng đồ thị Và /Hoặc.     AHoặc CBEFGHIJVà Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo79Phương pháp qui bài toán về các bài toán conVD: Bài toán Tháp Hà nội (n=3)321321ABCABCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo80n = 3n = 4Phương pháp qui bài toán về các bài toán conNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo81Thông thường, để giải quyết vấn đề người ta cần phân tích logic để thu gọn quá trình tìm kiếm và đôi khi nhờ phân tích logic có thể chứng tỏ được rằng một bài toán nào đó không thể giải được. VD: Bài toán trò chơi n2-1 sốPhương pháp biểu diễn vấn đề nhờ logic hình thức151413121110987654321 Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo82Các dạng logic hình thức được sử dụng để biểu diễn bài toán gồm:Logic mệnh đề Logic vị từPhương pháp biểu diễn bài toán nhờ logic hình thức cho phép:Kiểm tra điều kiện kết thúc trong khi tìm kiếm đối với không gian trạng tháiKiểm tra tính áp dụng được đối với các toán tửChứng minh không tồn tại lời giảiMục đích giải quyết vấn đề dựa trên logic hình thức là chứng minh một phát biểu nào đó trên cơ sở những tiền đề và luật suy diễn đã có.Phương pháp biểu diễn vấn đề nhờ logic hình thứcNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo83Trong nhiều trường hợp, việc giải quyết bài toán dựa trên các thuật ngữ đã được dùng để phát biểu nó là rất khó khăn. Người ta thường lựa chọn một dạng biểu diễn phù hợp nào đó đối với các dữ liệu của bài toán, làm cho bài toán trở nên dễ giải hơn. Lựa chọn phương pháp biểu diễn thích hợpNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo84Việc lựa chọn phương pháp biểu diễn thích hợp nhằm:Tránh giải trực tiếp bài toán đặt ra ban đầu do những khó khăn liên quan tới kích cỡ, trọng số, tầm quan trọng và chi phí xử lý dữ liệu của bài toán.Bỏ bớt những thông tin thừa hoặc không quan trọng trong bài toánTận dụng những phương pháp giải đã có đối với bài toán nhận được sau khi phát biểu lạiCách phát biểu mới có thể cho phép thể hiện một vài tương quan nào đó giữa các yếu tố của bài toán nhằm thu gọn quá trình giảiSau khi đã giải quyết xong bài toán theo cách biểu diễn mới, cần phải diễn giải lời giải nhận được cho sát với bài toán thực tế và chứng minh rằng cách diễn giải đó thực sự giải quyết được bài toán đặt ra.Lựa chọn phương pháp biểu diễn thích hợpNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo85 Để có thể giải quyết vấn đề trên máy tính, trước hết ta phải tìm cách biểu diễn lại vấn đề sao cho máy tính có thể “hiểu” được. Điều này có nghĩa là ta phải đưa các dữ liệu của bài toán về dạng có thể xử lý được trên máy tính.Cách biểu diễn dùng bảng: Sử dụng bảng để biểu diễn các hình trạng của bài toán.Biểu diễn vấn đề trong máy tính123456789101112131415 Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo86Cách biểu diễn dùng xâu ký hiệuBiểu diễn vấn đề trong máy tính         TgT             ToĐ    VĐ      MĐ                      TgT    VTNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo87Cách biểu diễn dùng cấu trúc danh sáchBiểu diễn vấn đề trong máy tính/*2a-b2*4acNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo88Có hai cách tiếp cận trong giải quyết vấn đề: Tổng quát hoá để đưa ra mô hình bài toán Cụ thể hoá trên cơ sở sử dụng các tri thức đặc tả Trên thực tế, có những bài toán không thể giải được nhờ sử dụng mô hình, hơn nữa lời giải nhận được còn khá xa với lời giải thực tế. Trong trường hợp đó, người ta áp dụng cách tiếp cận sử dụng tri thức đặc tả. Các phương pháp biểu diễn tri thức bao gồm: Frame, logic hình thức, mạng ngữ nghĩa và các hệ sản xuất.Biểu diễn tri thức và giải quyết vấn đềNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo89NỘI DUNGBIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNTCÁC PHƯƠNG PHÁP BIỂU DIỄN VẤN ĐỀCÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo90CÁC PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ Biểu diễn vấn đề trong không gian trạng thái và các chiến lược tìm kiếm trên đồ thịQui bài toán về bài toán con và các chiến lược tìm kiếm trên đồ thị Và/HoặcBiểu diễn vấn đề nhờ logic hình thức và phương pháp suy diễn logicMột số phương pháp giải quyết vấn đề khácNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo91Biểu diễn vấn đề trong KGTT và các chiến lược tìm kiếm trên đồ thị Các mô tả trạng thái và toán tửBiểu diễn vấn đề dưới dạng đồ thịCác phương pháp tìm kiếm trong không gian trạng tháiNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo92Các mô tả trạng thái và toán tử Khi giải quyết bài toán trong không gian trạng thái, chúng ta cần phải xác định dạng mô tả các trạng thái của bài toán.VD: Bài toán n2 - 1 số (n = 4)Mỗi trạng thái là bảng có kích thước 4 x 4Toán tử: phép biến đổi từ trạng thái này sang trạng thái khác (chuyển ô trống lên trên, xuống dưới, sang trái, sang phải nếu có thể). Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo93VD: Biến đổi biểu thức đại số:(A x B + C x D)/(B * C) thành A/C + D/B.Mỗi trạng thái là biểu thức đại số.Toán tử: Biến đổi được từ biểu thức này sang biểu thức khác.Dùng cấu trúc cây nhị phân.Dùng ký pháp nghịch đảo Ba lan (Hậu tố, tiền tố). Các toán tử trong không gian trạng thái là những phép biến đổi đưa trạng thái này về trạng thái khácCác mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo94Có hai cách biểu diễn các toán tử:Cách 1: Sử dụng kí hiệu hàm, có nghĩa là xem các toán tử như là các hàm xác định trên tập các trạng thái và nhận giá trị cũng trong tập này VD: Với bài toán trò chơi 15 số, ta có 4 loại toán tử có thể mô tả được dưới dạng kí hiệu hàm như sau dl: Dịch ô trống lên trên; dx: Dịch ô trống xuống dưới; df: Dịch ô trống sang phải; dt: Dịch ô trống sang trái; dl(A) = B, Giả sử A = (aij). B = (bij) và ô trống trong A ở vị trí (i0, j0)). Khi đó ứng với phép dịch ô trống lên trên ta có thể viết B = dl(A) = (bij) với Các mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo95Cách 2: Sử dụng các quy tắc sản xuất (Production Rules) si  sj. Nghĩa là, mỗi khi xuất hiện trạng thái si thì có thể dẫn tới trạng thái sj. VD: Với bài toán trò chơi 15 số, ta có sản xuất sau:Các mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo96Các thủ tục tìm kiếm trong không gian trạng thái thường bao gồm quá trình xây dựng các trạng thái mới xuất phát từ các trạng thái cũ và kiểm tra xem trạng thái mới này có thoả mãn những điều kiện áp dụng cho trạng thái đích không.Các mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo97Kết luận: Để biểu diễn bài toán trong không gian trạng thái cần phải xác định:Dạng mô tả của các trạng thái.Tập các toán tử và tác động của chúng lên các mô tả trạng thái .Các trạng thái đầu, các trạng thái đích .Các mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo98 Một cách hình thức ta có thể phát biểu bài toán như sau:Bài toán P1: Cho trạng thái đầu s0, tập trạng thái ĐICH. Hãy tìm dãy trạng thái s0, s1, s2, . . ., sn sao cho sn  ĐICH, thoả mãn một số điều kiện nào đó và với mọi i (i=0, .. ,n-1), từ trạng thái si có thể áp dụng toán tử biến đổi nào đó để nhận được trạng thái si+1 (i oi  O sao cho oi(si) = si+1hoặc i pi  P sao cho si  si+1 )Các mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo99Hay dưới dạng khác: Bài toán P2: Cho trạng thái đầu s0, tập trạng thái đích ĐICH. - Tìm dãy toán tử o1, . . ., on sao cho on(on-1(. . .(o1(s0). . .)) = sn  ĐICH - Tìm dãy sản xuất p1, p2, . . ., pn sao cho Các mô tả trạng thái và toán tử Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo100Biểu diễn vấn đề dưới dạng đồ thịĐồ thò: là một cấu trúc G = (N,A) bao gồm:Tập các nút NTập các cung A nối các cặp nút, có thể có nhiều cung trên một cặp nútABDCEBCADENút: {A,B,C,D,E}Cung: {(a,d), (a,b), (a,c), (b,c), (c,d), (c,e), (d,e)},e), (d,e) }Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo101Đồ thò có hướng: là đồ thò với các cung có đònh hướng, nghĩa là cặp nút có quan hệ thứ tự trước sau theo từng cung. Cung (Ni,Nj) có hướng từ Ni đến Nj, Khi đó Ni là nút cha và Nj là nút con.Nút lá: là nút không có nút con.Đường đi: là chuoãi có thứ tự các nút mà 2 nút kế tiếp nhau tồn tại một cung.Đồ thò có gốc: Trên đồ thò tồn tại nút X sao cho tất cả các đường đi đều đi qua nút đó. X là gốc.Biểu diễn vấn đề dưới dạng đồ thịNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo102Biểu diễn vấn đề dưới dạng đồ thịKhông gian trạng thái là một hệ thống gồm 4 thành phần [N,A,S,DICH]. Trong đó:N là tập nút của đồ thò. Moãi nút là một trạng thái của quá trình giải quyết vấn đềA: Tập các cung nối giưõa các nút N. Moãi cung là một bước (toán tử) trong giải quyết vấn đề. Cung có thể có hướngS: Tập các trạng thái bắt đầu. S khác roãng.DICH: Tập các trạng thái đích. DICH khác roãng.Lời giải: Là một đường đi đi từ một nút bắt đầu Si đến một nút kết thúc DICHj . Mục tiêu của các giải thuật tìm kiếm là tìm ra một lời giải và/hay lời giải tốt nhất.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo103Các phương pháp tìm kiếm trong KGTTTìm kiếm theo chiều rộng (Breath – first search)Tìm kiếm theo chiều sâu (Depth –first search )Tìm kiếm sâu dần (Depthwise search)Tìm kiếm cực tiểu hoá giá thành (Cost minimization search)Tìm kiếm cực tiểu hoá giá thành với tri thức bổ sung (Heuristic search: Cost minimization search with knowledge)Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo104Các phương pháp tìm kiếm trong KGTT: Breath First Search (TKR) Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N Ra : Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH Phương pháp: /* Sử dụng hai danh sách kiểu FIFO là MO và ĐONG, trong đó MO là danh sách chứa các đỉnh chưa xét còn ĐONG là danh sách chứa các đỉnh đã xét */ {MO  n0 /* Cho đỉnh n0 vào cuối danh sách MO */ While MO   do {n  get(MO) /* Lấy đỉnh n ở đầu danh sách MO */ ĐONG  ĐONG  {n} if B(n)   then /* B(n) là tập các nút con của nút n {MO  MO  B(n) /* Cho B(n) vào cuối danh sách MO */ if B(n)  ĐICH   then {exit(thành công); Xây dựng đường đi p} } } write(không thành công); }Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo105Các phương pháp tìm kiếm trong KGTT: Breath First Search (TKR)VD: Áp dụng thuật toán tìm kiếm theo chiều rộng với cây sau, tập ĐICH = {r, p}Thứ tự duyệt là: a b c d e f g h k l Đường đi: a c f l pNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo106Các phương pháp tìm kiếm trong KGTT: Breath First Search (TKR)Nếu trong cây G tồn tại ít nhất một đường đi từ n0 tới tập ĐICH thì thủ tục tìm kiếm theo chiều rộng dừng và cho ta đường đi p có độ dài ngắn nhất (thậm chí cây G vô hạn). Nếu không tồn tại đường đi như vậy thuật toán dừng nếu và chỉ nếu đồ thị cây G là hữu hạn. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo107Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS) Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N Ra : Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH Phương pháp: /* Sử dụng danh sách MO kiểu LIFO và danh sách ĐONG kiểu FIFO */ {MO  n0 /* Cho đỉnh n0 vào đầu danh sách MO */ While MO   do {n  get(MO) /* Lấy đỉnh n ở đầu danh sách MO */ ĐONG  ĐONG  {n} if B(n)   then {MO  MO  B(n) /* Cho B(n) vào đầu danh sách MO */ if B(n)  ĐICH   then {exit(thành công); Xây dựng đường đi p} } } write(không thành công); }Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo108Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)VD: Áp dụng thuật toán tìm kiếm theo chiều sâu với cây sau, tập ĐICH = {o, p} Thứ tự duyệt: a b d h Đường đi: a b d h o Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo109Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)Nếu cây G hữu hạn thì thủ tục tìm kiếm theo chiều sâu sẽ dừng và cho kết quả là một đường đi từ n0 đến tập ĐICHĐường đi nhận được theo thuật toán TKR (nếu có) sẽ là đường đi ngắn nhất còn đường đi nhận được theo thuật toán TKS (nếu có) có thể không phải là đường đi ngắn nhất. Hơn nữa, nếu đồ thị vô hạn thì thủ tục TKS có thể lặp vô hạn, thậm chí trong đồ thị G tồn tại đường đi từ n0 tới tập ĐICH.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo110Các phương pháp tìm kiếm trong KGTT: Depth First Search (TKS)Khắc phục bằng cách giới hạn độ sâu của giải thuật.Chiến lược giới hạn: Cố đònh một độ sâu DTheo cấu hình tài nguyên của máy tínhTri thức trong việc đònh giới hạn độ sâu.Giới hạn độ sâu => co hẹp không gian trạng thái => có thể mất nghiệm.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo111Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)Tìm kiếm theo chiều sâu đối với lớp các đỉnh tuỳ thuộc vào mức sâu k đã cho ban đầu. Cách thực hiện: Ta ký hiệu độ sâu hiện tại là DS, ban đầu gán DS = k, duyệt các đỉnh trong phạm vi độ sâu  DS, nếu chưa tìm được đường đi thì tăng DS = DS + k và tiếp tục duyệt.Độ sâu d(n) của đỉnh n được định nghĩa:d(n0) = 0d(n) = d(m) +1 nếu nB(m)Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo112Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N, mức sâu kRa: Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICHPhương pháp: /* Sử dụng ds MO kiểu lai LIFO và FIFO, ds DONG kiểu FIFO */ {MO  n0; DS = k; While MO   do {n  get(MO) /* Lấy đỉnh n ở đầu danh sách MO */ DONG  ĐONG  {n} if B(n)   then {if B(n)  ĐICH   then {exit(thành công); Xây dựng đường đi p} case d(n) do { [0..DS - 1]: đặt B(n) vào đầu MO DS: đặt B(n) vào cuối MO DS + 1: {DS = DS + k; if k =1 then đặt B(n) vào cuối MO else đặt B(n) vào đầu MO }}} write(không thành công); }Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo113Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)VD: Áp dụng thuật toán TKSD với cây sau:Tập ĐICH = {r, p}, độ sâu k = 2.Thứ tự duyệt: a b d e c f g h n o k lĐường đi: a c f l p Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo114Các phương pháp tìm kiếm trong KGTT: Depthwise search (TKSD)Khi k =1 thủ tục TKSD trở thành thủ tục TKRKhi k>=2 thủ tục TKSD tìm theo chiều sâu đối với các đỉnh có độ sâu nằm trong khoảng từ tk + 1 đến (t + 1)k với t bắt đầu từ 0 và mỗi lần tăng lên 1Nếu trong cây G tồn tại ít nhất một đường đi từ đỉnh n0 đến ĐICH thì thủ tục TKSD sẽ dừng và cho kết quả là đường đi có độ dài khác đường đi ngắn nhất không quá k - 1. Nếu không tồn tại đường đi như vậy thì thủ tục TKSD dừng khi và chỉ khi G hữu hạnNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo115Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)Giả sử C: AR+ là hàm giá (cost) tương ứng mỗi cung a  A với giá chi phí c(a)R+. Với một đường đi p trong G, p = n1, ..., nk ta có: Xác định p: n0nk  DICH sao cho: c(p)  min Kí hiệu g(n) là giá của đường đi cực tiểu từ n0 đến n. Khi đó, bài toán trên được phát biểu thành: Tìm đường đi p0 từ đỉnh gốc n0 đến đỉnh nk  DICH sao cho g(nk)=min{g(n)| n  DICH}. Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo116Vào: Cây G = (N, A), đỉnh gốc n0, tập ĐICH  N, c: A  R+Ra: Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH sao cho c(p) minPhương pháp: /* Sử dụng 2 danh sách MO và DONG */ {MO  n0; g0(n0)=0; /*g0(n): giá của đường đi hiện tại từ n0 đến n*/ While MO   do {n  get(MO) /* Lấy đỉnh n  MO sao cho g0(n) min */ ĐONG  ĐONG  {n} if n  ĐICH then exit(thành công) if B(n)   then {MO  B(n)  MO for each m  B(n) do g0(m) = g0(n) + c(n, m)} } write(không thành công); } Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo117VD: Áp dụng thuật toán TKCT đối với cây sau Tập ĐICH = {n, p} Thứ tự duyệt: a c b f l m d g h p Đường đi: a c f l p Có giá: 10Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo118Thủ tục TKR là trường hợp riêng của thuật toán TKCT khi c(a) =1 a  A. Thủ tục TKS cũng là trường hợp riêng của thủ tục TKCT khi lấy tiêu chuẩn chọn n  MO là d(n) max thay cho điều kiện g0(n) minNếu trong cây G tồn tại đường đi p từ n0 đến ĐICH thì thủ tục TKCT sẽ dừng và cho kết quả là đường đi p sao cho c(p) min. Hơn nữa, thủ tục TKCT tối ưu theo nghĩa số đỉnh cho vào tập ĐONG là nhỏ nhất so với các thủ tục tìm kiếm chỉ dựa vào giá các cung. Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo119Các Heuristic áp dụng cho thủ tục TKCT : Chỉ xét các đỉnh trong B(n) có triển vọng đạt tới tập ĐICH. Sắp xếp các đỉnh trong MO trước mỗi lần xử lý nhờ các hàm đánh giá.Các phương pháp tìm kiếm trong KGTT: Cost minimization search (TKCT)Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo120“Heuristics là các quy tắc, phương pháp, chiến lược, mẹo giải hay phương cách nào đó nhằm làm giảm khối lượng tìm kiếm lời giải trong không gian bài toán cực lớn.”Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện cách giải bài toán với các đặc tính sau:Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất)Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động của con người.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo121Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó người ta thường dựa vào một số nguyên lý cơ bản như sau:Nguyên lý vét cạn thông minh: Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.Nguyên lý tham lam (Greedy): Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn) trong quá trình tìm kiếm lời giải.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo122Nguyên lý thứ tự: Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát nhằm nhanh chóng đạt được một lời giải tốt.Hàm Heuristic: Trong việc xây dựng các thuật giải Heuristic, người ta thường dùng các hàm Heuristic. Đó là các hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng thái hiện tại của bài toán tại mỗi bước giải. Nhờ giá trị này, ta có thể chọn được cách hành động tương đối hợp lý trong từng bước của thuật giải.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo123Thủ tục TKCT là thuật giải tìm kiếm đường đi tối ưu khi chỉ xét tới các thông tin về các đỉnh, các cung và giá thành của chúng.Trong nhiều trường hợp việc tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các tri thức thu được dựa trên các hiểu biết về tình huống vấn đề ở mỗi bước. Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo124Các Heuristic trong việc tìm kiếm cực tiểu hoá giá thành:Chọn toán tử xây dựng cung B sao cho có thể loại bớt những đỉnh không liên quan đến bài toán hoặc ít có triển vọng nằm trên đường đi tối ưu.Sử dụng thông tin bổ sung nhằm xây dựng tập MO và cách lấy các đỉnh trong tập MO. Muốn vậy, ta phải đưa ra độ đo, tiêu chuẩn nào đó để tìm ra các đỉnh có triển vọng, thường gọi là các hàm đánh giá. Một số phương pháp xây dựng hàm đánh giá: - Dựa vào xác suất của đỉnh trên đường đi tối ưu. - Dựa vào khoảng cách, sự sai khác giữa một đỉnh nào đó với tập các đỉnh đích.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo125Vào: Đồ thị G=(N,A) tuỳ ý, đỉnh gốc n0. tập đỉnh đích ĐICH. Hàm f0: NR+. /*f0 là hàm ước lượng heuristic nào đó*/Ra: Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH Phương pháp: { MO{n0}; Tính f0(n0) ; While MO   do {n  get(MO); /* Lấy n  MO sao cho f0 (n)  min */ ĐONG  ĐONG  {n}; if n ĐICH then exit(“ thành công”); if B(n)   then for each m  B(n) do if m ĐONG  MO then { MO MO  {m}; Tính f0(m)} else if f0cũ(m) >fmới(m) then MO MO  {m}}; Write(“ không thành công”) }Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo126f0=g0+h0 , trong đó: h0(n) là tri thức bổ sung chỉ ra triển vọng của đỉnh n nằm trên đường tối ưu.f0(n) là ước lượng của hàm: f(n)=g(n)+h(n) , trong đó: g(n) là giá đường đi tối ưu từ n0 tới n h(n) là giá đường đi tối ưu từ n tới tập ĐICHf0(n) là xấp xỉ của giá đường đi tối ưu từ n0 tới tập ĐICH và đi qua đỉnh n. Thủ tục TKCT là trường hợp riêng của thủ tục TKCT* khi lấy h0=0Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo127Kết quả 1: (Tính đúng đắn)Nếu đối với mỗi đỉnh nN ta có 0  h0(n)  h(n) và tồn tại >0 sao cho aA c(a) thì thủ tục TKCT* dừng và cho đường đi p: n0n*ĐICH sao cho g(n*) min. Kết quả 2: (Tính tối ưu)Giả sử thủ tục TKCT*i sử dụng hàm đánh giá f0i(n)=g0(n)+h0i(n), i=1,2 và giả sử h2 thoả mãn điều kiện h02(m) – h02(n)  h(m, n), (h(m,n) là độ dài đường đi ngắn nhất từ m đến n) và n 0  h01(n)  h02(n)  h(n) thì số nút đưa vào tập DONG của thuật toán TKCT2* bao giờ cũng nhỏ hơn số nút đối với thuật toán TKCT1*.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo128VD: Xét bài toán tháp Hà Nội với n=2, lấy hàm f0=g0+h0, trong đó h0(n) là thông tin nói thêm về mối liên hệ giữa n và trạng thái đích. Chẳng hạn: h0=2 nếu ở cọc C chưa có đĩa nào, h0=1 nếu ở cọc C có đĩa to, h0=3 nếu ở cọc C có đĩa nhỏ, h0=0 nếu ở cọc C đã có hai đĩa.Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT*Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo129Các phương pháp tìm kiếm trong KGTT: Heuristic search: TKCT* g0 =0 g0 =1 g0 =2 g0 =3 h0 = 2, f0=2 h0 = 3, f0=4 h0 = 2, f0=3 h0 = 1 f0=3 h0 = 3 f0=5 h0 = 2 f0=4 h0 = 2 f0=5 h0 = 0 f0=3 h0 = 1 f0=4 ĐICH Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo130Qui bài toán về các bài toán con và các chiến lược tìm kiếm trên đồ thị Và/HoặcQui bài toán về các bài toán conThể hiện dưới dạng đồ thị VÀ/HOẶCCác phương pháp tìm kiếm trong đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo131Qui bài toán về các bài toán conÝ tưởng cơ bản là xuất phát từ bài toán đặt ra, tách bài toán này thành các bài toán con cho đến khi bài toán ban đầu trở thành các bài toán sơ cấp. Bài toán sơ cấp được hiểu là bài toán mà lời giải của chúng có thể nhận được ngay.VD: Với bài toán n2 – 1 số, bài toán sơ cấp chính là bài toán chuyển ô trống 1 lần để nhận được trạng đích. Với bài toán tháp Hà Nội, bài toán sơ cấp là chuyển 1 đĩa từ cọc này sang cọc khác.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo132Thể hiện dưới dạng đồ thị VÀ/HOẶCĐồ thị (định hướng) VÀ/HOẶC là cặp G = (N,A), sao cho n  N, tất cả các đỉnh m B(n) cùng thuộc vào một trong hai kiểu: đỉnh VÀ, đỉnh HOẶC. Khi các đỉnh con m của n là đỉnh VÀ thì cung (n,m) (m B(n)) được nối bởi ngoặc lớn. VD:Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo133Thể hiện dưới dạng đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo134Đỉnh giải được:Các đỉnh kết thúc (cuối) là đỉnh giải được.Nếu đỉnh n có các đỉnh con là đỉnh VÀ thì nó là đỉnh giải được khi và chỉ khi tất cả các đỉnh con của nó giải được.Nếu đỉnh n có các đỉnh con là đỉnh HOẶC thì nó là đỉnh giải được khi và chỉ khi tồn tại 1 đỉnh con của nó giải được. Đỉnh không giải được:Nếu đỉnh n không là đỉnh kết thúc và không có các đỉnh con thì nó là đỉnh không giải được.Nếu đỉnh n không là đỉnh kết thúc và có các đỉnh con là đỉnh VÀ thì nó là đỉnh không giải được khi và chỉ khi tồn tại một đỉnh con không giải được.Nếu đỉnh n không là đỉnh kết thúc mà có các đỉnh con là đỉnh HOẶC thì nó là đỉnh không giải được khi và chỉ khi tất cả các đỉnh con là không giải được Thể hiện dưới dạng đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo135Đồ thị lời giải: Là đồ thị con của đồ thị VÀ/HOẶC chỉ chứa các đỉnh giải được và đỉnh đầu.Nhận xét: Nếu trên đồ thị VÀ/HOẶC không có đỉnh VÀ nào thì đồ thị VÀ/HOẶC trở thành đồ thị thông thường và khi đó đồ thị con lời giải sẽ suy biến thành đường đi từ đỉnh đầu tới một đỉnh kết thúc nào đó.Mục đích của quá trình tìm kiếm trên đồ thị VÀ/HOẶC là ta phải xác định xem đỉnh đầu có giải được hay không. Trong trường hợp giải được thì ta phải đưa ra cây lời giải thoả mãn điều kiện nào đó.Thể hiện dưới dạng đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo136Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo137Thủ tục gđ(nN) { if nhan(n)= “kxđ” then if kt(n) then nhan(n)="gđ" else if n MO ĐONG then nhan(n)=”kxđ” else if kieu(n) then {bien=True; While B(n)  and bien do {m  get(B(n)); gđ(m); bien=(nhan(m)=”gđ”)} if bien then nhan(n)=”gđ” else nhan(n)=”kxđ”} else {bien=false; repeat {m get(B(n)); gđ(m); bien=(nhan(m)=”gđ”)} until bien or B(n)= if bien then nhan(n)=”gđ” else nhan(n)=”kxđ”}}Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo138Thủ tục tìm kiếm theo chiều rộng TKRMThủ tục tìm kiếm theo chiều sâu TKSMCác phương pháp tìm kiếm trong đồ thị VÀ/HOẶCNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo139Vào: Cây VÀ/HOẶC G=(N, A) với đỉnh đầu n0, tập đỉnh kết thúc T={ti} NRa: Thông báo “không thành công” nếu n0 kgđ, “thành công” nếu n0 gđ và đưa ra cây lời giải.Phương pháp: /* sử dụng hai danh sách FIFO: MO, ĐONG */{MO ={n0}; While MO   do {n get(MO); /*Lấy đỉnh n đầu danh sách MO*/ ĐONG{n}  ĐONG; bool = false; if B(n)  and bool = false then {MO MO B(n); /* đưa B(n) vào cuối danh sách MO */ For each m B(n) do {if kt(m) then {nhan=”gđ”; bool=true}} if bool then {gđ(n0); if nhan(n0)=”gđ” then exit(“thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh giải được}} else {nhan(n)=”kgđ”; kgđ(n0); if nhan(n0) = “kgđ” then exit (“không thành công”) else loại khỏi MO các đỉnh có tổ tiên là đỉnh không giải được;}}} Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKRMNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo140VD:Áp dụng thuật toán TKRM đối với cây sau Tập T = {t1,t2,t3,t4}Thứ tự duyệt:abcdefgijkCây lời giải:các cung tô đậmNhận xét: Nếu cây lời giải tồn tại thì thủ tục TKRM sẽ dừng và cho kết quả là cây lời giải có độ cao nhỏ nhấtCác phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKRMabcde fgij kAt1t2BCt3t4DEFNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo141Các phương pháp tìm kiếm trong đồ thị VÀ/HOẶC: Thủ tục TKSMVào: Cây VÀ/HOẶC G=(N, A) với đỉnh đầu n0, tập đỉnh kết thúc T={ti} N. Giới hạn sâu D.Ra: Thông báo “không thành công” nếu n0 kgđ, “thành công” nếu n0 gđ và đưa ra cây lời giải.Phương pháp: /* sử dụng hai danh sách FIFO: DONG, LIFO: MO */{MO ={n0}; While MO   do {n get(MO); /*Lấy đỉnh n đầu danh sách MO*/ ĐONG{n}  ĐONG; bool = false; if d(n) = : . & _ ~Dựa trên quy tắcChuỗi các chữ cái, chữ số, dấu _ ,bắt đầu bằng một chữ thường (VD : anna, x25, x__y, alpha_beta,...)Chuỗi các ký tự đặc biệt (VD : , === > , ...)Chuỗi các ký tự nằm trong cặp dấu ‘ ’ (VD : ‘Hoàng’, ‘Hoa’,...)ĐỐI TƯỢNG DỮ LIỆU – Nguyên tốNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo187Gồm số nguyên và số thựcVí dụ :Số nguyên : -3, -100, 1, 5 ,2, ...Số thực : 1.25, -3.25, ...Số thực ít được sử dụng trong lập trình PrologĐỐI TƯỢNG DỮ LIỆU - SốNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo188BiếnChuỗi các chữ cái, chữ số và dấu _, bắt đầu bằng một chữ viết HOA hoặc dấu _.Ví dụ : X, Result, Object2, _23Biến vô danhKý hiệu : _Nếu biến chỉ xuất hiện một lần, không cần đặt tên. Sử dụng biến vô danhVí dụ : haschild(X) :- parent(X,Y). %Biến Y chỉ xuất hiện một lầnhaschild(X) :- parent(X,_). %Thay thế bằng biến vô danhĐỐI TƯỢNG DỮ LIỆU - BiếnNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo189ĐỐI TƯỢNG DỮ LIỆU – Cấu trúcCác đối tượng có nhiều thành phần.Ví dụ :Đối tượng date có thể xem là một cấu trúc với các thành phần : day, month, year.Thể hiện bằng Prolog: Ví dụ :date(1,may, 2005)date1may2005Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo190Term (hạng)Tất cả các đối tượng dữ liệu trong Prolog được gọi là term.Ví dụ : thangnam, ngay(1, thangchin,2005) là các term.So khớp (matching)Là thao tác quan trọng nhất trên các term.Là quá trình kiểm tra xem hai term có khớp nhau hay không.ĐỐI TƯỢNG DỮ LIỆU – Cấu trúcNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo191Hai term được xem là khớp (match) nhau nếu:Giống nhau hoàn toànCác biến trong cả hai term được khởi tạo thành các đối tượng sao cho sau khi thay thế chúng bằng các đối tượng này thì chúng giống nhau hoàn toàn.Ví dụCho hai term date(D,M, 2005) và date(D1, thangchin, Y1) được coi là khớp nhauTa có : D khởi tạo thành D1, M khởi tạo thành thangchin, còn Y1 khởi tạo thành 2005.ĐỐI TƯỢNG DỮ LIỆU – Cấu trúcNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo192Xác định hai term có khớp nhau hay không?Nếu S, T là hằng số thì chúng khớp nhau khi chúng cùng một đối tượng.Nếu S là biến và T bất kỳ. Nếu chúng khớp nhau thì S được khởi tạo thành T và ngược lại.Nếu S và T là cấu trúc. Chúng khớp nhau khi tất cả các thành phần trong S và T khớp nhau.ĐỐI TƯỢNG DỮ LIỆU – Cấu trúcNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo193KIỂU DỮ LIỆU & PHÉP TOÁNKIỂU DỮ LIỆUchar : ký tự ở giữa cặp dấu ‘’.Ví dụ : ‘a’, ‘b’, ‘1’, ...integer : số nguyên (từ -32768 đến 32767)Ví dụ : 200, -521, 322, ...real : số thựcVí dụ : 25.18, -78.3e+21, 25.5e-20, ...string : chuỗi dài tối đa 64KB, nằm cặp dấu “”.Ví dụ : “chào các bạn”, “Prolog”symbol : chuỗi dài tối đa 80 ký tự, có thể không có dấu “”.Ví dụ : prolog, “Prolog”, chao_cac_ban,...Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo194KIỂU DỮ LIỆU & PHÉP TOÁNPHÉP TOÁN TRONG SWI-PROLOGPhép toán số học : +, -, *, /, mod, //, **Biểu thức số học: được xây dựng nhờ vị từ isNumber is Expr Number: đối tượng cơ bản Expr: biểu thức số học được xây dựng từ các phép toán số học, các số và các biến.Phép so sánh số học : >, =, 0Sử dụng thuật toán EuclideUSCLN của X và X là X.USCLN của X và Y là USCLN của X – Y và Y nếu X>Y.USCLN của X và Y là USCLN của Y-X và X nếu X xác định mục tiêu cần giải P(2) Biểu diễn bài toán dưới dạng chuẩn=> P i(jqij).(3) Chuyển sang mệnh đề Horn (luật, sự kiện)(4) Chuyển sang PrologNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo198(1) uscln(X,Y,Z)  Z là USCLN của X,Y.(2) uscln(X,Y,Z)  [(X>Y)  (T=X-Y)  uscln(T,Y,Z)] [(XY)  (T=X-Y)  uscln(T,Y,Z). uscln(X,Y,Z)  (XY, T is X-Y, uscln(T,Y,Z).uscln (X,Y,Z):-XY, is(T, X-Y), uscln(T,Y,Z).uscln (X,Y,Z):-X truePlist = [P1|Plist1] => true nếu P không tấn công P1 và P không tấn công các vị trí trong Plist1Bài toán 8 HậuNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo215Kiểm tra một vị trí đặt hậu pos(X,Y) thật sự không tấn công những con Hậu khácnoattack(_, []).noattack(pos(X,Y), [pos(X1,Y1) | Others]) :- Y =\= Y1, Y1-Y =\= X1-X, Y1-Y=\=X-X1, noattack(pos(X,Y),Others).Chương trình?Bài toán 8 HậuNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo216Điều khiển quay lui và lát cắtProlog tự động quay lui để thoả mãn mục tiêu.Đây là một công việc hữu ích nhưng có những lúc lại không hiệu quả.Cần có những cách điều khiển (ngăn) quay lui.Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo217Mối quan hệ giữa X và Y được xác lập qua 3 luật:Luật 1: Nếu X 2.Kết quả của câu hỏi trên?Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo220f(1,Y) sẽ cho kết quả Y=0.Khi đó, Y>2 trở thành 0>2 (=> false).Vì vậy, goal cho kết quả là : No.Prolog phải duyệt qua cả 3 mệnh đề của vị từ f.Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo221Lát cắt:Ký hiệu: !Dùng để ngăn Prolog quay lui trong trường hợp đã tìm ra lời giải hoặc sẽ không tìm ra lời giải thêm nếu tiếp tục.Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo222Thêm lát cắt :f(X,0) :- X2.Prolog sẽ cho kết quả ra sao? Thực thi như thế nào?Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo223Prolog sẽ cho ra cùng kết quả: No.Không có sử dụng đến mệnh đề (luật) 2 và 3. =>đỡ tốn kém thời gian thực hiện.=> tăng hiệu quả cho chương trình.Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo224Với đoạn chương trình:f(X,0) :- XB,!. max(A,B,B).Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo232Thuận lợi:Lát cắt làm tăng hiệu quả chương trình (tiết kiệm không gian, thời gian,)Loại bỏ được những chọn lựa chắc chắn sai.Có thể thực hiện các luật có dạng:if ĐK1 then KL1else KL2Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo233Khó khăn:Trật tự các mệnh đề trong vị từ có thể ảnh hưởng đến kết quả (khi sử dụng lát cắt)Ví dụ:Vớip :- a,b.p :- c.p (a  b)  cĐiều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo234Ví dụ:Trong khi vớip :- a, !, b.p :- c.p (a  b)  ( a  c)Cònp :- c.p :- a, !, b.p c  (a  b) Điều khiển quay lui và lát cắtNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo235ÔN TẬPNguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo236Xin chân thành cảm ơn!