NHẬP MÔN TRÍ TUỆ NHÂN TẠO
@copyrights by Dr Nguyễn Xuân Hoài
Nội Dung
Tìm kiếm có sử dụng thông tin thu nhận
trong quá trình tìm kiếm (informed search):
•
Best-first search
•
Greedy best-first search
•
A
*
search
•
Heuristics
•
Local search algorithms.
•
Hill-climbing search.
•
Simulated annealing search
•
Local beam search.
•
Genetic algorithms.
•
Ant Colony Optimization.
Mấu chốt của chiến lược tìm kiếm
•
Chiến lược chọn node để xử lý tiếp theo (Expand).
Best-first search (BFS)

GBFS chọn node “được cho là” gần với node
đích để expand.
Ví dụ về GBFS
Ví dụ về GBFS
Ví dụ về GBFS
Ví dụ về GBFS
Đánh giá GBFS
•
Đủ? Không – Có thể vào vòng lặp quẩn.
•
Độ phức tạp thời gian? O(b
m
), Nếu hàm
heuristic xấp xỉ tốt trong thực tế thì thời
gian chạy sẽ giảm đi rất nhiều
•
Độ phức tạp không gian? O(b
m
) – Lưu trữ
tất cả các Nodes.
•
Tối ưu? Không.
A
*
search
•
Ý tưởng: Loại bỏ những đường đi có chi
phí cao.
•
Hàm lượng giá f(n) = g(n) + h(n)

*
(n) là chi phí
thực để đi đến đích từ n.
•
Heuristic chấp nhận được không bao giờ đánh
giá chi phí cao quá thực tế.
•
Ví dụ h
SLD
(n) là Heuristic chấp nhận được.
•
Định lý: Nếu h(n) là chấp nhận được, A
*
là thuật
toán cho lời giải tối ưu.
Chứng minh tính tối ưu của A
*
•
Giả sử có đích G
2
được tìm ra và lời giải là không tối ưu.
giải sử n là node chưa được expand trong fringe sao cho
n Nằm trên đường đi tới lời giải tối ưu có đích là G.
•
f(G
2
) = g(G
2
) vì h(G
2

) > f(n), dẫn tới vô lý A
*
không thể lựa chọn G
2
để
expand.
Tính nhất quán của Heuristics
•
heuristic được gọi là nhất quán nếu với mọi node n, mọi
nút con n' của n sinh bởi toán tử chuyển trạng a, ta có:
h(n) ≤ c(n,a,n') + h(n')
•
Nếu h là nhất quán ta có:
f(n') = g(n') + h(n')
= g(n) + c(n,a,n') + h(n')
≥ g(n) + h(n)
= f(n)
•
i.e., f(n) không giảm theo bất cứ đường đi nào.
•
Định lý: Nếu h(n) là nhất quán, A* sử dụng
GRAPH-SEARCH là tối ưu.
•
Tín tối ưu của A
*
•
A
*
xét node theo thứ tự tăng dần của f
•

1
(S) = ?
•
h
2
(S) = ?
•