Một chiến lược (phương pháp) tìm kiếm = Một cách xác định  ộ ợ   (p         g p    p) ộ ị

thứ tự xét các nút của cây

Các chiến lược tìm kiếm cơ bản (uninformed search 

strategies) chỉ sử dụng các thông tin chứa trong định nghĩa strategies) chỉ sử dụng các thông tin chứa trong định nghĩa 

của bài toán

Không phù hợp với nhiều bài toán thực tế (do đòi hỏi chi phí quá 

cao về thời gian và bộ nhớ) cao về thời gian và bộ nhớ)

Các chiến lược tìm kiếm với tri thức bổ sung (informed search 

strategies) sử dụng các tri thức cụ thể của bài toán → Quá strategies) sử dụng các tri thức cụ thể của bài toán → Quá 

trình tìm kiếm hiệu quả hơn

Best-first search algorithms (Greedy best-first, A*)

( S Local search algorithms (Hill-climbing, Simulated annealing, Local 

beam, Genetic algorithms)

Best-first search

Ý tưởng: Sử dụng một hàm đánh giá f(n) cho mỗi nút của

cây tìm kiếm cây tìm kiếm

Để đánh giá mức độ “phù hợp” của nút đó

Æ Trong quá trình tìm kiếm, ưu tiên xét các nút có mức độ phù hợp

cao nhất cao nhất

Hàm đánh giá f(n) là hàm heuristic h(n)

Hàm heuristic h(n) đánh giá chi phí để đi từ nút hiện tại n

đến nút đích (mục tiêu)

Phương pháp tìm kiếm Greedy best-first search sẽ xét Phương pháp tìm kiếm Greedy best first search sẽ xét 

(phát triển) nút “có vẻ” gần với nút đích (mục tiêu) nhất

A * search

Ý tưởng:  Tránh việc xét (phát triển) các nhánh tìm kiếm 

đã   á   đị  h (  h   đế   thời điể    hiệ   t  i) là   ó   hi   hí đã xác định (cho đến thời điểm hiện tại) là có chi phí cao

Sử dụng hàm đánh giá f(n) = g(n) + h(n)

g(n) = chi phí từ nút gốc cho đến nút hiện tại n

h(n) = chi phí ước lượng từ nút hiện tại n tới đích (  )         p ợ  g ệ    ạ

f(n) = chi phí tổng thể ước lượng của đường đi qua nút hiện tại n

đến đích

Nếu không gian các trạng thái là hữu hạn và có giải 

pháp để tránh việc xét (lặp) lại các trạng thái  thì giải pháp để tránh việc xét (lặp) lại các trạng thái, thì giải 

thuật A* là hoàn chỉnh (tìm được lời giải) – nhưng không 

đảm bảo là tối ưu

Nếu không gian các trạng thái là hữu hạn và không có 

giải pháp để tránh việc xét (lặp) lại các trạng thái, thì giải 

* ỉ     ( ả      ả thuật A* là không hoàn chỉnh (không đảm bảo tìm được 

lời giải)

Nế   khô       i       á   t        thái là   ô h      thì   iải th  ật A* Nếu không gian các trạng thái là vô hạn, thì giải thuật A* 

là không hoàn chỉnh (không đảm bảo tìm được lời giải)

Một ước lượng (heuristic) h(n) được xem là chấp nhận

được nếu đối với mọi nút n: 0 ≤ h(n) ≤ h * (n)  trong đó được nếu đối với mọi nút n: 0 ≤ h(n) ≤ h (n), trong đó

h * (n) là chi phí thật (thực tế) để đi từ nút n đến đích

Một ước lượng chấp nhận được không bao giờ đánh giá

ố ể quá cao (overestimate) đối với chi phí để đi tới đích

Thực chất, ước lượng chấp nhận được có xu hướng đánh giá

“lạc quan”

Ví dụ:   Ước lượng  h SLD (n) không bao giờ đánh giá quá

cao khoảng cách đường đi thực tế

Định lý: Nếu h(n) là đánh giá chấp nhận được, thì

phương pháp tìm kiếm A * sử dụng giải thuật TREE-

SEARCHlà tối ưu SEARCHlà tối ưu

Xây dựng (khởi tạo) quần thể (population) ban đầu

• Tạo nên một số các giả thiết (khả năng của lời giải) ban đầu

Mỗi giả thiết khác các giả thiết khác (vd: khác nhau đối với các giá trị của một • Mỗi giả thiết khác các giả thiết khác (vd: khác nhau đối với các giá trị của một 

số tham số nào đó của bài toán)

Đánh giá quần thể

Đánh giá (cho điểm) mỗi giả thiết (  d   bằng cách kiểm tra độ chính   ác của • Đánh giá (cho điểm) mỗi giả thiết (vd:  bằng cách kiểm tra độ chính xác của 

hệ thống trên một tập dữ liệu kiểm thử)

• Trong lĩnh vực sinh học, điểm đánh giá này của mỗi giả thiết được gọi là độ 

phù hợp (fitness) của giả thiết đó phù hợp (fitness) của giả thiết đó

• Xếp hạng các giả thiết theo mức độ phù hợp của chúng, và chỉ giữ lại các giả 

thiết tốt nhất (gọi là các giả thiết phù hợp nhất – survival  of the fittest)

Sản sinh ra thế hệ tiếp theo (next generation) Sản sinh ra thế hệ tiếp theo (next generation)

• Thay đổi ngẫu nhiên các giả thiết để sản sinh ra thế hệ tiếp theo (gọi là các 

con cháu – offspring)

Lặp lại quá trình trên cho đến khi ở một thế hệ nào đó có giả thiết tốt nhất có độ Lặp lại quá trình trên cho đến khi ở một thế hệ nào đó có giả thiết tốt nhất có độ 

phù hợp cao hơn giá tri phù hợp mong muốn (định trước)

3 toán tử di truyền được sử dụng để sinh ra các cá thể con cháu 

(offspring) trong thế hệ tiếp theo

• Nhưng chỉ có 2 toán tử lai ghép (crossover) và đột biến (mutation) tạo nên 

sự thay đổi

Tái sản xuất (Reproduction) Tái sản xuất (Reproduction)

→ Một giả thiết được giữ lại (không thay đổi)

Lai ghép (Crossover) để sinh ra 2 cá thể mới

Ghép (“phối hợp") của hai cá thể cha mẹ → Ghép ( phối hợp ) của hai cá thể cha mẹ

• Điểm lai ghép được chọn ngẫu nhiên (trên chiều dài của nhiễm sắc thể)

• Phần đầu tiên của nhiễm sắc thể h i

được ghép với phần sau của nhiễm 

sắc thể h j

và ngược lại  để sinh ra 2 nhiễm sắc thể mới sắc thể h j

, và ngược lại, để sinh ra 2 nhiễm sắc thể mới

Đột biến (Mutation) để sinh ra 1 cá thể mới

→Chọn ngẫu nhiên một bit của nhiễm sắc thể, và đổi giá trị (0→1 / 1→0)

Chỉ t       ê      ột th     đổi   hỏ   à     ẫ     hiê   đối   ới    ột   á thể   h        ! • Chỉ tạo nên một thay đổi nhỏ và ngẫu nhiên đối với một cá thể cha mẹ

Một ràng buộc (constraint) là một quan hệ trên một tập các biến

Mỗi biến có (gắn với) một tập các giá trị có thể nhận – gọi là miền  (g          ) p       g g

giá trị (domain)

Trong môn học này, chúng ta chỉ xét các miền hữu hạn các giá trị 

rời rạc

Phương pháp giải quyết bằng kiểm thử (Generate and 

Test)

Sinh ra một khả năng (candidate) của lời giải Sinh ra một khả năng (candidate) của lời giải

Kiểm tra xem khả năng này có thực sự là một lời giải

Á   d         h há   kiể    thử đối   ới bài t  á   CSP Áp dụng phương pháp kiểm thử đối với bài toán CSP

Bước 1. Gán các giá trị cho tất cả các biến

Bước 2. Kiểm tra xem tất cả các ràng buộc được thỏa mãn hay  g     ộ       ợ y

không

Lặp lại 2 bước này cho đến khi tìm được một phép gán thỏa mãn

Điểm yếu nghiêm trọng của phương pháp tìm kiếm bằng 

kiểm thử là việc phải xét quá nhiều các khả năng gán kiểm thử là việc phải xét quá nhiều các khả năng gán 

(hiển nhiên) không thỏa mãn các ràng buộc