Xem mẫu
- CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG
Bài toán tìm kiếm I
THS. BÙI THỊ DANH
BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
- Nội dung chính
Tổng quan bài toán tìm kiếm
Cây tìm kiếm
Các thuật toán tìm kiếm mù
2
- Bài toán tìm kiếm
Bài toán tìm đường đi
◦ Tìm đường ngắn nhất,
◦ Tìm đường nhanh nhất
◦ Tìm đường có nhiều cảnh đẹp nhất
Các hành động:
◦ Đi thẳng
◦ Rẽ trái
◦ Rẽ phải
3
- Bài toán tìm kiếm
Giải bài toán puzzle
◦ Tìm cách đạt đến “cấu hình” xác định
Các hành động:
◦ Di chuyển các miếng ghép
4
- Bài toán tìm kiếm
Một bài toán tìm kiếm gồm 5 thành phần:
◦ Không gian trạng thái: S
◦ Tập các hành động: Action(s)
◦ Trạng thái bắt đầu: start
◦ Hàm kiểm tra trạng thái đích: IsGoal(s)
◦ Hàm xác định trạng thái kế tiếp: Successor(s)
◦ Thường đi kèm với hành động và chi phí tương ứng
Một lời giải của bài toán tìm kiếm là một chuỗi các hành động để di chuyển từ trạng thái
bắt đầu đến trạng thái đích.
5
- Không gian trạng thái
Trạng thái (state) là tập các chi tiết / thông tin cần thiết cho việc ra quyết định.
Không gian trạng thái là tập tất cả các trạng thái có thể có.
Kích thước của không gian trạng thái, được tính như sau:
◦ Mỗi trạng thái có N chi tiết
◦ Mỗi chi tiết có miền giá trị là 𝐷𝑖
◦ Kích thước của không gian trạng thái: 𝑆 = 𝐷1 × 𝐷2 × ⋯ × 𝐷𝑁
6
- Bài toán tìm đường đi
Trạng thái: (tên địa điểm)
S : {tất cả các địa điểm trên bản đồ}
Start : điểm xuất phát
IsGoal(s): Có phải điểm muốn đến không?
Successor(s): các trạng thái có thể đi đến được từ s.
Câu hỏi: Kích thước không gian trạng thái là bao nhiêu?
7
- Bài toán tìm đường đi
Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ
thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn.
◦ Không được viếng thăm quá 2 thành phố lẻ
Câu hỏi: trạng thái gồm các chi tiết gì? Từ đó, xác định các thành phần của bài toán?
◦ Trạng thái: (thành phố hiện tại, thành phố trước là lẻ?(true/false))
◦ Actions(s): đi từ thành phố sang thành phố khác
◦ IsGoal(s): s có phải là thành phố n không?
◦ Successor(s): các trạng thái s’(Thành_phố, Là_lẻ). Trong đó,
◦ Thành_phố: chỉ số của thành phố đi đến được, tức 𝑇ℎà𝑛ℎ_𝑝ℎố ≥ 𝑠
◦ Là_lẻ: true nếu s là thành phố lẻ hoặc chi tiết s.Là_lẻ là true.
8
- Bài toán tìm đường đi
Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ
thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn.
◦ Cần viếng thăm ít nhất 3 thành phố lẻ
Câu hỏi: trạng thái gồm các chi tiết gì? Từ đó, xác định các thành phần của bài toán?
9
- Bài toán tìm đường đi
Tìm đường đi ngắn nhất từ thành phố 1 đến thành phố n. Biết rằng chỉ được di chuyển từ
thành phố có chỉ số nhỏ hơn đến thành phố có chỉ số lớn hơn.
◦ Cần viếng thăm số thành phố lẻ nhiều hơn số thành phố chẵn.
Câu hỏi: trạng thái gồm các chi tiết gì? Từ đó, xác định các thành phần của bài toán?
10
- Bài toán Puzzle
Câu hỏi: Cho biết trạng thái gồm các chi tiết gì? Liệt kê các thành phần của bài toán?
11
- Nội dung chính
Tổng quan bài toán tìm kiếm
Cây tìm kiếm
Các thuật toán tìm kiếm mù
12
- Đồ thị trạng thái
Đồ thị trạng thái (state graph): một cách biểu diễn hình học cho bài toán tìm kiếm.
◦ Mỗi đỉnh đồ thị tương ứng với một trạng thái
◦ Mỗi cạnh đồ thị nối trạng thái với một trạng thái kế của nó.
◦ Hàm kiểm tra trạng thái đích chính là tập các đỉnh tương ứng với trạng thái đích
Trong đồ thị trạng thái, mỗi trạng thái chỉ xuất hiện duy nhất một lần
Thường không xây dựng đồ thị trạng thái đầy đủ trên bộ nhớ máy tính vì rất lớn.
13
- Đồ thị trạng thái
14
- Cây tìm kiếm
Cây tìm kiếm (search tree) là cấu trúc cây thể hiện các hành động và kết quả tương ứng của
hành động.
◦ Node gốc tương ứng với trạng thái bắt đầu
◦ Các node con tương ứng với trạng thái kế tiếp của node cha.
◦ Node lá tương ứng với trạng thái đích
◦ Mỗi lời giải tương ứng với một đường đi từ gốc đến node lá
Mỗi trạng thái có thể xuất hiện nhiều hơn 1 lần.
Thường không xây dựng đầy đủ cây tìm kiếm trong bộ nhớ vì rất lớn
15
- Đồ thị trạng thái vs Cây tìm kiếm
16
- Câu hỏi
Giả sử trạng thái bắt đầu là Faragas, hãy vẽ cây tìm kiếm cho đồ thị trạng thái dưới đây?
Eforie
Pitesti
Vaslui
Sibiu
Craiova
Arad Faragas
Lugoj
Zerind Oradea
17
- Cây tìm kiếm
Câu hỏi: có bao nhiêu node trên cây tìm kiếm tương ứng với đồ thị trạng thái sau?
18
- Thuật toán tìm kiếm trên cây
Input: problem – các thành phần của bài toán tìm kiếm
strategy – chiến lược duyệt
Output: solution – nếu tồn tại lời giải; failure – nếu ngược lại
Khởi tạo cây tìm kiếm với trạng thái bắt đầu của problem
Loop
If không còn ứng viên để mở rộng then return “không có lời giải”
Chọn một node lá để mở rộng dựa theo strategy
If node được chọn là trạng thái đích then return “có lời giải”
else mở rộng node và thêm các node kết quả vào cây tìm kiếm
End
19
- Thuật toán tìm kiếm trên cây
Mở rộng dần các trạng thái tiềm năng
Cần cấu trúc dữ liệu hợp lý để đảm bảo thứ tự các trạng thái được xem xét, tạm gọi là
Fringe
Cố gắng mở rộng ít trạng thái nhất có thể.
20
nguon tai.lieu . vn
