Xem mẫu
- CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG
Bài toán thoả mãn ràng buộc
THS. BÙI THỊ DANH
BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM
- Nội dung chính
Bài toán thoả mãn ràng buộc (CSP)
Đồ thị ràng buộc
CSP với kĩ thuật quay lui
CSP với tìm kiếm cục bộ
2
- Bài toán thoả mãn ràng buộc (CSP)
Được xem như tập con đặc biệt của bài toán tìm kiếm.
Trạng thái được định nghĩa bởi tập các biến Xi có giá trị nằm trong miền D
◦ Có trường hợp mỗi biến có miền giá trị D khác nhau.
Trạng thái đích được nhận biết thông qua một tập các ràng buộc trên việc kết hợp giá trị
cho các biến.
3
- Ví dụ: Tô màu đồ thị
Các biến: WA, NT, Q, NSW, V, SA, T
◦ Mỗi biến đại diện cho một bang
Miền giá trị: D = {red, green, blue}
Tập ràng buộc: các bang kề nhau không được giống màu
◦ WA ≠ NT, WA ≠ SA, NT ≠ SA …
Lời giải: phép gán màu thoả mãn các ràng buộc, chẳng hạn:
◦ {WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue, T = green}
4
- Ví dụ: N-Hậu
Các biến: Xij
Miền giá trị: D = {0, 1}
Các ràng buộc: "i, j, k, (Xij , Xik ) Î {(0, 0), (0,1), (1, 0)}
"i, j, k, (Xij , Xkj ) Î {(0, 0), (0,1), (1, 0)}
"i, j, k, (Xij , Xi+k, j+k ) Î {(0, 0), (0,1), (1, 0)}
"i, j, k, (Xij , Xi+k, j-k ) Î {(0, 0), (0,1), (1, 0)}
åX ij =N
i, j
5
- Ví dụ: N-Hậu
Các biến: Qk
Miền giá trị: D = {1, 2, 3, …, N}
Các ràng buộc: "i, j, non _ threatening(Qi ,Qj )
6
- CSP trong thực tế
Phân công công việc, chẳng hạn phân công giảng dạy …
Lập lịch: lớp học ở đâu và khi nào?
Lập lịch giao thông
Tổ chức mạch điện
…
7
- Nội dung chính
Bài toán thoả mãn ràng buộc (CSP)
Đồ thị ràng buộc
CSP với kĩ thuật quay lui
CSP với tìm kiếm cục bộ
8
- Đồ thị ràng buộc (constraint graph)
Các node tròn: đại diện cho các biến
Các node vuông: đại diện cho ràng buộc
Các cạnh: nối các biến thông qua node ràng buộc liên quan
9
- Đồ thị ràng buộc
𝒇𝒊 (𝑿) là hàm giá trị cho biết mức độ thoả mãn ràng buộc thứ i.
Trọng số của một phép gán (hay lời giải) x = (𝑥1 , 𝑥2 , … , 𝑥𝑛 ):
Weight x = ෑ 𝑓𝑗 (x)
j=1..𝑚
Mục tiêu bài toán là tìm phép gán có trọng số lớn nhất
Đối với CSP: 𝑓𝑗 (x) ∈ {0,1}
10
- Ví dụ: Tô màu đồ thị
Các biến: X = {WA, NT, SA, Q, NSW, V, T}
Miền giá trị: D = {R, G, B}
Các ràng buộc:
𝑓1 X = WA ≠ NT
𝑓2 X = NT ≠ SA
….
11
- Ví dụ: Sudoku
Các biến: mỗi ô vuông
Miền giá trị: D = {1, 2, …, 9}
Các ràng buộc:
𝑓1 X = allDiff(cột1)
𝑓2 X = allDiff(dòng1)
𝑓3 X = allDiff khối1
.....
12
- Nội dung chính
Bài toán thoả mãn ràng buộc (CSP)
Đồ thị ràng buộc
CSP với kĩ thuật quay lui
CSP với tìm kiếm cục bộ
13
- CSP với kĩ thuật quay lui
Có thể giải CSP bằng các thuật toán của bài toán tìm kiếm, như BFS, DFS, …
Các thành phần của bài toán tìm kiếm tương ứng:
◦ Trạng thái: các giá trị đã gán hiện tại cho biến. Ở đây thực hiện gán một phần tập biến.
◦ Trạng thái bắt đầu: phép gán rỗng {}
◦ Hàm successor(s): gán một giá trị cho một biến chưa gán
◦ Hàm IsGoal(s): phép gán hiện tại đã đầy đủ và thoả tất cả các ràng buộc
14
- CSP với kĩ thuật quay lui
Backtrack(𝒙, 𝒘,𝑫𝒐𝒎𝒂𝒊𝒏𝒔):
If 𝑥 là phép gán đầy đủ then
Cập nhật phép gán tốt nhất và thoát
Else
Chọn một biến chưa gán giá trị 𝑋𝑖
Sắp xếp các giá trị trong Domains𝑖 của biến 𝑋𝑖
Với mỗi giá trị value trong Domains𝑖 theo thứ tự sắp xếp:
Kiểm tra ràng buộc: 𝛿 ← ς𝑓j ∈D(x,𝑋𝑖 ) 𝑓𝑗 (x ∪ 𝑋𝑖 : value )
If 𝛿 == 0 then continue
Cập nhật miền giá trị của các biến: Domains′ ← Filtering(Domains)
Backtrack (x ∪ 𝑋𝑖 : value , δw, Domains’)
End If
15
- Filtering
Filtering là hàm cho phép lưu vết miền giá trị cho các biến chưa được gán và loại bỏ đi các
“giá trị xấu”.
◦ Việc loại bỏ được thực hiện dựa trên các ràng buộc.
◦ Loại bỏ các giá trị khỏi miền giá trị, cho phép tỉa nhánh tăng tốc tìm kiếm.
Các kĩ thuật filtering:
◦ Forward checking
◦ Arc consistency (AC-3)
16
- Forward checking
Ý tưởng: đảm bảo tính nhất quán của các cạnh nối giữa biến Xi được gán giá trị và các láng
giềng của nó.
Nếu có một miền giá trị bị rỗng thì không gọi đệ qui.
Lưu ý: khi bỏ gán biến Xi, cần khôi phục lại miền giá trị tương ứng.
17
- Ví dụ: Forward checking
Tô màu đồ thị
18
- Nội dung chính
Bài toán thoả mãn ràng buộc (CSP)
Đồ thị ràng buộc
CSP với kĩ thuật quay lui
CSP với tìm kiếm cục bộ
19
- CSP với tìm kiếm cục bộ
Kĩ thuật quay lui : mở rộng dần phép gán
Tìm kiếm cục bộ (local search): điều chỉnh các phép gán hoàn
chỉnh
◦ Thuật toán lặp
◦ Leo đồi
◦ Thuật giải di truyền
20
nguon tai.lieu . vn
