Read lecture3 text version

Chng 3: Các k thu t tìm ki m Heuristics

1

N i dung

Khái ni m Tìm ki m t t nh t tr c Phng pháp leo ñ i Cài ñ t hàm ñánh giá Thu gi m ràng bu c Gi i thu t c t t a -

2

Gi i h n c a duy t h th ng

8-puzzle

L i gi i c n trung bình 22 c p (depth) ð r ng c a b c ~ 3 Tìm ki m vét c n cho 22 c p c n 3.1 x 1010 states N u ch gi i h n d=12, c n trung bình 3.6 tri u tr ng thái [24 puzzle có 1024 tr ng thái]

C n chi n l c tìm ki m heuristic

3

Khái ni m: Heuristic

Heuristics: là các ph ng ñoán, c ch ng d a trên kinh nghi m, tr c giác (ki n th c b sung) Các h gi i quy t AI s d ng heuristic trong hai tình hu ng c b n:

Bài toán ñ c ñ nh ngha chính xác nhng chi phí tìm l i gi i vét c n là không th ch p nh n VD: S bùng n không gian tr ng thái (KGTT) trong trò chi c vua V n ñ v i nhi u s m h trong l i phát bi u bài toán hay d li u cng nh tri th c s n có VD: Ch n ñoán trong y h c

4

Khái ni m: Gi i thu t Heuristics

M t gi i thu t heuristic có th ñ c xem g m 2 ph n:

Phép ño heuristic: th hi n qua hàm ñánh giá heuristic (evaluation function f(n) - EF), dùng ñ ñánh giá các ñ c ñi m c a m t tr ng thái trong KGTT Gi i thu t tìm ki m heuristic:

TK t t nh t (best-first search) A* search Gi i thu t leo núi (hill-climbing)

5

Ví d phép ño Heuristics

6

Ví d phép ño Heuristics (tt)

Heuristic "S ñ ng th ng nhi u nh t" (theo các ñ ng chéo trên bàn c ) áp d ng cho các con c ñ u tên ñ t vào bàn c trong bàn c tic-tac-toe

7

Ví d phép ño Heuristics (tt)

8

Gi i thu t leo ñ i (Hill climbing)

Gi i thu t

Xét tr ng thái b t ñ u N u là ñích d ng

Ng c l i: thi t l p kh i ñ u nh TT hi n t i

L p ñ n khi: g p ñích ho c không còn lu t nào cha ñ c áp d ng vào TT hi n t i

L a m t lu t ñ áp d ng vào TT hi n t i ñ sinh ra m t TT m i Xem xét TT m i này N u là ñích d ng N u không là ñích, nhng t t hn TT hi n t i thi t l p TT m i là TT hi n t i N u không t t hn thì l p ti p t c

9

Gi i thu t leo ñ i (tt)

Gi i h n

Gi i thu t có khuynh h ng b sa l y c cb nh ng c c ñ i

L i gi i tìm ñ c không t i u Không tìm ñ c l i gi i m c dù có t n t i l i gi i

Gi i thu t có th g p vòng l p vô h n do không lu gi thông tin v các tr ng thái ñã duy t

10

Gi i thu t leo ñ i (tt)

Bài toán 8 H u

Tr ng thái b t ñ u: m i H u trên 1 c t Tr ng thái ñích: các H u không th t n công nhau Phép ño Heuristic h(n): s l ng các c p h u ñ i kháng nhau

H(n) = 17

h(n) = 1

11

Tìm ki m t t nh t (BFS)

Là phng pháp dung hoà c a BrFS và DFS Có s d ng ñ ñánh giá u th c a m i tr ng thái, có th là c l ng t nó ñ n TT ñích T i m i b c, gi i thu t s ch n tr ng thái mà nó cho r ng là có u th nh t trong s các tr ng thái ñã sinh ra ñ c ñ n th i ñi m ñó Khác v i gi i thu t leo ñ i có c i ti n ch : có lu t t c nh ng TT ñã phát sinh ñ n th i ñi m ch n TT ñ xét ti p Dùng hai danh sách:

OPEN: ch a các TT s ñ c xét. CLOSED: ch a các TT ñã xét qua.

12

Tìm ki m t t nh t (BFS)

Gi i thu t

OPEN = [TT ñ u] L p ñ n khi: g p ñích ho c OPEN r ng

L y TT t t nh t t OPEN Phát sinh các con c a nó V i m i con:

N u nó cha ñ c phát sinh: gán nó tr ñánh giá, ña vào OPEN, ghi nh n TT cha c a nó N u ñã ñ c phát sinh tr c: N u ñ t ñ n b i ñ ng khác t t hn ghi nh n l i TT cha c a nó, c p nh t l i tr ñánh giá c a nó và c a các con c a nó

13

Tìm ki m t t nh t (BFS)

1. 2. 3.

4.

5.

6.

7.

open = [A5]; closed = [ ] ðánh giá A5; open = [B4,C4,D6]; closed = [A5] ðánh giá B4; open = [C4,E5,F5,D6]; closed = [B4,A5] ðánh giá C4; open = [H3,G4,E5,F5,D6]; closed = [C4,B4,A5] ðánh giá H3; open = [O2,P3,G4,E5,F5,D6]; closed = [H3,C4,B4,A5] ðánh giá O2; open = [P3,G4,E5,F5,D6]; closed = [O2,H3,C4,B4,A5] ðánh giá P3; tìm ñ c l i gi i!

Open là queue, x p theo Heuristic tng d n

14

Cài ñ t hàm ñánh giá (EF)

Xét trò chi 8-ô, m i tr ng thái n, m t giá tr f(n):

f(n) = g(n) + h(n)

g(n) = kho ng cách th c s t n ñ n tr ng thái b t ñ u h(n) = hàm heuristic ñánh giá kho ng cách t tr ng thái start n ñ n m c tiêu.

2 1 8 7 6 2 3 4 5 2 1 8 6 7 3 4 5 2 1 7 6 8 3 4 5 2 1 7 8 6 5 3 4 8 6 3 4 5

g(n) = 0

1 7

goal h(n): s l ng các v trí còn sai; g(n) = 1 f(n) =

6

4

6

15

Ví d

16

Ví d ...

17

Ví d ...

18

Heuristic trong trò chi ñ i kháng

Gi i thu t minimax

Hai ñ u th trong trò chi ñ c g i là MIN và MAX. M i nút lá có giá tr :

1 n u là MAX th ng, 0 n u là MIN th ng.

Minimax s truy n các giá tr này lên cao d n trên ñ th , qua các nút cha m k ti p theo các lu t sau:

N u tr ng thái cha m là MAX, gán cho nó giá tr l n nh t có trong các tr ng thái con. N u tr ng thái cha m là MIN, gán cho nó giá tr nh nh t có trong các tr ng thái con.

19

Áp d ng GT Minimax vào Trò Chi NIM

1

MIN MAX MIN

1 1 1

0

1

0

1

MAX

0

1

0

MIN

0

1

K T QU C A MAX

MAX

0 K T QU C A MIN

20

Minimax v i ñ sâu l p c ñ nh

Minimax ñ i v i m t KGTT gi ñ nh

3 là giá tr max c a các nút con

2 là giá tr min c a các nút con

Các nút lá ñ c gán các giá tr heuristic nào ñó Còn giá tr t i các nút trong là các giá tr nh n ñ c d a trên gi i thu t Minimax (min hay max cua các nút con)

21

Heuristic trong trò chi tic-tac-toe

Hàm Heuristic: E(n) = M(n) ­ O(n) Trong ñó: M(n) là t ng s ñ ng th ng có th c a tôi O(n) là t ng s ñ ng th ng có th c a ñ i th E(n) là tr s ñánh giá t ng c ng cho tr ng thái n

22

Minimax 2 l p ñ c áp d ng vào n c ñi m ñ u trong tic-tac-toe

Max (X) có 5 ñ ng th ng, Min(O) có 4, hàm heuristic là -1

23

Thu gi m bài toán

ð th AND-OR :

ð c dùng ñ bi u di n KGTT cho bài toán gi i ñ c b ng cách phân rã ra các bài toán nh hn Khi bài toán ñ c phân rã thành N bài toán con, mà t t c chúng ph i ñ c gi i ñ hoàn thành bài toán l n thì ñ c bi u di n thành cung AND ch ñ n N tr ng thái con Nhi u cách gi i cho bài toán có th ñ c dùng thì có th bi u di n b i cung OR

A có th ñ c thông qua hai cách: - Gi i B, ho c - Gi i c C và D

24

Thu gi m bài toán (tt)

ð th AND-OR :

N u dùng gi i thu t BFS cho vi c tìm l i gi i trên ñ th ANDOR thì có l không thích h p vì nh xem xét ñ th sau:

N u giá tr ghi k bên tr ng thái là tr c l ng cho tr ng thái ñó. Theo BFS thì tr ng thái k ti p ñ c ch n là C, nh:

Khi ch n cách gi i qua C thì b t bu c ph i gi i c D. Do v y t ng chi phí cho cách gi i này là: C+D+ 2 = 9, 2 là giá tr c a hàm g trong BFS Trong khi ñó n u ch n cách gi i qua B thì chi phí ch là: B+1 = 6.

25

Thu gi m bài toán (tt)

GT thu gi m bài toán

Kh i ñ ng ñ th là TT b t ñ u. L p ñ n khi: TT ñ u ñ c gán nhãn là SOLVED ho c chi phí v t qua ng ng FUTILITY:

Duy t ñ th b t ñ u t TT ñ u, theo con ñ ng t t nh t hi n t i, tích lu t p tr ng thái trên con ñ ng ñó mà nó cha ñ c m r ng ho c ñ c gán nhãn SOLVED. L y m t TT cha m r ng và m r ng nó. N u không có con thì gán FUTILITY b ng tr c a TT này. Ng c l i, thêm các con vào ñ th và m i chúng tính f' (s d ng ch h', b qua g). N u f' =0 thì gán nhãn cho TT ñó là SOLVED. Thay ñ i f' c a TT ñã ñ c m r ng ñ ph n ánh thông tin ñ c cung c p b i con c a nó. Lan truy n tr này ng c lên ñ th . N u m t TT có cung mà t t c các con c a nó ñã ñ c gán nhãn SOLVED thì nó cng ñ c gán nhãn SOLVED. Khi lan truy n ng c lên ñ th ñánh d u cung nào là t t nh t nh là ph n c a con ñ ng t t nh t hi n t i.

26

Thu gi m bài toán (tt)

GT Thu gi m (tt.) - t ng b c:

27

Thu gi m bài toán (tt)

GT Thu gi m (tt.) - t ng b c:

28

Gi i thu t c t t a -

Tìm ki m theo ki u depth-first. Nút MAX có 1 giá tr (luôn tng) Nút MIN có 1 giá tr (luôn gi m) Tìm ki m có th k t thúc d i b t k: Nút MIN nào có c a b t k nút cha MAX nào. Nút MAX nào có c a b t k nút cha MIN nào. Gi i thu t c t t a - th hi n m i quan h gi a các nút l p n và n+2, mà t i ñó toàn b cây có g c t i l p n+1 có th c t b .

29

C t t a (v trí MAX)

MAX S

Có giá tr >=

MIN

A Có=giá tr

C

Có giá tr <= k

- cut

Có giá tr = k

MAX

ði ði ði B u ki n 1: Ch c n bi t giá tr t i A và B u ki n 2: Giá tr A > giá tr B u ki n 3: X, Y, .. , Z v trí Max nh ng cây con có g c là X,Y,..., Z

B

X

Y ....

Z

30

C t t a (v trí Min)

MIN S

Có giá tr <=

MAX

A

Có giá tr =

C

Có giá tr >= k

- cut MIN

ði ði ði B

B

Có giá tr = k

X

Y ....

Z

u ki n 1: Ch c n bi t giá tr t i A và B u ki n 2: Giá tr A < giá tr B u ki n 3: X, Y, .. , Z v trí Min nh ng cây con có g c là X,Y,..., Z

31

C t t a -: ví d

32

Bài t p: bài 1 (trò ñ 8 ô nh)

Start 1 2 3 6 7 8 5 4 Goal 1 2 3 8 4 7 6 5

Dùng các hàm l ng giá heuristic sau h1 = s l ng các v trí sai khác so v i tr ng thái goal. h2 = t ng s ñ d i ng n nh t c a các ô v v trí ñúng (kho ng cách Manhattan) Hãy tri n khai không gian tr ng thái c a bài toán ñ n m c 5 (n u cha tìm ñ c goal): a) Theo gi i thu t leo núi b) Theo gi i thu t tìm ki m r ng c) Theo gi i thu t tìm ki m sâu d) Theo gi i thu t tìm ki m t t nh t ñ u tiên

33

Bài t p: bài 2 (duy t ñ th )

Trong cây tìm ki m d i ñây, m i nút có 2 giá tr ñi kèm: giá tr bên trái c a nút (in nghiêng) th hi n giá tr heuristic c a nút, và giá tr bên ph i nút th hi n th t nút ñ c duy t qua. V i m i chi n l c tìm ki m d i ñây, hãy vi t danh sách th t các nút ñ c duy t, so sánh và cho bi t ta ñã dùng gi i thu t tìm ki m nào trên cây :

a) Tìm ki b) Tìm ki c) Tìm ki d) Tìm ki

m r ng BFS m sâu DFS m t t nh t ñ u tiên BFS m leo núi

34

Bài t p: bài 3 (minimax)

Li t kê danh sách các nút ñ c duy t theo tìm ki m DFS. Th c hi n gi i thu t Minimax trên cây.

S có gì khác bi t n u nh ta dùng gi i thu t c t t a alpha ­ beta ñ ñ nh tr nút g c cho cây?

35

Information

lecture3

35 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

276295