Bài giảng Trí Tuệ Nhân Tạo

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
1
TRÍ TUỆ NHÂN TẠO
Nguyễn Ngọc Hiếu
Khoa Công nghệ Thông tin
Trường Đại học Vinh
Email: [email protected]
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
2
NỘI DUNG
TỔNG QUAN VỀ KHOA HỌC TTNT
CÁC PHƯƠNG PHÁP BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ
NGÔN NGỮ TTNT PROLOG
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
3
TÀI LIỆU THAM KHẢO
1. 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 Norvig

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
4
ĐÁ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ạo
5
KHỐI LƯỢNG & CẤU TRÚC HỌC PHẦN
Số đơn vị học trình: 3
Lý thuyết: 35 tiết
Thực hành, bài tập: 10 tiết
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
6
TỔNG QUAN VỀ KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
7
NỘI DUNG
CÁC KHÁI NIỆM CƠ BẢN
CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT
LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT
CÁC THÀNH TỰU CỦA KHOA HỌC TTNT
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
8
CÁ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ạo
9
Intelligence: 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ạo
10



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ạo
11



CÁC KHÁI NIỆM CƠ BẢN:
TTNT và lập trình truyền thống
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
12
CÁC KHÁI NIỆM CƠ BẢN:
Các yêu cầu của TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
13
CÁC KHÁI NIỆM CƠ BẢN:
Hành động như con người:Phép thử Turing
Alan Turing (1912-1954)
“Computing Machinery and Intelligence” (1950)
Phép thử
Người kiểm tra
Người
Hệ thống TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
14
Chỉ 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ếp
Biể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ấn
Suy 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ới
Họ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ười
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
15
CÁ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 đúng
Cò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ạo
16
CÁ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ạo
17
CÁ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ắn
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
18
CÁC KHÁI NIỆM CƠ BẢN:
Các phương pháp và kỹ thuật
Các phương pháp biểu diễn tri thức và kỹ thuật xử lý tri thức
Các phương pháp giải quyết vấn đề
Các phương pháp Heuristic
Các phương pháp học
Các ngôn ngữ TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
19
CÁC KHÁI NIỆM CƠ BẢN:
Các thành phần trong hệ thống
Hai 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ức
Cá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ễn
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
20
NỘI DUNG
CÁC KHÁI NIỆM CƠ BẢN
CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT
LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT
CÁC THÀNH TỰU CỦA KHOA HỌC TTNT
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
21
CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT
TTNT 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ác

TTNT
Tâm lý học
Ngôn ngữ học
Khoa học
máy tính
Triết học
Toán học
Các lý thuyết của lập luận và học
Các lý thuyết xác suất logic, tạo quyết định và tính toán
Làm cho TTNT trở thành hiện thực
Nghiên cứu ý nghĩa và cấu trúc của ngôn ngữ
Nghiên cứu tâm trí con người
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
22
NỘI DUNG
CÁC KHÁI NIỆM CƠ BẢN
CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT
LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT
CÁC THÀNH TỰU CỦA KHOA HỌC TTNT
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
23
LỊCH SỬ PHÁT TRIỂN CỦA
KHOA HỌC TTNT

Bắ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ạo
24
“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 McCarthy
Marvin Minsky
LỊCH SỬ PHÁT TRIỂN CỦA
KHOA HỌC TTNT

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
25
Trô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 Theorist
Gelernter’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 TTNT

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
26
Thự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 TTNT

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
27
TTNT 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 TTNT

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
28
LỊCH SỬ PHÁT TRIỂN CỦA
KHOA HỌC TTNT

Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
29
NỘI DUNG
CÁC KHÁI NIỆM CƠ BẢN
CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT
LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT
CÁC THÀNH TỰU CỦA KHOA HỌC TTNT
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
30
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
31
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
32
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
33
SONY AIBO
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
34
Đi bộ
Quay
Lên xuống cầu thang
Honda Humanoid Robot
& Asimo
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
35
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
36
CÁC THÀNH TỰU CỦA
KHOA HỌC TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
37
NỘI DUNG
CÁC KHÁI NIỆM CƠ BẢN
CÁC TIỀN ĐỀ CƠ BẢN CỦA TTNT
LỊCH SỬ PHÁT TRIỂN CỦA KHOA HỌC TTNT
CÁC THÀNH TỰU CỦA KHOA HỌC TTNT
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
38
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
39
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
40
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
41
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
42
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
43
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
44
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
45
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
46
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
47
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
48
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
49
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
50
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
51
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
52
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
53
CÁC XU HƯỚNG MỚI TRONG TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
54
Một số chủ đề nghiên cứu
Giải thuật di truyền và ứng dụng
Mạng Nơron nhân tạo và ứng dụng
Công nghệ tác tử và ứng dụng
KDD và ứng dụng
Phân lớp - học có thầy
Lý thuyết tập thô
Cây quyết định
.....
Phân cụm - học không có thầy
Luật kết hợp
....
. . .
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
55
CÁ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ạo
56
NỘI DUNG
BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT
CÁ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ạo
57
BIỂ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 TTNT
Giải quyết vấn đề của con người
Phâ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ạo
58
Giải quyết vấn đề và khoa học TTNT
Hoạ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ải
VD: Biểu diễn bằng mạng ngữ nghĩa => Các thủ tục tìm kiếm
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
59
Giả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 Heuristic
Phâ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 minh
Cá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 gia
Các hệ chuyên gia


Giải quyết vấn đề và khoa học TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
60
Phát biểu bài toán-Xác định phương pháp bd bài toán
Sản sinh không gian bài toán
Bài toán có thể giải nhờ thuật toán đa thức

Xác định lời giải nhờ các ngôn ngữ lập trình
Xác định các tri thức đặc biệt để rút gọn không gian TK
Xây dựng các phương pháp biểu diễn tri thức và suy diễn
Lựa chọn ngôn ngữ, công cụ phù hợp
Các hệ giải quyết vấn đề dựa vào tri thức
Bài toán (Vấn đề)
Đ
S

Công nghệ lập trình truyền thống

Cô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 TTNT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
61
Giả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ạo
62
Quá trình xử lý thông tin của con người
Giải quyết vấn đề của con người
Hệ thống thụ cảm
Cơ quan thụ cảm
Bộ nhớ đệm
Hệ thống nhận thức
Bộ nhớ dài hạn
Bộ nhớ làm việc
Bộ xử lý nhận thức
Hệ thống hành động
Cơ quan hành động
Bộ nhớ đệm
Kích


thích
Trả


lời
hệ thống xử lý thông tin của con người
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
63
Giả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ười
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
64
Cá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ười
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
65
Cá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ười
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
66
Khô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ười
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
67
Phâ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).
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
68
Bài toán 2: Bài toán Tháp Hà nội
Phân loại vấn đề & Các đặc trưng cơ bản của vấn đề

3
2
1
3
2
1
A
B
C
A
B
C
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
69
Phâ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ạo
70
Cá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ạo
71
Cá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án
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ạo
72
NỘI DUNG
BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT
CÁ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ạo
73
CÁ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ái
Phương pháp qui bài toán về các bài toán con
Phương pháp biểu diễn vấn đề nhờ logic hình thức

Lựa chọn phương pháp biểu diễn thích hợp
Biểu diễn vấn đề trong máy tính
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ạo
74
Phương pháp biểu diễn nhờ KGTT
Trạ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ạo
75
Mộ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ũ choi n2-1 s? (n?N, n>2)
n = 4
Phương pháp biểu diễn nhờ KGTT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
76
Phương pháp biểu diễn nhờ KGTT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
77
Mỗ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ối
Khô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ờ KGTT
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
78
Phương pháp qui bài toán về các bài toán con
Tá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.
 
 
 
 
 
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
79
Phương pháp qui bài toán về các bài toán con
VD: Bài toán Tháp Hà nội (n=3)
3
2
1
3
2
1
A
B
C
A
B
C
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
80
n = 3




n = 4
Phương pháp qui bài toán về các bài toán con
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
81
Thô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ức
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
82
Cá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ái
Kiể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ải
Mụ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ức
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
83
Trong 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ợp
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
84
Việ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án
Tậ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ại
Cá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ải
Sau 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ợp
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
85
Để 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ính
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
86
Cách biểu diễn dùng xâu ký hiệu
Biểu diễn vấn đề trong máy tính
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
87
Cách biểu diễn dùng cấu trúc danh sách
Biểu diễn vấn đề trong máy tính
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
88
Có 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ạo
89
NỘI DUNG
BIỂU DIỄN VÀ GIẢI QUYẾT VẤN ĐỀ TRONG KHOA HỌC TTNT
CÁ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ạo
90
CÁ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ặc
Biểu diễn vấn đề nhờ logic hình thức và phương pháp suy diễn logic
Một số phương pháp giải quyết vấn đề khác
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
91
Biể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ái
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
92
Cá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 4
Toá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ạo
93
VD: 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ác
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ạo
94
Có 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ạo
95
Cá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ạo
96
Cá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ạo
97
Kế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ạo
98
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+1
hoặ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ạo
99
Hay 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ạo
100
Biể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 N
Tậ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út
A
B
D
C
E
B
C
A
D
E
Nú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ạo
101
Đồ 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ạo
102
Biể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ướng
S: 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ạo
103
Các phương pháp tìm kiếm trong KGTT
Tì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ạo
104
Cá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ạo
105
Cá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 p
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
106
Cá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ạo
107
Cá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ạo
108
Cá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ạo
109
Cá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ạo
110
Cá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 D
Theo cấu hình tài nguyên của máy tính
Tri 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ạo
111
Cá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) = 0
d(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ạo
112
Cá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 k
Ra: Đường đi p từ đỉnh n0 tới đỉnh n*  ĐICH
Phươ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ạo
113
Cá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ạo
114
Cá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 TKR
Khi 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 1
Nế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ạn
Nguyễn Ngọc Hiếu - Các Bài giảng Trí tuệ Nhân tạo
115
Cá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ạo
116
Và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) min
Phươ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ạo
117
VD: Á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á: 10
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ạo
118
Thủ 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) min
Nếu trong cây G tồn tại đường đi p từ n0 đến ĐICH thì thủ t