Chương 3
Không gian trạng thái và
Các phương pháp tìm kiếm mù
Biên soạn: TS Ngô Hữu Phúc
Bộ môn Khoa học máy tính
ĐT: 098 56 96 580
eMail: ngohuuphuc76@gmail.com
Chương 3: Không gian trạng thái và Tìm kiếm mù
Trí tuệ nhân tạo
1
Thông tin chung
Thông tin về nhóm môn học:
Thời gian, địa điểm làm việc: Bộ môn Khoa học máy tính Tầng 2, nhà A1.
Địa chỉ liên hệ: Bộ môn Khoa học máy tính, khoa Công nghệ thông tin.
Điện thoại, email: 069-515-329, ngohuuphuc76.mta@gmail.com.
TTNT - Học viện Kỹ thuật Quân sự
2
TT
Họ tên giáo viên
Học hàm
Học vị Đơn vị công tác (Bộ môn)
1
Ngô
Hữu Phúc GVC TS BM Khoa học máy tính
2
Trần
Nguyên
Ngọc
GVC TS BM Khoa học máy tính
3
Hà
Chí Trung GVC TS BM Khoa học máy tính
4
Trần
Cao Trưởng GV ThS BM Khoa học máy tính
Cấu trúc môn học
Chương 1: Giới thiệu chung.
Chương 2: Logic hình thức.
Chương 3: Các phương pháp tìm kiếm mù.
Chương 4: Các phương pháp tìm kiếm có sử dụng thông tin.
Chương 5: Các chiến lược tìm kiếm có đối thủ.
Chương 6: Các bài toán thỏa rằng buộc.
Chương 7: Nhập môn học máy.
TTNT - Học viện Kỹ thuật Quân sự
3
Bài 3: Tìm kiếm mù
TTNT - Học viện Kỹ thuật Quân sự
Chương 3, mục: 3.1 –3.6
Tiết: 1-3; Tuần thứ: 4.
Mục đích, yêu cầu:
1. Nắm được phương pháp giải quyết vấn đề.
2. Nắm được các khái niệm về không gian trạng thái.
3. Nắm được các phương pháp tìm kiếm yếu; qua đó nắm được
ưu, nhược điểm của các phương pháp trên.
Hình thức tổ chức dạy học:Lý thuyết.
Thời gian: 3 tiết.
Địa điểm:Giảng đường do Phòng Đào tạo phân công
Nội dung chính: (Slides)
4
Nội dung bài học
Chương 3: Không gian trạng thái và Tìm kiếm mù
5
1. Khái niệm về “Giải quyết một số vấn đề”.
2. Không gian trạng thái.
3. Phân loại vấn đề.
4. Các chiến lược tìm kiếm trên không gian trạng thái:
Tìm kiếm hướng từ dữ liệu (data –driven)
Tìm kiếm hướng từ mục tiêu (goal –driven).
5. Tìm kiếm trên không gian trạng thái:
Tìm kiếm rộng (breath –first search).
Tìm kiếm sâu (depth –first search).
Tìm kiếm sâu bằng cách đào sâu nhiều lần (depth –first search with iterative
deepening).
6. Đồ thị and/or.