Ứng dụng lý thuyết cơ sở trí tuệ nhân tạo
Bài tập Lý thuyết Cơ sở Trí tuệ Nhân tạo – CTT303 Spring 2012
Giáo viên: Nguyễn Ngọc Thảo, Vũ Thanh Hưng 1
CHỦ ĐỀ 1: GIẢI QUYẾT VẤN ĐỀ BẰNG TÌM KIẾM
1. Nội dung lý thuyết
1.1. Định nghĩa bài toán tìm kiếm
- Bài toán tìm kiếm là gì? Các thành phần của bài toán tìm kiếm?
- Qui đổi một số vấn đề thực tế thành bài toán tìm kiếm
1.2. Nhóm thuật toán tìm kiếm mù
1.2.1. Tìm kiếm theo chiều rộng
- Ý tưởng của các thuật toán: Breadth-First Search (BFS), Least Cost Breadth-First
Search (LCBFS), Uniformed-Cost Search (UCS)
- Điểm khác biệt cơ bản của các thuật toán này là gì? (tiêu chí chọn đỉnh kế tiếp,
điều kiện dừng, …)
- Qui tắc tính chi phí đường đi g
- Cách sử dụng hàng đợi ưu tiên trong bài toán tìm kiếm
- Tính đầy đủ và tối ưu của các thuật toán (*)
1.2.2. Tìm kiếm theo chiều sâu
- Ý tưởng của các thuật toán: Depth-First Search (DFS), DFS cải tiến – PCDFS và
MEMDFS
- Tính đầy đủ và tối ưu của các thuật toán
- Điểm khác biệt giữa PCDFS và MEMDS, ưu điểm của mỗi phương pháp trong
trường hợp cụ thể
1.2.3. Tìm kiếm lặp sâu dần
- Ý tưởng của thuật toán Iterative Deepening Search (IDS).
- Tính đầy đủ và tối ưu của IDS
1.3. Nhóm thuật toán tìm kiếm có heuristic
1.3.1. Tìm kiếm tham lam tốt nhất đầu tiên và A*
- Ý tưởng của các thuật toán: Greedy Best First Search (GBFS), A*
- Điểm khác biệt cơ bản của các thuật toán này so với nhóm thuật toán tìm kiếm mù
là gì? (tiêu chí chọn đỉnh kế tiếp, điều kiện dừng, …)
- Qui tắc tính giá trị heuristic h, đại lượng f = g + h
- Tính đầy đủ và tối ưu của các thuật toán (*)
Bài tập Lý thuyết Cơ sở Trí tuệ Nhân tạo – CTT303 Spring 2012
Giáo viên: Nguyễn Ngọc Thảo, Vũ Thanh Hưng 2
1.3.2. Tìm kiếm lặp sâu dần A*
- Ý tưởng của thuật toán Iterative Deepening A*
- Điểm khác biệt giữa IDS và IDA*
- Tính đầy đủ và tối ưu của IDA*
1.4. Thuật giải leo đồi và thuật giải di truyền
- Thuật giải leo đồi có đặc điểm gì giống và khác so với các thuật toán tìm kiếm mù
và tìm kiếm heuristic? Có đảm bảo tìm thấy đường đi và đường đi tối ưu hay
không? Trình bày một số cải tiến của thuật giải leo đồi.
- Ý tưởng của thuật giải di truyền: sơ đồ thuật giải, gen, các toán tử lai và đột biến,
hàm thích nghi, hàm mục tiêu. Làm thế nào biểu diễn gen? Phương pháp bàn quay
Roulette là gì?
Bài tập Lý thuyết Cơ sở Trí tuệ Nhân tạo – CTT303 Spring 2012
Giáo viên: Nguyễn Ngọc Thảo, Vũ Thanh Hưng 3
2. Nội dung bài tập
2.1. Cho bản đồ các thành phố ở Rumani và khoảng cách đường chim bay từ các thành
phố đến Bucharest như bên dưới.
Một khách du lịch muốn tìm đường đi từ Arad đến Bucharest.
a. Hãy tìm đường đi theo từng chiến lược tìm kiếm dưới đây. Trình bày thứ tự mở các
trạng thái, đường đi kết quả và chi phí.
- LCBFS: để tiết kiệm thời gian, giả sử đường đi kết thúc tại Bucharest (không
có đường đi đến Giurgiu và Urziceni) và Lugoj (không có đường đi đến
Mehadia)
- UCS
- Greedy Best First Search: sử dụng heuristic là khoảng cách đường chim bay
- A*: sử dụng heuristic như trong GBFS
b. Hãy tìm đường đi sao cho qua ít thành phố nhất. Trình bày thứ tự mở các trạng thái,
đường đi kết quả và chi phí thực tế.
c. Liệt kê 3 đường đi tùy chọn khi sử dụng thuật toán DFS (có kiểm tra trạng thái đang
nằm trên đường đi). Trình bày thứ tự mở các trạng thái, đường đi kết quả và chi phí
thực tế.
d. Biểu diễn cây tìm kiếm cho từng chiến lược tìm kiếm như trên.
Bài tập Lý thuyết Cơ sở Trí tuệ Nhân tạo – CTT303 Spring 2012
Giáo viên: Nguyễn Ngọc Thảo, Vũ Thanh Hưng 4
2.2. Cho bản đồ một số thành phố ở Châu Âu như bên dưới. Con số nằm trên đường nối
giữa hai thành phố biểu thị thời gian lái xe trung bình (giờ) giữa cặp thành phố này.
Một người đi công tác muốn lái xe từ Warsaw đến Rome. Với mỗi chiến lược tìm kiếm dưới
đây, hãy trình bày thứ tự mở các trạng thái, đường đi kết quả và thời gian lái. Trong mọi yêu
cầu, nếu xảy ra tình trạng trạng thái có chi phí bằng nhau thì chọn mở trạng thái nào có tên
nhỏ hơn theo thứ tự bảng chữ cái (ví dụ Budapest < Munich).
a. Tìm kiếm theo chiều sâu (sử dụng chiến lược kiểm tra trạng thái đang nằm trên
đường đi để tránh lặp vô tận)
b. Tìm kiếm theo chiều rộng
c. Tìm kiếm chi phí đồng nhất
d. Tìm kiếm tham lam tốt nhất đầu tiên với heuristic: h(Odesa) = 20 giờ, h(Budapest) =
12 giờ, h(Munich) = 3 giờ, h(Venice) = 3 giờ, h(Rome) = 0 giờ, h(Warsaw) = 30 giờ.
e. Tìm kiếm A* với cùng heuristic như câu d.
f. Heuristic trong câu d có chấp nhận được hay không? Hãy chứng minh.
Bài tập Lý thuyết Cơ sở Trí tuệ Nhân tạo – CTT303 Spring 2012
Giáo viên: Nguyễn Ngọc Thảo, Vũ Thanh Hưng 5
2.3. Cho trạng thái đầu (a) và trạng thái đích (b) như bên dưới.
1
3
4
2
5
7
8
6
1 2 3
4
5
6
7
8
(a) (b)
Hãy sử dụng thuật toán A* để biến đổi từ trạng thái (a) sang trạng thái (b) sao cho số ô cần
đẩy là ít nhất. Heuristic được sử dụng lần lượt là Khoảng cách Manhattan và Số ô sai so với
trạng thái đích. Với mỗi trường hợp, trình bày cây tìm kiếm và bộ giá trị (f, g, h).
2.4. Cho trạng thái đầu (a) và trạng thái đích (b) như bên dưới.
1
3
6
8
7
2
5
4
1 6 2
7
3
4
8
5
(a) (b)
Hãy sử dụng thuật toán A* để biến đổi từ trạng thái (a) sang trạng thái (b) sao cho số ô cần
đẩy là ít nhất. Heuristic được sử dụng lần lượt là Khoảng cách Manhattan và Số ô sai so với
trạng thái đích. Với mỗi trường hợp, trình bày cây tìm kiếm và bộ giá trị (f, g, h).
2.5. Cho mê cung như hình bên dưới. Đường in đậm biểu diễn vách ngăn không qua được.
Hãy tìm đường đi từ s đến g với các chiến lược tìm kiếm dưới đây. Trình bày thứ tự duyệt các
ô theo định dạng <b
1
, b
2
,..., b
n
>, với b
i
là ô được duyệt.
a. Tìm kiếm theo chiều rộng
b. Tìm kiếm theo chiều sâu có kiểm tra trạng thái đang nằm trên đường đi để tránh lặp
vô tận. Thứ tự mở là Phải → Dưới→ Trái → Trên.
c. Tìm kiếm tham lam tốt nhất đầu tiên với heuristic là khoảng cách Manhattan.
h(state) = số bước ngắn nhất từ state đến g nếu không có rào chắn, ví dụ, h(k) = 2,
h(s) = 4, h(g) = 0.
d. Tìm kiếm A* với cách dừng thông thường
Bài tập Lý thuyết Cơ sở Trí tuệ Nhân tạo – CTT303 Spring 2012
Giáo viên: Nguyễn Ngọc Thảo, Vũ Thanh Hưng 6
2.6. Cho mê cung như hình bên dưới. Đường in đậm biểu diễn vách ngăn không qua được.
Hãy tìm đường đi từ start đến goal với các chiến lược tìm kiếm dưới đây. Trình bày thứ tự
duyệt các ô theo định dạng <b
1
, b
2
,..., b
n
>, với b
i
là ô được duyệt.
a. Tìm kiếm theo chiều rộng.
b.
Tìm kiếm theo chiều sâu có kiểm tra trạng thái đang nằm trên đường đi để tránh lặp
vô tận. Thứ tự mở là Phải → Trái→ Trên → Dưới.
có thể bạn quan tâm
Luận văn thạc sĩ: Một số thuật toán mã hóa khác ứng dụng trong bảo mật...
26
1.609
495
Thạc sĩ cao học
26
(New)
Nghiên cứu nghiêm túc về những mặt tích cực và hạn chế của lý thuyết Z...
12
1.209
646
Kinh tế quản lý
12
(New)
Tiểu luận:Nội dung, nhận định và phân tích triết học Nho giáo, học thu...
26
2.034
521
Lý luận chính trị
26
(New)
TOÁN LỚP 7 LÝ THUYẾT VÀ BÀI TẬP NHÂN, CHIA SỐ HỮU TỈ
3
917
399
Giáo án, bài giảng lớp 7
3
(New)
Tóm tắt lý thuyết và hướng dẫn giải bải tập SGK Sinh học 10: Tế bào nh...
4
888
431
Giải bài tập các môn
4
(New)
LÝ THUYẾT SINH HỌC 12: GEN, MÃ DI TRUYỀN VÀ QUÁ TRÌNH NHÂN ĐÔI CỦA ADN
3
1.088
487
Tài liệu, đề thi Sinh Học
3
(New)
sinh học 12 Nguyên nhân và cơ chế tiến, học thuyết Đacuyn
0
10.496
4
Giáo án, bài giảng lớp 12
(New)
Tóm tắt lý thuyết và hướng dẫn giải bài tập Toán lớp 7: Nhân chia số h...
5
1.316
440
Tài liệu, đề thi môn Toán
5
(New)
thông tin tài liệu
Tài liệu cung cấp một số bài tập về Lý thuyết cơ sở trí tuệ nhân tạo và cách giải
Mở rộng để xem thêm
từ khóa liên quan
tài liệu mới trong mục này
tài liệu hot trong mục này
tài liệu giúp tôi
Nếu bạn không tìm thấy tài liệu mình cần có thể gửi yêu cầu ở đây để chúng tôi tìm giúp bạn!
Toán lớp 1 Tiếng Anh lớp 1 Toán lớp 2 Tiếng Anh lớp 2 Toán lớp 3 Tiếng Anh lớp 3 Toán lớp 4 Tiếng Anh lớp 4 Toán lớp 5 Tiếng Anh lớp 5
Toán lớp 6 Tiếng Anh lớp 6 Toán lớp 7 Tiếng Anh lớp 7 Toán lớp 8 Tiếng Anh lớp 8 Toán lớp 9 Tiếng Anh lớp 9
Toán lớp 10 Tiếng Anh lớp 10 Toán lớp 11 Tiếng Anh lớp 11 Toán lớp 12 Tiếng Anh lớp 12
×
