Cơ sở trí tuệ nhân tạo - Cơ sở dữ liệu | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Heuristic chấp nhận được
• Đặt h*(n) = chi phí tối thiểu thấp nhất từ n đến đích.
• Một heuristic h là chấp nhận được nếu h(n) <= h*(n) với mọi trạng thái n.
• Một heuristic chấp nhận được đảm bảo không bao giờ ước tính quá chi phí đến đích.
• Một heuristic chấp nhận được là tối ưu. Tài liệu được sưu tầm giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem !

17 9 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cơ sở dữ liệu (HCMUS)

Trường: Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Thành phố Hồ Chí Minh

Thông tin:

4 trang 1 tháng trước

Tác giả:

Profile Phạm Thị Huyền
lOMoARcPSD|46342985
lOMoARcPSD|46342985
CƠ SỞ TRÍ TUỆ NHÂN TẠO
1. Tìm đường đi từ A đến G
Heuristic chấp nhận được
• Đặt h*(n) = chi phí tối thiểu thấp nhất từ n đến đích.
• Một heuristic h là chấp nhận được nếu h(n) <= h*(n) với mọi trạng thái n.
• Một heuristic chấp nhận được đảm bảo không bao giờ ước tính quá chi phí đến đích.
• Một heuristic chấp nhận được là tối ưu.
a, BFS b, DFS
Fringe = [A] Fringe = [A]
Fringe = [B C] //Lấy đầu Queue, B Fringe = [C B] //Lấy đầu Stack, B
Fringe = [C D] //Lấy C Fringe = [C D] //Lấy D
Fringe = [D] //Lấy D Fringe = [C G F E] //Lấy E
Fringe = [E F G] //Lấy E
Fringe = [C F G] //Tìm thấy đích, dừng giải thuật
Fringe = [F G] //Lấy F
➔ Đường đi từ A đến G: A, B, D, E, G
Fringe = [G] //Tìm thấy đích, dừng giải thuật
➔ Đường đi từ A đến G: A, B, C, D, E, G
c, UCS Greedy: h1
Close_set: A, B, C, D, F, G
Close_set: A, C, D, G
PQ = [(A:0)]
PQ = [A9.5]
PQ = [(B:1), (C:4)] //Lấy điểm nhỏ nhất: (B:1)
PQ = [B9, C8] //Lấy điểm nhỏ nhất: CPQ = [(C:4), (C:2), (D:6)] //Lấy (C:2)
PQ = [(D:6), (D:5), (D:7)] //Lấy (D:5) PQ = [B9, D7] //Lấy D
PQ = [(E:13), (E:14), (E:15), (F:8), (F:9), (F:10),
PQ = [E1.5, F4, G0] //Lấy G
(G:14), (G:15), (G:16)] // Lấy (F:8)
PQ = [(E:13), (E:14), (E:15), (G:14), (G:15),
Đường đi từ S đến G theo phương pháp
(G:16), (G:13), (G:14), (G:15)] // Lấy (G:13)
Greedy là A, C, D, G
Đường đi từ S đến G theo phương pháp
UCS là A, B, C, D, F, G với chi phí đường
đi là 13.
A*: h1
Close_set: A, B, C, D, F, G
PQ = [A0+9.5]
PQ = [B1+9, C4+8] //Lấy điểm nhỏ nhất, đầu hàng đợi: B
PQ = [C2+8, C4+8, D6+7] //Lấy C
PQ = [D5+7, D6+7] //Lấy D
PQ = [E13+1.5, F8+4, G14+0] //Lấy F
PQ = [E13+1.5, G13+0, G14+0] //Lấy G
➔ Đường đi ngắn nhất từ A đến G theo phương pháp A* là A, B, C, D, F, G.
lOMoARcPSD|46342985
2. Tìm kiếm đối kháng
B=3;C=2,D=2,A=3
α là giá trị max, β là giá trị Min
Để A chọn C thì C>=3, khi duyệt C <=2
không thỏa nên không cần duyệt tiếp
Xét D, D>=3
3. Logic mệnh đề (≡ trùng với, ¬ not, ˄ and, ˅ or)
Dạng viết tắt: α => β ≡ α ˅ β ; α <=> β ≡ (α => β) ˄ (β => α)
Hợp giải: KB = (α ˅ β, ¬ β ˅ γ) KL = (α ˅ γ)
Sau khi hợp giải
không thể ra câu mới
được nữa, mà trong
KB vẫn chưa xuất hiện
mâu thuẫn, không thể
đưa ra kết luận.
Ví dụ 3: KB suy ra
được câu kết luận
lOMoARcPSD|46342985
4. Logic bậc nhất
Naïve Bayes
So sánh P(Y/X) = (P(X|Y) + P(Y))/P(X)
lOMoARcPSD|46342985
ID3
Đi hết các node nhưng không ra được quyết định thì theo đa số
| 1/4
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

lOMoARcPSD|46342985 lOMoARcPSD|46342985
CƠ SỞ TRÍ TUỆ NHÂN TẠO
1. Tìm đường đi từ A đến G
Heuristic chấp nhận được
• Đặt h*(n) = chi phí tối thiểu thấp nhất từ n đến đích.
• Một heuristic h là chấp nhận được nếu h(n) <= h*(n) với mọi trạng thái n.
• Một heuristic chấp nhận được đảm bảo không bao giờ ước tính quá chi phí đến đích.
• Một heuristic chấp nhận được là tối ưu. a, BFS b, DFS Fringe = [A] Fringe = [A]
Fringe = [B C] //Lấy đầu Queue, B
Fringe = [C B] //Lấy đầu Stack, B
Fringe = [C D] //Lấy C
Fringe = [C D] //Lấy D Fringe = [D] //Lấy D
Fringe = [C G F E] //Lấy E
Fringe = [E F G] //Lấy E
Fringe = [C F G] //Tìm thấy đích, dừng giải thuật
Fringe = [F G] //Lấy F
➔ Đường đi từ A đến G: A, B, D, E, G
Fringe = [G] //Tìm thấy đích, dừng giải thuật
➔ Đường đi từ A đến G: A, B, C, D, E, G c, UCS Greedy: h1 Close_set: A, B, C, D, F, G Close_set: A, C, D, G PQ = [(A:0)] PQ = [A9.5]
PQ = [(B:1), (C:4)] //Lấy điểm nhỏ nhất: (B:1)
PQ = [(C:4), (C:2), (D:6)] //Lấy (C:2)
PQ = [B9, C8] //Lấy điểm nhỏ nhất: C
PQ = [(D:6), (D:5), (D:7)] //Lấy (D:5) PQ = [B9, D7] //Lấy D
PQ = [(E:13), (E:14), (E:15), (F:8), (F:9), (F:10), PQ = [E1.5, F4, G0] //Lấy G
(G:14), (G:15), (G:16)] // Lấy (F:8)
PQ = [(E:13), (E:14), (E:15), (G:14), (G:15),
Đường đi từ S đến G theo phương pháp
(G:16), (G:13), (G:14), (G:15)] // Lấy (G:13) Greedy là A, C, D, G
Đường đi từ S đến G theo phương pháp
UCS là A, B, C, D, F, G với chi phí đường đi là 13. A*: h1
Close_set: A, B, C, D, F, G PQ = [A0+9.5]
PQ = [B1+9, C4+8] //Lấy điểm nhỏ nhất, đầu hàng đợi: B
PQ = [C2+8, C4+8, D6+7] //Lấy C
PQ = [D5+7, D6+7] //Lấy D
PQ = [E13+1.5, F8+4, G14+0] //Lấy F
PQ = [E13+1.5, G13+0, G14+0] //Lấy G
➔ Đường đi ngắn nhất từ A đến G theo phương pháp A* là A, B, C, D, F, G. lOMoARcPSD|46342985
2. Tìm kiếm đối kháng B=3;C=2,D=2,A=3
α là giá trị max, β là giá trị Min
Để A chọn C thì C>=3, khi duyệt C <=2 Xét D, D>=3
không thỏa nên không cần duyệt tiếp
3. Logic mệnh đề (≡ trùng với, ¬ not, ˄ and, ˅ or)
Dạng viết tắt: α => β ≡ α ˅ β ; α <=> β ≡ (α => β) ˄ (β => α)
Hợp giải: KB = (α ˅ β, ¬ β ˅ γ) KL = (α ˅ γ) Sau khi hợp giải không thể ra câu mới được nữa, mà trong KB vẫn chưa xuất hiện mâu thuẫn, không thể đưa ra kết luận. Ví dụ 3: KB suy ra
được câu kết luận lOMoARcPSD|46342985 4. Logic bậc nhất Naïve Bayes
So sánh P(Y/X) = (P(X|Y) + P(Y))/P(X) lOMoARcPSD|46342985 ID3
Đi hết các node nhưng không ra được quyết định thì theo đa số