Bài giảng Cơ sở Trí tuệ nhân tạo‎: Chương 2

THUẬT TOÁN, THUẬT GIẢI MỘT SỐ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ

Nội dung

• Vấn đề, giải quyết vấn đề • Khái niệm về thuật toán, thuật giải • Các nguyên lý của thuật giải heuristic • Các chiến lược tìm kiếm và Thuật giải A*

06/10/2009 Nhập môn Trí tuệ nhân tạo 2

Vấn đề?

Những vướng mắc khó khăn cần giải quyết

Một yêu cầu tìm kiếm xử lý trong một ngữ cảnh cụ thể

Bao gồm:

- các sự kiện - các thông tin - những ràng buộc nhất định.

vấn đề = bài toán

06/10/2009 Nhập môn Trí tuệ nhân tạo 3

Mô hình vấn đề

A  B A: giả thiết, điều kiện ban đầu B: kết luận cần đạt đến : suy luận hay giải pháp cần xác định = một số hữu hạn bước

06/10/2009 Nhập môn Trí tuệ nhân tạo 4

Phân loại vấn đề

• Xác định rõ

- A, B đều rõ

• Chưa rõ

- A rõ, B chưa rõ - A chưa rõ, B rõ - A, B đều chưa rõ

06/10/2009 Nhập môn Trí tuệ nhân tạo 5

Thuật toán

• Thuật toán là giải pháp viết dưới dạng thủ tục và thỏa

3 tiêu chuẩn

Xác định : không mập mờ và có thể thực

thi được

Hữu hạn Đúng

 Thuật toán là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho kết quả mong muốn.

06/10/2009 Nhập môn Trí tuệ nhân tạo 6

Thuật toán

• Tính tổng các số nguyên dương lẻ từ 1n

– B1: S=0; – B2: i=1 – B3: Nếu i=n+1 thì sang bước 7, ngược lại sang

i>n

bước 4 – B4: S=S+i – B5: i=i+2 – B6: Quay lại 3 – B7: Tổng cần tìm là S

06/10/2009 Nhập môn Trí tuệ nhân tạo 7

Thuật toán

Thuật toán có thể được thể hiện qua:

Ngôn ngữ tự nhiên Lưu đồ Mã giả NN lập trình

Ngoài ra thuật toán còn phải đạt hiệu quả cao hay có độ

phức tạp thấp

06/10/2009 Nhập môn Trí tuệ nhân tạo 8

Thuật toán

06/10/2009 Nhập môn Trí tuệ nhân tạo 9

Một số ví dụ về bài toán có độ phức tạp cao

• Bài toán phân công công việc

Một đề án gồm n công việc và các việc sẽ đưọc thực hiên bởi m máy như nhau.

Giả sử biết thời gian để 1 máy thực hiện viêc thứ

j là tj

Yêu cầu: Tìm phương án phân công sao cho thời

gian hoàn thành toàn bộ công việc là thấp nhất.

Mẫu số liệu

n=10, m=3 tj = 4 9 5 2 7 6 10 8 7 5

06/10/2009 Nhập môn Trí tuệ nhân tạo 10

Một số ví dụ về bài toán có độ phức tạp cao

• Bài toán tô màu

Giả sử ta có bản đồ các quốc gia trên thế giới, ta muốn tô màu các quốc gia này sao cho các nước khác nhau được tô khác màu.

Yêu cầu tìm cách tô sao cho số màu sử dụng là ít nhất.

06/10/2009 Nhập môn Trí tuệ nhân tạo 11

06/10/2009 Nhập môn Trí tuệ nhân tạo 12

Một số ví dụ về bài toán có độ phức tạp cao

Bài toán người đưa thư • Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu

06/10/2009 Nhập môn Trí tuệ nhân tạo 13

Thuật giải

• Thuật giải: giải pháp được viết dưới dạng thủ tục

tương tự như thuật toán nhưng không đòi hỏi các tiêu chuẩn như thuật toán.

Tính đúng: chấp nhận các thuật giải đơn giản có

thể cho kết quả đúng hay gần đúng nhưng có khả năng thành công cao hơn.

06/10/2009 Nhập môn Trí tuệ nhân tạo 14

Thuật giải heuristic

Để có thể được chấp nhận thuật giải phải thể hiện một giải pháp hợp lý nhất có thể trong tình huống hiện tại bằng cách:

Tận dụng mọi thông tin hữu ích Sử dụng tri thức, kinh nghiệm trực giác

của con người

Tự nhiên đơn giản nhưng cho kết quả

chấp nhận được

 Thuật giải Heuristic

06/10/2009 Nhập môn Trí tuệ nhân tạo 15

Thuật giải heuristic

Đặc tính • Thường tìm được lời giải tốt, mặc dù không phải là tốt

nhất

• Thực hiện dễ dàng nhanh chóng so với thuật giải tối

ưu

• Khá tự nhiên gần gũi với cách giải của con người

06/10/2009 Nhập môn Trí tuệ nhân tạo 16

Các nguyên lý của thuật giải heuristic

• Vét cạn thông minh • Nguyên lý thứ tự • Nguyên lý tham lam • Hàm heuristic

06/10/2009 Nhập môn Trí tuệ nhân tạo 17

Các nguyên lý của thuật giải heuristic

Vét cạn thông minh

Hạn chế vùng không gian tìm kiếm và có sự định

hướng để nhanh chóng tìm đến mục tiêu.

Tạo miền D’ rất nhỏ so với D Vét cạn trên D’

06/10/2009 Nhập môn Trí tuệ nhân tạo 18

Các nguyên lý của thuật giải heuristic

• Nguyên lý thứ tự

Trong quá trình hành đông để thực hiện việc

chọn lọc các cách làm các trạng thái ta có thể dựa trên một thứ tự hợp lý để giải pháp đạt tính hiệu quả cao

06/10/2009 Nhập môn Trí tuệ nhân tạo 19

Các nguyên lý của thuật giải heuristic

• Nguyên lý tham lam

Trong nhiều vấn đề cần phải đạt đến một 1 mục tiêu tối ưu toàn cục mà không nhìn thấy được toàn bộ quá trình hành động, hơn nữa trong từng bước ta phải lựa chọn hành động dựa trên những thông tin cục bộ. Khi đó trong từng bước của quá trình hành động người ta dựa trên mục tiêu tối ưu toàn cục để định ra mục tiêu cục bộ và dựa theo đó chọn lựa hành động

06/10/2009 Nhập môn Trí tuệ nhân tạo 20

Các nguyên lý của thuật giải heuristic

• Hàm heuristic

Là hàm ứng với mỗi trạng thái hay mỗi sự chọn lựa một giá trị có ý nghĩa đối với vấn đề để dựa vào giá trị hàm này ta chọn lựa hành động.

06/10/2009 Nhập môn Trí tuệ nhân tạo 21

Ví dụ 1

• Giải xấp xỉ nghiệm của phương trình f(x)=0 liên tục

trên [a,b] với f(a)f(b)<0.

• Với điều kiện f(a)f(b)<0 và f liên tục trên a,b ta biết

f(x) có nghiệm thuộc [a,b]. phương pháp vét cạn như sau: – Gọi c là trung điểm của [a,b] – Nếu f(a)f(c)<0 thì b=c, ngược lại a=c

06/10/2009 Nhập môn Trí tuệ nhân tạo 22

Ví dụ 2

Thuật giải cho bài toán phân công đơn giản

Chọn việc J chưa phân công có thời gian thực hiện cao nhất phân công cho máy có thời gian làm việc thấp nhất

for(k=0;k

{

Chọn việc J chưa phân công có thời gian thực hiện

cao nhất.

Chọn máy M có thời gian làm việc thấp nhất Bố trí việc J cho máy M.

} 06/10/2009

Nhập môn Trí tuệ nhân tạo 23

Ví dụ 2

n=10, m=3 tj = 4 9 5 2 7 6 10 8 7 5

2 máy, 5 công việc (3,3,2,2,2)

06/10/2009 Nhập môn Trí tuệ nhân tạo 24

Ví dụ 3

• Bài toán tô màu

– QT1: Chọn đỉnh có số đỉnh chưa tô ở cạnh nó là

lớn nhất (bậc lớn nhất)

– QT2: Chọn màu:Với một đỉnh N đang xét, trước tiên thử tô bằng những màu đã tô, nếu không được thì sử dụng màu mới

– Sau khi tô màu cho đỉnh N thì ta xóa các cạnh có nối đến N và đánh dấu các đỉnh kế bên không được tô màu vừa tô cho N

06/10/2009 Nhập môn Trí tuệ nhân tạo 25

06/10/2009 Nhập môn Trí tuệ nhân tạo 26

Ví dụ 3

• Có một cuộc hội thảo khoa học với 9 chủ đề khác

nhau: A, B, C…

•

Các chủ đề sau không được đồng thời; AE, BC,

ED, ABD, AHI, BHI, DFI, DHI, FGH.

•

Xây dựng lịch sao cho số buổi tổ chức là ít nhất

06/10/2009 Nhập môn Trí tuệ nhân tạo 27

Ví dụ 4

Bài toán người đưa thư

•

thuật giải GST(Greedy Traveling Saleman): Ở mỗi bước chọn cạnh

ngắn nhất tiếp theo để đi

Tạo ra lịch từ p thành phố xuất phát riêng biệt. Tìm p chu trình qua n thành phố Chỉ chu trình tốt nhất trong p chu trình được giữ lại.

06/10/2009 Nhập môn Trí tuệ nhân tạo 28

Ví dụ 5

• Có 1 trạm cấp nước và N điểm dân cư. Hãy xây dựng chương trình thiết kế tuyến đường ống nước cung cấp đến mọi nhà sao cho tổng chiều dài đường ống phải dùng là ít nhất. Giả sử rằng các đường ống chỉ được nối giữa 2 điểm dân cư hoặc giữa trạm cấp nước với điểm dân cư.

06/10/2009 Nhập môn Trí tuệ nhân tạo 29

Ví dụ 5

06/10/2009 Nhập môn Trí tuệ nhân tạo 30

Ví dụ 5

• Sắp xếp các cạnh theo thứ tự tăng của trọng số •

for(i=0;i

lấy cạnh ej nhỏ nhất thêm vào T sao cho T

không có chu trình

• Kết thúc ta có T là cây khung nhỏ nhất

06/10/2009 Nhập môn Trí tuệ nhân tạo 31

Bài toán tìm kiếm

Vấn đề = Tìm kiếm mục tiêu

06/10/2009 Nhập môn Trí tuệ nhân tạo 32

Không gian trạng thái

• Không gian trạng thái: tập tất cả các trạng thái có thể

có của bài toán.

06/10/2009 Nhập môn Trí tuệ nhân tạo 33

Các ví dụ

06/10/2009 Nhập môn Trí tuệ nhân tạo 34

06/10/2009 Nhập môn Trí tuệ nhân tạo 35

• Bài toán đổ nước • Bài toán người quỷ qua sông

06/10/2009 Nhập môn Trí tuệ nhân tạo 36

Không gian trạng thái

• Giữa các trạng thái có sự liên hệ gọi là chuyển trạng

thái hay toán tử chuyển trạng thái.

06/10/2009 Nhập môn Trí tuệ nhân tạo 37

Ví dụ

• Trạng thái đầu và cuối của bài toán 8 số • Các toán tử: qua trái, phải, lên trên, xuống dưới

06/10/2009 Nhập môn Trí tuệ nhân tạo 38

• Biểu diễn trạng thái bằng (a, b, k)

Với a, b là số người và quỷ ở bên bờ phải k=1 là thuyền ở bờ phải, k=0 thuyền ở bờ trái

Không gian trạng thái

Trạng thái ban đầu (3, 3, 1) Các toán tử: chở 1 người, 1 quỷ, 2 người, 2 quỷ,

1người và 1 quỷ

Trạng thái kết thúc (0, 0, 0)

06/10/2009 Nhập môn Trí tuệ nhân tạo 39

06/10/2009 Nhập môn Trí tuệ nhân tạo 40

Không gian trạng thái

• Không gian trạng thái này có thể được biểu biễn bằng

đồ thị

• Đồ thị trang thái xác định khi:

– Biết trạng thái đầu – Biết hàm next(S)(tập hợp toán tử) trả về các trạng thái kế

của S.

– Biết trạng thái kết thúc (tập trạng thái kết thúc)

06/10/2009 Nhập môn Trí tuệ nhân tạo 41

Cây tìm kiếm

06/10/2009 Nhập môn Trí tuệ nhân tạo 42

Cây tìm kiếm

06/10/2009 Nhập môn Trí tuệ nhân tạo 43

Phát biểu bài toán

• Trên một đồ thị có trọng số dương ta muốn tìm đường đi ngắn nhất từ một đỉnh xuất phát S0 đến một đỉnh mục tiêu G. Giả sử ta có thêm thông tin như sau: tại mỗi đỉnh S ta biết ước tính quãng đường từ S đến mục tiêu là h(S).

06/10/2009 Nhập môn Trí tuệ nhân tạo 44

Các đặc điểm của bài toán(vấn đề)

• Khả năng phân rã ? • Khả năng lờ đi và quay lui. • Khả năng dự đoán toàn cục. • Mục tiêu là trạng thái hay con đường. • Lượng tri thức cần để giải bài toán. • Có cần sự can thiệp của con người trong quá trình

giải không?

06/10/2009 Nhập môn Trí tuệ nhân tạo 45

Khả năng phân rã

06/10/2009 Nhập môn Trí tuệ nhân tạo 46

Khả năng lờ đi và quay lui

– Có thể lờ đi : như BT chứng minh định lý.

• Vì: định lý vẫn đúng sau một vài bước áp dụng các luật.

– Có thể quay lui: như BT 8-puzzle.

• Vì: có thể di chuyển theo hướng ngược lại để về TT trước.

– Không thể quay lui: như BT chơi cờ.

• Vì: game over!

06/10/2009 Nhập môn Trí tuệ nhân tạo 47

Khả năng dự đoán của bài toán:

– Có thể dự đoán được: như BT 8 puzzle.

• có thể đề ra 1 chuổi nước đi và tự tin vào kết

qua sẽ xãy ra.

– Không thể dự đoán được: như các game

có đối kháng. • Cần theo đuổi nhiều kế hoạch. • Có chiến lược/đánh giá để chọn kế hoạch tốt.

06/10/2009 Nhập môn Trí tuệ nhân tạo 48

Lời giải là trạng thái hay con đường:

06/10/2009 Nhập môn Trí tuệ nhân tạo 49

Vai trò của tri thức là gì?

– Cần ít tri thức:

• Như bài toán: “chơi cờ”. • Tri thức = luật để di chuyển hợp lệ, cơ chế điều khiển, chiến lược điều khiển để tăng tốc tìm kiếm.

– Cần nhiều tri thức:

• Như bài toán: Hiểu câu chuyện trên tạp chí. • Tri thức: nhiều, cả những cái đã ghi tường minh và cả những cái không được ghi trong chính câu chuyện.

06/10/2009 Nhập môn Trí tuệ nhân tạo 50

Công việc có cần tương tác với con người?

– Không cần tương tác: CT nhận mô tả bài toán, sinh ra lời giải mà

không cần sự tương tác với con người trong quá trình giải để nhận thêm thông tin hay để giải thích các bước.

• Như BT: chứng minh định lý (với yêu cầu đơn giản là vào đlý – ra là lời

giải).

– Cần tương tác: CT cần tương tác với con người để nhận thêm thông

tin, để giải thích, để nhận được hướng dẫn cần thiết.

• Như BT: xây dựng các hệ chuẩn đoán bệnh.

– Sự phân biệt này cũng có tính tương đối. Như việc chứng minh đlý nói trên, đôi lúc CT cũng được yêu cầu để giải thích từng bước chứng minh hay đôi cũng cần phải nhận hướng dẫn để bắt đầu từ điềm nào.

– Xác định được CT có cần tương tác hay không sẽ giúp chọn ra

phương pháp giải thích hợp.

06/10/2009 Nhập môn Trí tuệ nhân tạo 51

Các vấn đề trong thiết kế các CT tìm kiếm

• Xác định hướng tìm (forward hay backward

reasoning).

• Cách lựa chọn luật để áp dụng (matching) • Cách biểu diễn NODE của quá trình tìm (knowledge

representation problem, frame problem).

• Các NODE trong đồ thị có thể được phát sinh nhiều lần, và có thể đã được xem xét trước đó trong quá trình duyệt  cần loại bỏ những NODE lặp lại.  cần lưu lại các NODE đã xét.

06/10/2009 Nhập môn Trí tuệ nhân tạo 52

Lý thuyết đồ thị - Review

• Đồ thị: là một cấu trúc bao gồm:

– Tập các nút N1, N2,… Nn,.. Không hạn chế – Tập các cung nối các cặp nút, có thể có nhiều cung trên một

cặp nút

A

B

A

B

C

D

E

D

C

E

Nút: {A,B,C,D,E}

Cung: {(a,d), (a,b), (a,c), (b,c), (c,d), (c,e), (d,e) }

Nhập môn Trí tuệ nhân tạo 06/10/2009 53

Đặc tính đồ thị

• Đồ thị có hướng: là đồ thị với các cung có

định hướng, nghĩa là cặp nút có quan hệ thứ tự trước sau theo từng cung. Cung (Ni,Nj) có hướng từ Ni đến Nj, Khi đó Ni là nút cha và Nj là nút con.

• Nút lá: là nút không có nút con. • Path: là chuổi có thứ tự các nút mà 2 nút kế

tiếp nhau tồn tại một cung.

06/10/2009 Nhập môn Trí tuệ nhân tạo 54

Đặc tính đồ thị

• Đồ thị có gốc: Trên đồ thị tồn tại nút X sao cho tất cả các path đều đi qua nút đó. X là gốc - Root

• Vòng : là một path đi qua nút nhiều hơn một

lần

• Cây: là graph mà không có path vòng • Hai nút nối nhau :nếu có một path đi qua 2

nút đó

06/10/2009 Nhập môn Trí tuệ nhân tạo 55

Các chiến lược tìm kiếm

• Tìm kiếm mù • Tìm kiếm tốt nhất • Tìm kiếm heuristic

 Mục tiêu: tìm ra một solution path

và/hay solution path tốt nhất

06/10/2009 Nhập môn Trí tuệ nhân tạo 56

Tìm kiếm mù

• Tìm kiếm theo chiều sâu • Tìm kiếm theo chiều rộng • Tìm kiếm sâu dần

06/10/2009 Nhập môn Trí tuệ nhân tạo 57

• O = {S}; C={}; • While O khác rỗng •

{

Lấy p trong O Duyệt p Bỏ p vào C Với mỗi q kề p, q không thuộc C: bỏ q vào O

•

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 58

Tìm kiếm theo chiều sâu

• Tìm kiếm sâu trong không gian bài toán được bắt đầu từ một nút rồi tiếp tục cho đến khi hoặc đến ngõ cụt hoặc đến đích

• Tại mỗi nút có luật trọng tài

06/10/2009 Nhập môn Trí tuệ nhân tạo 59

Tìm kiếm theo chiều sâu

• O = {S}; C={}; • While O khác rỗng •

{

Lấy p từ đầu O Duyệt p Bỏ p vào C Với mỗi q kề p, q không thuộc C: bỏ q vào đầu O

•

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 60

06/10/2009 Nhập môn Trí tuệ nhân tạo 61

06/10/2009 Nhập môn Trí tuệ nhân tạo 62

Tìm kiếm theo chiều rộng

• Tìm kiếm trên tất cả các nút của một mức trong

không gian bài toán trước khi chuyển sang các nút của mức tiếp theo

06/10/2009 Nhập môn Trí tuệ nhân tạo 63

Tìm kiếm theo chiều rộng

• O = [S]; C={}; • While O khác rỗng •

{

Lấy p từ đầu O Duyệt p Bỏ p vào C Với mỗi q kề p, q không thuộc C: bỏ q vào cuối O

•

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 64

06/10/2009 Nhập môn Trí tuệ nhân tạo 65

06/10/2009 Nhập môn Trí tuệ nhân tạo 66

• Bài

tập 3. Đại dương được xem như là một mặt phẳng toạ độ trên đó có n hòn đảo với toạ độ lần lượt là (x1, y1), (x2, y2), …, (xn, yn). Một chiếc ca nô xuất phát từ đảo d1 muốn tuần tra đến đảo d2. bình xăng của ca nô chỉ chứa đủ xăng để đi được một quãng đường dài không quá m (km). Trên đường đi ca nô có thể ghé một số đảo nào đó để tiếp thêm xăng, lúc này ca nô được tiếp thêm xăng đầy bình chứa. Hãy chỉ ra một đường đi từ đảo d1 đến đảo d2 sao cho số lần ghé đảo trung gian để tiếp thêm xăng là ít nhất.

06/10/2009 Nhập môn Trí tuệ nhân tạo 67

Tìm kiếm sâu dần

• Kỹ thuật tìm kiếm sâu dần là thực hiện việc tìm kiếm với độ sâu ở mức giới hạn d nào đó. Nếu không tìm ra nghiệm ta tăng độ sâu lên d+1 và lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên được lặp lại với d lần lượt là 1, 2,...đến độ sâu max nào đó

06/10/2009 Nhập môn Trí tuệ nhân tạo 68

Tìm kiếm tốt nhất

• Dùng tri thức về bài toán để hướng dẫn • Tại mỗi nút được xem xét: tìm kiếm tiếp tục theo

nhánh nào tin tưởng sẽ dẫn đến lời giải.

06/10/2009 Nhập môn Trí tuệ nhân tạo 69

Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (1)

Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n

C : đỉnh đóng O : đỉnh mở

Bước 1: O= {S}

C={} g(S)=0 Bước 2: While (O≠{})

2.1 Chọn N thuộc O có g(N) nhỏ nhất

N: mục tiêu  dừng, thông báo kết quả Nếu không tồn tại N  dừng

2.2 Chuyển N qua C, và mở các Q sau N g(Q) = g(N)+cost(N,Q)

Bước 3: Không có kết quả.

06/10/2009 Nhập môn Trí tuệ nhân tạo 70

06/10/2009 Nhập môn Trí tuệ nhân tạo 71

06/10/2009 Nhập môn Trí tuệ nhân tạo 72

Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (2)

Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n

C : đỉnh đóng O : đỉnh mở

Bước 1: O= {S}

C={} g(S)=0 Bước 2: While (O≠{})

2.1 Chọn N thuộc O có g(N) nhỏ nhất

N: mục tiêu  dừng, thông báo kết quả Nếu không tồn tại N  dừng

2.2 Chuyển N qua C, và mở các Q sau N g(Q) = g(N)+cost(N,Q)

Bước 3: Không có kết quả.

06/10/2009 Nhập môn Trí tuệ nhân tạo 73

Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (3)

Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n

C : đỉnh đóng O : đỉnh mở

Bước 1: O= {S}

C={} g(S)=0 Bước 2: While (O≠{})

2.1 Chọn N thuộc O có g(N) nhỏ nhất

N: mục tiêu  dừng, thông báo kết quả Nếu không tồn tại N  dừng

2.2 Chuyển N qua C, và mở các Q sau N

Bước 3: Không có kết quả.

06/10/2009 Nhập môn Trí tuệ nhân tạo 74

Tìm kiếm đường đi có giá thành cực tiểu Thuật toán AT (3)

• 2.2 Chuyển N qua C, và mở các Q sau N

2.2.1 Nếu Q đã có trong O

nếu g(Q)> g(N)+cost(N,Q)

g(Q) = g(N)+cost(N,Q) prev(Q)=N

2.2.2 Nếu Q chưa có trong O g(Q) = g(N)+cost(N,Q) prev(Q)=N

06/10/2009 Nhập môn Trí tuệ nhân tạo 75

Thuật toán AKT

Mỗi đỉnh tương ứng với 1 số g(n): giá thành đi từ đỉnh ban đầu tới n

C : đỉnh đóng O : đỉnh mở

Bước 1: O= {S}

C={} g(S)=0, f(S) = h(S)

Bước 2: While (O≠{})

2.1 Chọn N thuộc O có f(N) nhỏ nhất

N: mục tiêu  dừng, thông báo kết quả Nếu không tồn tại N  dừng

2.2 Chuyển N qua C, và mở các Q sau N

g(Q) = g(N)+cost(N,Q); f(Q)=g(Q)+h(Q);

Bước 3: Không có kết quả.

06/10/2009 Nhập môn Trí tuệ nhân tạo 76

Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*

Cụ thể trong quá trình lựa chọn đỉnh để duyệt xét các đỉnh kế tiếp thì thuật giải A* dựa vào giá trị sau:

f(N) = g(N) + h(N) với g(N) số đo lộ trình từ S tới N

f(N) ước tính độ dài từ S đến N

06/10/2009 Nhập môn Trí tuệ nhân tạo 77

Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*

Bước 1:

C = {}; O = {S}; g(S) = 0; f(S) = h(S);

06/10/2009 Nhập môn Trí tuệ nhân tạo 78

Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*

Bước 2:

while(O≠{}) {

2.1 Chọn N  O có f(N) nhỏ nhất 2.2 Lấy N từ O cho vào C 2.3 if(NG)

Dừng. Kết luận: tìm được

06/10/2009 Nhập môn Trí tuệ nhân tạo 79

Tìm kiếm cực tiểu sử dụng hàm đánh giá - Thuật toán A*

2.4 Xét các đỉnh kế S của N TH1: SO và S  C

if(g(S)>g(N)+w(N,S))

g(S)= g(N)+w(N,S); f(S)=g(S)+h(S); prev(S)=N

TH2: SO và S  C

g(S)= g(N)+w(N,S); f(S)=g(S)+h(S); prev(S)=N

} Bước 3: Kết luận…

06/10/2009 Nhập môn Trí tuệ nhân tạo 80

A* - Ví dụ

• Trạng thái đầu và cuối của bài toán 8 số • Các toán tử: qua trái, phải, lên trên, xuống dưới

h(Si) = số nút sai của Si so với G

06/10/2009 Nhập môn Trí tuệ nhân tạo 81

06/10/2009 Nhập môn Trí tuệ nhân tạo 82

Puzzle – Cài đặt

#define UP 1 #define DN 2 #define LT 3 #define RT 4 #define NO 0

06/10/2009 Nhập môn Trí tuệ nhân tạo 83

Puzzle – Cài đặt

typedef char TAB[3][3]; struct info{ TAB S; unsigned g,h,f; int d;

};

06/10/2009 Nhập môn Trí tuệ nhân tạo 84

Puzzle – Cài đặt

define SIZE 500 typedef struct List{

int n; info e[SIZE]; List(){n=0;} void them(info X); info timfnho(); void xuatlist(); int vitri(info X)

};

06/10/2009 Nhập môn Trí tuệ nhân tạo 85

Puzzle – Cài đặt

List O,C,KQ; TAB S0, G; void main() {

nhap(); if(Astart()) {

timkq(); KQ.xuatlist();

} }

06/10/2009 Nhập môn Trí tuệ nhân tạo 86

Puzzle – Cài đặt

void nhap(); unsigned count(TAB S); //h int sobang(TAB S1, TAB S2); void ganbang(TAB S1, TAB S2); //gán S2 cho S1 void timotrong(TAB S, int &k, int &l) void bangke(TAB N, int d, TAB S,int k, int l) //S là bảng

kề của N int Astart(); void xulyke(info X, int d, TAB S); void xuat(TAB S); void timkq();

06/10/2009 Nhập môn Trí tuệ nhân tạo 87

Puzzle – Cài đặt

int Astart() {

info X; ganbang(X.S,S0); X.g=0; X.h=count(S0); X.f=X.h; X.d=NO; O.them(X); while(O.n>0) {

X=O.timfnho(); C.them(X);

06/10/2009 Nhập môn Trí tuệ nhân tạo 88

Puzzle – Cài đặt

while(O.n>0)

{

X=O.timfnho(); C.them(X); if(sobang(X.S,G)) return 1; timotrong(X.S, k, l); if(k>0) {

d=UP; bangke(X.S,d,BK,k,l); xulyke(X,d,BK);

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 89

Puzzle – Cài đặt

if(k<2){…} if(l>0){…} if(l<2){…} } return 0;

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 90

Puzzle – Cài đặt

void xulyke(info X, int d, TAB S) {

info Y; int k; if(C.vitri(S)==-1) return; if(k=O.vitri(S)==-1) {

ganbang(Y.S,S); Y.g=X.g+1; Y.h=count(S); Y.f=Y.g+Y.h; Y.d=d; O.them(Y);

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 91

Puzzle – Cài đặt

}

else if(X.g+1

O.e[k].g=X.g+1; O.e[k].f= O.e[k].g+ O.e[k].h; O.e[k].d=d;

}

06/10/2009 Nhập môn Trí tuệ nhân tạo 92

Chiến lược minimax

• Giải thuật tìm kiếm Heuristic với các hàm

heuristic chỉ thích hợp cho các bài toán không có tính đối kháng. Như các trò chơi chỉ có một người chơi: Puzzle, tìm lối ra mê cung, bài toán n quân hậu,…

• Các trò chơi có tính đối kháng cao, thường là các trò chơi 2 người chơi như: tic tac toe, caro, cờ quốc tế,… giải thuật trên không có tác dụng vì: Đối phương không bao giờ đi theo con đường cho ta có thể đi đến goal

06/10/2009 Nhập môn Trí tuệ nhân tạo 93

Chiến lược minimax

• Cần phải có một giải thuật khác phù hợp hơn.

Chiến lược MINIMAX

• Chiến lược Minimax (được thể hiện bằng giải

thuật minimax) dựa trên 2 giả thiết sau: – Cả 2 đối thủ có cùng kiến thức như nhau về

không gian trạng thái của trò chơi

– Cả 2 đối thủ có cùng mức cố gắng thắng như

nhau

06/10/2009 Nhập môn Trí tuệ nhân tạo 94

Giải thuật minimax

Hai đối thủ trong trò chơi có tên là MAX và MIN

– Max: biểu diễn cho mục đích của đối thủ này

là làm lớn tối đa lợi thế của mình

– Min: biểu diễn cho mục đích của đối thủ này là

làm nhỏ tối đa lợi thế của đối phương. Trên cây tìm kiếm sẽ phân lớp thành các lớp Max

và Min.

06/10/2009 Nhập môn Trí tuệ nhân tạo 95

Giải thuật minimax

Với một node n bất kỳ,

– Nếu nó thuộc lớp Max thì gán cho nó giá trị

Max của các node con

– Nếu nó thuộc lớp Min thì gán cho nó giá trị

nhỏ nhất của các node con.

06/10/2009 Nhập môn Trí tuệ nhân tạo 96

Minimax – Ví dụ

-2

Maximizing ply Player

-6

-2

-4

Minimizing ply Opponent

E 9

F -6

G 0

H 0

I -2

J -4

K -3

06/10/2009 Nhập môn Trí tuệ nhân tạo 97

Giải thuật minimax – ví dụ

• Bài toán que diêm

Một tập que diêm ban đầu đặt giữa 2 người chơi. Lần lượt đi xen kẽ. Người đến lượt đi phải chia nhóm que diêm theo nguyên tắc: – Chọn nhóm bất kỳ có số que >2 – Chia thành 2 nhóm có số que khác nhau

Goal: người nào đến lượt mà không chia được là

thua.

06/10/2009 Nhập môn Trí tuệ nhân tạo 98

Giải thuật minimax – ví dụ

• Không gian trạng thái của trò chơi được phát

triển toàn bộ, các node lá được gán giá trị 1 nếu là MAX thắng và 0 nếu là MIN thắng.

• Với một node bất kỳ nếu thuộc lớp MAX gán cho nó giá trị lớn nhất của các node con. Nếu thuộc lớp MIN gán cho nó giá trị nhỏ nhất của các node con.

06/10/2009 Nhập môn Trí tuệ nhân tạo 99

Minimax – bài toán que diêm

7 0

MIN

6-1 0

5-2 1

4-3 0

MAX

5-1-1 0

4-2-1 0

3-2-2 1

3-3-1 0

MIN

4-1-1-1 1

3-2-1-1 0

2-2-2-1 1

MAX

3-1-1-1-1 1

2-2-1-1-1 0

MIN

2-1-1-1-1-1 1

MAX

06/10/2009 Nhập môn Trí tuệ nhân tạo 100

Minimax với độ sâu giới hạn

• Minimax như đã xét buộc phải có toàn bộ không gian trạng thái đã được triển khai để có thể gán trị cho các nút lá và tính ngược lại  Không khả thi với các bài toán lớn vì không gian trạng thái là quá lớn.

 Giới hạn không gian trạng thái lại theo một độ sâu

nào đó và giới hạn các node con theo một qui tắc nào đó.

• Đây là chiến lược thông thường của các người chơi

cờ: khả năng tính trước bao nhiêu nước.

06/10/2009 Nhập môn Trí tuệ nhân tạo 101

Minimax với độ sâu giới hạn

• Khi đó ta chỉ triển khai các nút con đến độ sâu giới

hạn.

• Đánh giá cho các nút này như là nút lá bằng một hàm

lượng giá Heuristic.

• áp dụng chiến lược minimax cho việc đánh giá các

nút cấp trên.

• Kỹ thuật này gọi là nhìn trước K bước với K là độ sâu

giới hạn.

06/10/2009 Nhập môn Trí tuệ nhân tạo 102

Ví dụ: Bài toán Tic Tac Toa

• Hàm lượng giá heuristic h(n) = X(n) – O(n) với

– X(n) số khả năng thắng của quân X. – O(n) số khả năng thắng của quân O

06/10/2009 Nhập môn Trí tuệ nhân tạo 103

Ví dụ: Bài toán Tic Tac Toa

X có 6 khả năng thắng

E(n) = 6 - 5 = 1

O X

O có 5 khả năng thắng

Với hàm Heuristic trên X sẽ cố làm cho E(n) lớn nhất (MAX) và O làm cho E(n) nhỏ nhất (MIN)

06/10/2009 Nhập môn Trí tuệ nhân tạo 104

Ví dụ: Bài toán Tic Tac Toa

1 MAX

1 -1

-2

X X

MI N

1

2

X X

MAX

X X X

1 X

0 1 X

0 -1

O O

O O O

Nhập môn Trí tuệ nhân tạo 105 06/10/2009

Các đồ án

• Mở rộng bài toán phân công • Thuật giải minmax, alpha – beta: trò chơi đối kháng • Tối ưu hoá hệ luật dẫn • Thuật giải di truyền • Mạng noron • SVM • Mô hình Markov ẩn • Điều khiển mờ, Logic mờ • Data mining • Web Mining • Agent • Các bài toán nhận dạng: âm thanh, hình ảnh • Ontology, xây dựng ontology về 1 lĩnh vực • Xây dựng chương trình giải toán, tra cứu kiến thức 06/10/2009 • ………………..

Nhập môn Trí tuệ nhân tạo 106