lOMoAR cPSD| 45619127
Câu 1 : Trình bày các yếu tố cần xác định khi biểu diễn vấn đề trong không gian trạng thái ? Hãy đưa ra ví dụ . Bài làm :
Cần xác định các yếu tố : • Trạng thái ban đầu
• Một tập hợp các toán tử
• Một tập hợp T các trạng thái kết thúc (Trạng thái đích) Ví dụ …
Câu 2 : Luật nếu thì là gì ? Lấy ví dụ
Các luật nếu – thì là dạng biểu diễn tự nhiên của tri thức. Bằng cách sử dụng các luật nếu – thì chúng ta
có thể biểu diễn được một số lượng lớn tri thức của con người về tự nhiên, về xã hội, kinh nghiệm của
con người trong lao động, sản xuất, tri thức của các thầy thuốc, tri thức của các kỹ sư, tri thức trong
các ngành khoa học: kinh tế, sinh học, hoá học, vật lý, toán học, … Ví dụ Luật về kinh nghiệm dự báo thời tiết
Nếu : Chuồn chuồn bay thấp Thì : Trời sẽ mưa
Câu 3 : Trình bày khái niệm cây trò chơi , Cách tìm kiếm trên cây trò chơi , Lấy ví dụ về cây trò chơi
Khái niệm : Cây trò chơi là một cấu trúc dữ liệu biểu diễn các trạng thái và các nước đi trong một trò
chơi. Nó được sử dụng trong tìm kiếm và đánh giá các nước đi tiềm năng để đạt được kết quả tốt nhất trong trò chơi.
Cách tìm kiếm trên cây trò chơi bao gồm các bước sau:
• Xây dựng cây trò chơi
• Đánh giá các trạng thái lá
• Lựa chọn nước đi tối ưu
Ví dụ : về cây trò chơi là trong trò chơi Tic-Tac-Toe. Cây trò chơi bắt đầu từ trạng thái ban đầu với bảng
rỗng. Các nút trong cây biểu diễn các trạng thái của bảng và các cạnh liên kết các trạng thái với các nước đi tương ứng.
Câu 4: Trình bày giải thuật Minimax trong tìm kiếm có đối thủ?
Giải thuật Minimax là một thuật toán tìm kiếm trong trò chơi có đối thủ. Nó hoạt động bằng cách xây
dựng một cây trò chơi và lựa chọn các nước đi tối ưu cho người chơi hiện tại và giả sử đối thủ chơi tối ưu
nhất. Giải thuật này sử dụng lần lượt các bước tìm kiếm tối đa và tối thiểu để lựa chọn các nước đi tốt nhất.
• Xây dựng cây trò chơi: Đánh giá các trạng thái lá Lựa chọn tối đa (Max):
• Lựa chọn tối thiểu (Min):
Cuối cùng, giải thuật Minimax trả về nước đi tại nút con của nút gốc có giá trị tối đa, đại diện cho nước đi
tốt nhất cho người chơi hiện tại trong trò chơi có đối thủ. lOMoAR cPSD| 45619127
Cau 5 : Trình bày thuật toán kìm kiếm đầu tiên-tốt nhất: Chiến lược tìm kiếm, viết thủ tục tìm
kiếm, cho ví dụ về xây dựng hàm đánh giá h(u).
Dưới đây là mô tả ngắn gọn về giải thuật này:
1. Giải thuật Best-First Search sử dụng một hàng đợi ưu tiên (OPEN) để lưu trạng thái được sinh
ravà chờ phát triển theo thứ tự tốt nhất.
2. Một danh sách (CLOSE) được sử dụng để lưu trạng thái đã được phát triển.
3. Ban đầu, trạng thái bắt đầu (u0) được đưa vào hàng đợi OPEN.
4. Quá trình lặp tiếp tục cho đến khi hàng đợi OPEN trống.
5. Trong mỗi vòng lặp, trạng thái u đầu tiên trong hàng đợi OPEN được loại bỏ khỏi hàng đợi
vàthêm vào danh sách CLOSE.
6. Nếu trạng thái u là trạng thái đích, thì tìm kiếm thành công và quá trình kết thúc.
7. Với mỗi trạng thái v kề u, nếu v không có trong danh sách OPEN và CLOSE, thì được thêm
vàodanh sách OPEN và được gán cha của v là u. lOMoAR cPSD| 45619127
8. Sau đó, hàng đợi OPEN được sắp xếp lại theo thứ tự tăng dần của hàm h, mà h là một hàm đánhgiá trạng thái v.
9. Nếu không tìm thấy trạng thái đích sau khi đã duyệt qua tất cả các trạng thái có thể, thì tìm
kiếmthất bại và quá trình kết thúc.
Một ví dụ về hàm đánh giá trong trò chơi cờ vua có thể là hàm đếm số lượng quân cờ còn lại cho mỗi bên
và gán giá trị dương cho bên mà chúng ta muốn chiến thắng và giá trị âm cho bên kia. Ví dụ, nếu chúng ta
đang chơi với mục tiêu là chiến thắng, chúng ta có thể đánh giá trạng thái dựa trên sự chênh lệch giữa số
lượng quân cờ còn lại của hai bên.
Câu 6: Trình bày thuật toán kìm kiếm Beam: Chiến lược tìm kiếm, cho ví dụ về xây dựng hàm đánh giá h(u).
Chiến Lược Tìm Kiếm Beam:
• Khởi tạo tập trạng thái ban đầu: bắt đầu với một tập hữu hạn các trạng thái ban đầu.
• Mở rộng trạng thái: mở rộng các trạng thái trong tập hiện tại để tạo ra các trạng thái con.
• Lọc và giữ lại: chọn một số lượng nhỏ nhất các trạng thái con dựa trên một hàm đánh giá.
• Kiểm tra mục tiêu: kiểm tra xem có trạng thái nào trong tập hiện tại là trạng thái mục tiêu hay không.
• Lặp lại: lặp lại quá trình trên cho đến khi tìm được mục tiêu hoặc không còn trạng thái để mở rộng.
Ví dụ, trong bài toán tìm kiếm đường đi ngắn nhất, hàm đánh giá có thể tính toán khoảng cách từ nút u
đến đích mong muốn. Trong trò chơi cờ vua, hàm đánh giá có thể tính toán giá trị của trạng thái hiện tại
dựa trên các yếu tố như số quân cờ còn lại, vị trí của các quân cờ và sự ưu thế của một bên so với bên kia.
Câu 7: Trình bày giải thuật Minimax với độ sâu hạn chế?
Giải thuật Minimax với độ sâu hạn chế là một biến thể của giải thuật Minimax, trong đó tìm kiếm trên cây
trò chơi được giới hạn ở một độ sâu cụ thể. Điều này giúp giảm độ phức tạp tính toán và thời gian tìm
kiếm khi không thể duyệt toàn bộ cây trò chơi.
Các bước của giải thuật Minimax với độ sâu hạn chế như sau:
• Xây dựng cây trò chơi: Xây dựng cây trò chơi từ trạng thái ban đầu của trò chơi, nhưng chỉ
mở rộng cây cho đến một độ sâu đã được chỉ định.
• Đánh giá trạng thái lá: Đánh giá các trạng thái lá ở độ sâu đã đạt được. Điều này có thể
được thực hiện bằng cách sử dụng một hàm đánh giá để xác định giá trị của trạng thái.
• Lựa chọn nước đi tối ưu: Bắt đầu từ trạng thái gốc, thực hiện lựa chọn nước đi tối ưu bằng
cách lựa chọn các nước đi dựa trên giá trị đã được tính toán từ các trạng thái lá. Lựa chọn
nước đi tối ưu có thể sử dụng cách tiếp cận Minimax thông thường, lựa chọn nước đi với
giá trị tối đa cho người chơi hiện tại và giá trị tối thiểu cho đối thủ. lOMoAR cPSD| 45619127
• Giới hạn độ sâu: Khi đạt đến độ sâu đã định, dừng quá trình mở rộng cây và đánh giá các
trạng thái lá. Điều này giới hạn khả năng tìm kiếm và tính toán.
Câu 1: Anh/chị hãy trình bày hai thủ tục thuật toán tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu
trong chiến lược tìm kiếm mù. Hai thủ tục đó khác nhau như thế nào
Theo chiều rộng :Từ 1 đỉnh gốc sẽ duyệt qua tất cả các đỉnh con liền kề của đỉnh đó . Sau đó từ các đỉnh
con này ta lại tiếp tục thực hiện tìm kiếm tất cả các đỉnh con của các đỉnh con đó .Lặp lại cho đến khi không còn 1 nút con nào .
Theo chiều sâu : Có thể nói nôm na là tìm kiếm theo chiều sâu bắt đầu từ đỉnh v được thực hiện trên cơ sở
tìm kiếm theo chiều sâu từ tất cả các đỉnh chưa xét kề với v
Cau 2 : Thuật toán A* được cải tiến từ thuật toán nào và cải tiến như thế nào?
thuật toán A* được cải tiến từ thuật toán tìm kiếm đầu tiên-tốt nhất bằng cách sử dụng hàm đánh giá f(n)
kết hợp giữa chi phí đã đi qua và ước lượng chi phí còn lại để tìm đường đi tối ưu.
Cau 3 : Thuật toán “Tìm kiếm leo đồi” được cải tiến từ thuật toán nào và cải tiến như thế nào?
Thuật toán Tìm kiếm leo đồi được cải tiến từ thuật toán tìm kiếm theo chiều sâu bằng cách kết hợp sử
dụng hàm đánh giá để tìm đường đi tối ưu.
Câu 4 : Thuật toán “Tìm kiếm tốt nhất-đầu tiên (best-first search)” được cải tiến từ thuật toán nào và cải tiến như thế nào?
Thuật toán Tìm kiếm tốt nhất đầu tiên được cải tiến từ thuật toán tìm kiếm theo chiều rộng bằng cách kết
hợp sử dụng hàm đánh giá để tìm đường đi tối ưu.