Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng

CÁC HỆ THỐNG THÔNG MINH NHÂN TẠO & ỨNG DỤNG

Bài toán tìm kiếm II THS. BÙI THỊ DANH

BM.KHMT, KHOA CNTT, ĐH.KHTN TP.HCM

Nội dung

Heuristic

Tìm kiếm tham lam

Thuật giải A*

Sự nới lỏng

Heuristic

Các thuật toán tìm kiếm mù duyệt trạng thái theo mọi hướng, không sử dụng thông tin của trạng thái đích.

Ước lượng chi phí đến trạng thái đích. Liệu có tìm đường nhanh hơn?!?

Heuristic

Heuristic là một hàm ước lượng mức độ gần của một trạng thái so với trạng thái đích

Heuristic được thiết kế cho từng bài toán tìm kiếm cụ thể

◦ Kí hiệu là h(s), với s là trạng thái.

Một số hàm heuristic phổ biến: ◦ Khoảng cách Euclidean, Mahattan.

◦ …

Ví dụ - Tìm đường đi cho Pacman

Hàm h(s) là hàm Euclidean

Ví dụ - Tìm đường đi trên bản đồ

Hàm h(s) là khoảng cách đường chim bay

Ví dụ - N-Puzzle

Hàm h(s): số ô khác biệt giữa 2 puzzle…

Nội dung

Heuristic

Tìm kiếm tham lam

Thuật giải A*

Sự nới lỏng

Tìm kiếm tham lam (greedy search)

Chiến lược duyệt: mở rộng trạng thái được ước lượng là gần trạng thái đích nhất

Sử dụng hàng đợi ưu tiên để triển khai, với độ ưu tiên là h(s)

◦ Hàm heuristic tương ứng h(s) có giá trị nhỏ nhất

Tùy chọn: đánh dấu các trạng thái đã được xem xét ◦ Đánh dấu khi trạng thái được lấy khỏi hàng đợi

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = null, PQ={(Start,12)}

h = 11 h = 9 h = 6

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = Start/12, PQ={(e, 4), (d, 8), (p,11)}

h = 11 h = 9 h = 6

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = e/4, PQ={ (h,6), (r, 6), (d, 8), (p,11),}

h = 11 h = 9 h = 6

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = h/6, PQ={(r, 6), (d, 8), (q, 9), (p,11),}

h = 11 h = 9 h = 6

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = r/6, PQ={ (f, 4), (d, 8), (q, 9), (p,11),}

h = 11 h = 9 h = 6

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = f/4, PQ={ (Goal, 0), (d, 8), (q, 9), (p,11),}

h = 11 h = 9 h = 6

Ví dụ

Goal

h = 0 2 2 h = 8

h = 5

2 5 8 1

h = 11 2

d

h = 4

Start

h = 8 9 1 h = 4

h

1 h = 12 h = 6

S = Goal/0, PQ={ (d, 8), (q, 9), (p,11),}  Đã tìm thấy Goal

h = 11 h = 9 h = 6

Tìm kiếm tham lam (greedy search) Khởi tạo hàng đợi ưu tiên pQueue Đưa trạng thái bắt đầu start vào pQueue Loop

If không còn trạng thái để mở rộng then return “không có lời giải” Chọn trạng thái s đầu hàng đợi để mở rộng If s là trạng thái đích then return “có lời giải” Gán nhãn cho trạng thái s Với mỗi trạng thái mới s’ mở rộng từ s: If s’ chưa được gán nhãn then

Tí𝑛ℎ ℎ(𝑠′) If 𝑠′ không có trong pQueue then Thêm s’ vào pQueue Ghi nhớ trạng thái trước của s’ là s

end

Tìm kiếm tham lam (greedy search)

Tính đầy đủ:

Tính tối ưu: ◦ Không, vì chỉ dựa vào chi phí ước lượng

◦ Có

Độ phức tạp tính toán: ◦ O(min N, 𝑏max )

Độ phức tạp lưu trữ: ◦ O(min N, 𝑏max )

◦ Thường đưa agent tới thẳng trạng thái đích, nhưng không phải với chi phí tốt nhất

Nội dung

Heuristic

Tìm kiếm tham lam

Thuật giải A*

Sự nới lỏng

Thuật giải A*

Ý tưởng: kết hợp thuật toán UCS và tìm kiếm tham lam

UCS: chiến lược duyệt dựa theo chi phí từ trạng thái bắt đầu đến trạng thái đang xét, 𝑔(𝑠)

Tìm kiếm tham lam: chiến lược duyệt dựa theo chi phí ước lượng từ trạng thái đang xét đến trạng thái cuối, ℎ(𝑠)

Thuật giải A*: chiến lược duyệt dựa theo theo giá trị tổng 𝑓 𝑠 = 𝑔 𝑠 + ℎ(𝑠)

Goal

s

ℎ 𝑠 ,ước lượng …

Start

…

𝑔(𝑠)

Thuật giải A*

Khởi tạo hàng đợi ưu tiên pQueue, Đưa trạng thái bắt đầu start vào pQueue Loop

If không còn trạng thái để mở rộng then return “không có lời giải” Chọn trạng thái s đầu hàng đợi để mở rộng If s là trạng thái đích then return “có lời giải” Gán nhãn cho trạng thái s Với mỗi trạng thái mới (s’) mở rộng từ s:

If 𝑠′ không thuộc pQueue và chưa gán nhãn then

𝑔 𝑠′ = 𝑔 𝑠 + 𝐶 𝑠, 𝑠′ 𝑓 𝑠′ = 𝑔 𝑠′ + ℎ(𝑠′) Thêm s’ vào pQueue và ghi nhớ trạng thái trước của s’ là s

If 𝑠′ thuộc pQueue hoặc đã gán nhãn then

𝑔 𝑠′ = min{𝑔 𝑠′ , 𝑔 𝑠 + 𝐶(𝑠, 𝑠′) f 𝑠′ = 𝑔 𝑠′ + ℎ(𝑠) If 𝑓 𝑠′ giảm then Ghi nhớ trạng thái trước của s’ là s If 𝑓 𝑠′ giảm và s’ đã được gán nhãn then Đưa s’ trở lại hàng đợi

end

Thuật giải A* có tối ưu?

Chi phí ước lượng cao hơn chi phí thực  thuật toán A* cho kết quả không tối ưu

◦ Chi phí đi từ s đến A là 6, nhưng chi phí thực tế chỉ là 1.

Heuristic có thể chấp nhận

Một heuristic là có thể chấp nhận (admissible) nếu:

0 ≤ ℎ 𝑠 ≤ ℎ∗ 𝑠

Định lý: Nếu ℎ(𝑠) là heristic có thể chấp nhận, thuật toán A* với cây tìm kiếm có tính tối

ưu.

◦ Trong đó, ℎ∗(𝑠) là chi phí thực tế nhỏ nhất để đến đích từ s.

Heuristic có thể chấp nhận

Thông thường, admissible heuristic là các lời giải cho các bài tóan được nới lỏng ràng buộc

(relaxation), ở đó có nhiều hành động mới được cho phép.

Đôi khi các inadmissible heuristic cũng có ích

Nội dung

Heuristic

Tìm kiếm tham lam

Thuật giải A*

Sự nới lỏng

Sự nới lỏng (relaxation)

Làm sao để có một heuristic tốt? ◦ Lý tưởng thì h(s) = h*(s). Điều này khó như giải quyết bài toán gốc

◦ Thay vì dùng h*(s) của bài toán gốc, chúng ta dùng h*(s) của bài toán dễ hơn

◦ Heuristic tốt liên quan đến mô hình hóa, không phải xây dựng thuật toán

Sự nới lỏng

Giảm chi phí

Loại bỏ ràng buộc

Tìm kiếm dễ hơn Các bài toán con độc lập Lời giải dạng gần đúng

Lời giải dạng gần đúng

Mục tiêu: di chuyển từ ô hình tam giác đến hình tròn

Nới lỏng: bỏ các bức tường đi

Bài toán sau khi nới lỏng: ℎ∗(𝑠) là khoảng cách Mahattan ◦  Sử dụng ℎ∗(𝑠) này để làm heuristic

Tìm kiếm dễ hơn

Bài toán gốc ◦ Trạng thái bắt đầu: thành phố 1

◦ Hành động walk: từ s đến s+1 ( chi phí là 1)

◦ Hành động tram: từ s đến 2s (chi phí là 2)

◦ Trạng thái đích: thành phố n

Trạng thái: (thành_phố, #walk - #tram) ◦ Số trạng thái từ O(n) thành O(n2)

◦ Ràng buộc: số hành động tram không được nhiều hơn walk

Tìm kiếm dễ hơn

Giữ các thông tin bài toán gốc, nhưng loại bỏ ràng buộc

Trạng thái sau nới lỏng: (thành_phố)

Bài toán sau khi nới lỏng: tìm đường đi từ thành phố 1 đến thành phố n. ◦ Hàm heuristic là ℎ∗(𝑠) của bài toán nới lỏng: kết quả của thuật toán UCS tìm đường từ trạng thái s tới

trạng thái đích hoặc ngược lại

Bài toán con độc lập

Bài toán gốc: các mảnh ghép không được chồng lên nhau

Nới lỏng: Các mảnh ghép có thể chồng lên nhau.

Bài toán sau khi nới lỏng: 8 bài toán con độc lập nhau. ◦ Mỗi bài toán con tương ứng với một dạng gần đúng (slide trước).

◦ Hàm heuristic là hàm tổng của các bài toán con.

Nhắc lại

Các bài toán nới lỏng được sử dụng để lấy giá trị cho hàm heuristic h(s) nhằm định hướng

tìm kiếm. Các lời giải của bài toán nới lỏng không phải là lời giải của bài toán gốc.

Tài liệu tham khảo

Cơ sở Trí tuệ Nhân tạo, Lê Hoài Bắc, Tô Hoài Việt, NXB Khoa học & Kỹ thuật.

Slide bài giảng Trí tuệ nhân tạo, GV. Tô Hoài Việt, GV. Lê Ngọc Thành, Khoa CNTT, ĐH. KHTN TP.HCM

Artificial Intelligence: A Modern Approach, 3rd Edition, S. Russel and P. Norvig, Pearson Education Inc., 2010

Techniques in Artificial Intelligence (SMA 5504) , MIT OpenCourseWare, Massachusetts Institute of Technology

Artificial Intelligence: Principles and Techniques, Stanford courses, Autumn 2015.

Bài giảng Các hệ thống thông minh nhân tạo và ứng dụng - Chương 4: Bài toán tìm kiếm 2