TTNT. p.1
Lec 3
Giải quyết vấn đề bằng
tìm kiếm: tìm kiếm mù
TTNT. p.2
Nội dung
◼Biểu diễn bài toán trong Không Gian Trạng Thái
◼Các chiến lược tìm kiếm
–Tìm kiếm mù
–Tìm kiếm kinh nghiệm (heuristic).
◼Tìm kiếm trên không gian trạng thái:
–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 bằng cách đào sâu nhiều lần (depth –
first search with iterative deepening)
◼Sử dụng không gian trạng thái để biễu diễn suy luận
với phép tính vị từ: Đồ thị Và/Hoặc (And/Or Graph)
TTNT. p.3
Giải quyết vấn đề bằng tìm kiếm
◼Khi biểu diễn một vấn đề như là một đồ thị không gian
trạng thái, chúng ta có thể sử dụng lý thuyết đồ thị để
phân tích cấu trúc và độ phức tạp của các vấn đề cũng
như các thủ tục tìm kiếm.
56
Riverbank1
Riverbank 2
Island1Island 2
1
2 3 4
7
Hệ thống cầu thành phố Konigsberg và biểu diễn đồ thị tương ứng
i1
i2
rb1
rb2
b2
b3
b1
b6
b5
b7
b4
TTNT. p.4
Bài toán tìm kiếm
◼Tìm kiếm: là tìm một đối tượng thoả mãn một số đòi hỏi
nào đó, trong một tập hợp rộng lớn các đối tượng
◼Các kỹ thuật tìm kiếm đuợc áp dụng rộng rãi trong lĩnh
vực TTNT :
– Tìm kiếm mù : không có hiểu biết gì về các đối tượng để
hướng dẫn tìm kiếm
– Tìm kiếm kinh nghiệm (heuristic) : dựa vào kinh nghiệm và
hiểu biết về vấn đề cần giải quyết để xây dựng hàm đánh giá
hướng dẫn sự tìm kiếm.
• Tìm kiếm tối ưu
• Tìm kiếm có đối thủ : tìm kiếm nước đi trong các trò chơi hai người (cờ
vua, cờ tướng,...)
TTNT. p.5
Không gian trạng thái
◼Không gian tìm kiếm : bao gồm tất cả các đối tượng mà ta cần quan tâm tìm
kiếm (có thể là không gian liên tục (không gian các véc tơ thực n chiều) hoặc
không gian các đối tượng rời rạc.
◼Toán tử : mô tả hành động hoặc phép biến đổi để đưa một trạng thái tới trạng
thái khác
Ví dụ : Bài toán tìm đường đi : các con đường nối các thành phố sẽ được biểu
diễn bởi các toán tử --->Giải bài toán bằng tìm một dãy các toán tử để đưa
trạng thái ban đầu (điểm xuất phát) về trạng thái kết thúc (điểm đích)
◼Biểu diễn một bài toán trong không gian trạng thái, 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 các trạng thái kết thúc (trạng thái đích).
→Không gian trạng thái có thể được biểu diễn bởi một đồ thị có hướng: mỗi đỉnh
của đồ thị tương đương với một trạng thái, nếu toán tử R biến đổi trạng thái u
thành trạng thái v thì cung (u,v) được gán nhãn R