Thuật giải AT, AKT

Thuật giải AT, AKT

Thuật giải AT (Algorithm for Tree): Mỗi đỉnh n tương ứng với một số g(n): giá thành

của đường đi từ đỉnh ban đầu đến đỉnh n.

Đỉnh: + Đỉnh đóng (Closed) : là những đỉnh đã được

xem xét.

+Đỉnh mở (Open)

: là những đỉnh giả thiết

sẽ được xem xét ở bước sau.

+ Đỉnh ẩn (Hiden)

: là những đỉnh mà tại

đó hàm g(n) chưa được xác định.

Thuật giải AT

Bước 1: + Mọi đỉnh n, mọi giá trị g(n) đều là ẩn. + Mở đỉnh đầu tiên và gọi đó là đỉnh S. Đặt g(S) = 0. Bước 2 : Chọn đỉnh mở với giá thành g tương ứng là nhỏ nhất và gọi đó là đỉnh N. + Nếu N là mục tiêu: đường đi từ đỉnh ban đầu đến N là đường đi ngắn nhất và bằng

g(N). Dừng (Success).

+ Nếu không tồn tại một đỉnh mở nào nữa: cây biểu diễn vấn đề không có đường đi tới

mục tiêu. Dừng (Fail).

+ Nếu tồn tại nhiều hơn 1 đỉnh N (nghĩa là có 2 đỉnh N trở lên) mà có cùng giá thành

g(N) nhỏ nhất. Kiểm tra xem trong số đó có đỉnh nào là đích hay không. Nếu có: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn nhất và bằng g(N), dừng

(Success).

Nếu không có: Chọn ngẫu nhiên một trong các đỉnh đó và gọi là đỉnh N. Bước 3: Đóng đỉnh N và mở các đỉnh sau N (là những đỉnh có cung hướng từ N tới). Tại

mọi đỉnh S sau N tính :

g(S) = g(N) + cost(Nfi S)  Bước 4: Quay lại bước 2

Thuật giải AT­ Ví dụ

1 0 0

1

1 7

1

D

B

C

A

1

1 0

2 0

1 2

1

1

G

H

I

J

E

F

1

1

1

1

N

K

L

M

1

1

P

O

1

1

R

Q

1

1

T

S

1

T r a ïn g t h a ùi ñ í c h

U

1

V

Thuật giải AT­ Ví dụ

1 0 0

1

1 7

1

D

B

C

A

1

1 0

2 0

1 2

1

1

G

I

H

J

E

F

1

1

1

1

N

K

L

M

1

1

P

O

1

1

R

Q

1

1

S

T

1

T r a ïn g t h a ùi ñ í c h

U

1

V

Mọi đỉnh n, g(n) chưa biết.  B1: Mở S, đặt g(S) = 0. B2: Đóng S; mở A, B, C, D g(A) = g(S) + gt(Sfi A) = 0 + 100 = 100 g(B) = 0 + 17 = 17 g(C) = g(D) = 0 + 1 = 1 (min) Chọn ngẫu nhiên giữa C, D: chọn C B3: Đóng C, mở G, H: g(A) = 100 g(B) = 17 g(D) = 1 (min) g(G) = 11 g(H) = 21

Thuật giải AT­ Ví dụ

1 0 0

1

1 7

1

D

B

C

A

1

1 0

2 0

1 2

1

1

G

I

H

J

E

F

1

1

1

1

K

N

L

M

1

1

O

P

1

1

Q

R

1

1

S

T

1

T r a ïn g th a ùi ñ í c h

U

B4: Đóng D, mở I, J: g(A) = 100 g(B) = 17 g(I) = 13 g(J) = 2 (min) g(G) = 11 g(H) = 21 B5: Đóng J, mở N: g(A) = 100 g(B) = 17 g(I) = 13 g(G) = 11 g(H) = 21 g(N) = 3 (min)

1

V

Thuật giải AT­ Ví dụ

1

1 0 0

1 7

1

D

B

C

A

1

1 0

1 2

2 0

1

1

J

I

H

G

E

F

1

1

1

1

K

N

M

L

1

1

O

P

1

1

Q

R

1

1

S

T

1

T r a ïn g t h a ùi ñ í c h

U

1

V

1

1

1

1

1

D

N

S

P

J

(cid:190) fi (cid:190) (cid:190) fi (cid:190) (cid:190) fi (cid:190) (cid:190) fi (cid:190) (cid:190) fi (cid:190)

B6: Đóng N, mở P: g(A) = 100 g(B) = 17 g(I) = 13 g(G) = 11 g(H) = 21 g(P) = 4 (min) B7: Đóng P, mở R: g(A) = 100 g(B) = 17 g(I) = 13 g(G) = 11 g(H) = 21 g(R) = 5 (min) R R là đích. Vậy đường đi là: Nhận xét: Thuật toán này chỉ sử dụng 3 thông tin: đỉnh, cung và giá thành của cung.

Thuật giải AKT – Tìm kiếm với tri thức bổ  sung (Algorithm for Knowledgeable Tree Search):

 Thu t gi

i A

ng đi t

ậ

ậ

ả

ế

ố

ấ ố ớ ề

ườ

ườ ị ủ c đ nh h ị

ẽ ượ

ử ụ

ế

ệ

ả T là thu t gi ề ỉ ườ c d a trên các hi u bi

t nh t đ i v i cây ch có ỉ ng h p ợ ng rõ thêm n u s d ng các ấ

ướ t v tình hu ng v n đ ố ế ề

ng đi s đ ự

m i ề ở ỗ

ể

i tìm ki m đ các thông tin v đ nh, cung và giá tr c a cung. Trong nhi u tr vi c tìm ki m đ ế tri th c thu đ ượ b

m i đ nh đ

ổ

ẳ

ộ

ị

ví d c a

ng ng v i m t giá tr h(n). Ch ng ớ ứ n đ n m c tiêu. ng đi t ụ

ụ ủ

Ở

ừ

ế

c t ượ ươ ng giá thành đ ườ c đ u tiên :

ứ c.ướ Tri th c b sung ứ h n đó là ạ gi ả

ở ỗ ỉ c l ướ ượ b i thu t AT, ở ướ ậ

ầ

ể

ế

ộ

ọ

ỉ

ư ỉ

ầ

c:

g(c) = g(d) = 1  AT ch n tùy ý m t trong hai đ nh c và d đ xét ti p. Nh ng thay vì ch n ọ tùy ý chúng ta có th đ t câu h i “Đ nh nào trong các đ nh c và d g n ỉ ể ặ m c tiêu h n”, chúng ta ng đ ơ

ỏ c l ướ ượ

ượ

ụ

ế ế

ứ

ọ

ỉ

h(c) = 11 h(d) = 4 thì vi c ch n đ nh k ti p s là d ch không ph i c. Do v y tri th c b sung s d a trên c s c c ti u hóa giá thành f

ẽ ẽ ự

ơ ở ự

ả ể

ứ

ổ

m i ở ỗ

b

ệ ậ ướ

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

Thuật giải AKT

t.

ế

ư

ư

ầ

c tính hàm h(S)

ỉ

ọ

ỏ

đ nh ban đ u đ n đ nh N là ng n nh t và và b ng g(N). D ng ắ

ừ

ế

ỉ

ấ ầ

ướ : Ch n đ nh m có f là nh nh t và g i là đ nh N ừ ỉ ế

ằ

ấ

ng đi t

i m c tiêu.

i đ nh m nào: cây bi u di n v n đ không t n t

ớ

ụ

ế

ồ ạ ỉ

i đ ồ ạ ườ

ề

ễ

ể

ấ

ở

ừ

N u có 2 đ nh m tr lên có cùng giá tr f nh nh t: Chúng ta ph i ki m tra xem nh ng đ nh

ở ở

ể

ế

ấ

ả

ỏ

ị

ữ

ỉ

đ nh ban đ u đ n đ nh N là ng n nh t và b ng g(N). D ng (Success).

ừ ỉ

ằ

ắ

ấ

ầ

ỉ

ừ

ng đi t ọ

ọ ỉ

ẫ

ỉ

ỗ ỉ

ớ

ể

c 2.

ứ ổ i b ạ ướ

ướ : B c 1 M i đ nh, cũng nh các hàm g, h, f ch a bi ọ ỉ M đ nh đ u tiên S, gán g(S) = 0 ở ỉ S d ng tri th c b sung đ ể ướ ứ ổ ử ụ Tính f(S) = g(S) + h(S) B c 2 ở ỉ ọ N u N là đích: đ ng đi t ườ (Success). N u không t n t D ng (Fail). ỉ đó có đ nh nào là đích hay không. ỉ + N u có: đ ế ế ườ + N u không có: ch n ng u nhiên m t trong các đ nh đó và g i đ nh đó là N. ộ ế ướ : B c 3 Đóng đ nh N, m m i đ nh sau N. V i m i đ nh S sau N, tính: ở ọ ỉ ỉ g(S) = g(N) + cost(Sfi N) S d ng tri th c b sung đ tính h(S) và f(S): f(S) = g(S) + h(S) ử ụ ướ : Quay l B c 4

Bài toán Tháp Hà Nội với n = 2

S 0

S n

Các tr

ườ

ng h p c a bài toán là v i tr ng thái c t th ba ứ :

ợ ủ

ớ ạ

ộ

0

1

2

3

h ( n ) =

g = 0 h = 2 f = 2

g = 1 h = 2 f = 3 ( m i n )

g = 1 h = 3 f = 4

g = 2 h = 3 f = 5

g = 2 h = 2 f = 4

g = 2 h = 1 f = 3 ( m i n )

g = 3 h = 1 f = 4

g = 3 h = 2 f = 5

g = 3 h = 0 f = 3 ( Ñ í c h )

Bài toán taci

3

1

2

3

2

8

4

8

4

1

6

7

6

7

5

5

S 0

S n

Cách 1:

t

=

b

i

=

(cid:236)

= (cid:229)

H

)b,a( vôùi i i

)b,a( i i

d d (cid:237)

b

= 1i

i

0 a neáu i 1 a neáu i

„ (cid:238)

2

8

3

1

6

4

g = 0 h = 4 ( c o ù 4 s o á s a i v ò tr í s o v ô ùi G o a l ) f = 4

7

5

2

8

3

2

8

3

3

2

8

1

6

4

1

4

4

1

6

g = 1 h = 5 f = 6

g = 1 h = 3 f = 4 ( m i n )

g = 1 h = 5 f = 6

7

5

7

6

5

7

5

8

3

3

3

8

2

2

2

1

4

1

8

4

1

4

g = 2 h = 3 f = 5

g = 2 h = 3 f = 5 ( m i n )

g = 2 h = 4 f = 6

7

6

5

7

6

5

5

7

6

3

3

2

2

8

4

1

1

8

4

g = 3 h = 4 f = 7

g = 3 h = 2 f = 5 ( m i n )

6

5

7

7

6

5

2

3

1

1

2

3

8

4

8

4

g = 5 h = 0 f = 5 ( Ñ í c h )

g = 4 h = 1 f = 5 ( m i n )

6

5

7

7

6

5

Bài toán taci

t

Cách 2:

=

H

)b,a( i

i

= 1

i

ả ẩ

ề

ọ

v i ớ h (ai,bi) là s l n ít nh t ph i đ y ô a

i = a theo chi u d c

hay ngang v đúng v trí b ề

ố ầ ị

ấ i = b.

Gi

s : ả ử

8

2

3

Coäng

1

2

3

4

5

6

7

8

Soá

6

1

4

Vò trí

1

1

0

0

0

1

2

5

0

7

5

h (cid:229)

Bài toán taci (tt)

The algorithm tries to reach a state in G from SI as  follows. 1. OPEN := {SI}, CLOSED := ;. 2. If some state in G is in OPEN, then stop: solution  found. 3. If OPEN = ;, then stop: no solution. 4. Choose an element S 2 OPEN with the least  f(S). 5. OPEN := OPEN\{S}, CLOSED := CLOSED[{S}. 6. OPEN := OPEN [ neighbors/successors of S not  in OPEN nor in CLOSED. 7. Go to 2.

Thuật giải A* ­ tìm kiếm đường  đi trên đồ thị tổng quát

Mở rộng thuật giải AKT thành thuật giải A* như sau:

Bước 1: Mở đỉnh đầu tiên:

{Trang thái ban đầu}

= 0; = g(S0)+ h(S0)

; {Gán S0 cho tập đỉnh mở} {Gán tập đóng C bằng rỗng}

{} do

S0 = E; g(S0) f(S0) q = {S0}; C={}; while q  „ Bước 2: Chọn một S trong q  với f(S) nhỏ nhất:

{Đóng đỉnh S}

q  = q  ­ {S} C = C + {S} Nếu S là đích thì dừng. Ngược lại qua bước 3.

Thuật giải A* ­ tìm kiếm đường đi  trên đồ thị tổng quát (tt)

lẫn

Bước  3:  Xây  dựng  các  đỉnh  Si  có  thể  đến  từ  S  nhờ  các  hành động có thể chọn để thực hiện." Si sau S: •Tính g(Si) ứng với mỗi i: g(Si) = g(S) + cost(S­>Si). •Ước lượng h(Si)  •Gán f(Si)=g(Si)+h(Si)  những  Si  không  có  trong  q Bước  4:  Đặt  vào  trong  q trong C. Với các Si đã có trong q  hoặc trong C thì gán:

f(Si) = Min( fcũ(Si), fmới(Si) ). If Si có trong C and fcũ(Si)< fmới(Si) then

C := C – {Si} q  := q  + {Si}

End A*

{Mở Si}

Thuật giải A* ­ tìm kiếm đường đi  trên đồ thị tổng quát (tt)

Thuật giải này được diễn giải như sau : Bước 1: Mọi đỉnh và

Mọi đỉnh, cũng như các hàng g, h, f chưa biết. Mở đỉnh đầu tiên S, gán g(S) = 0 Ước lượng hàm h(S) Gán f(S) = h(S)+ g(S)

Bước 2: Chọn đỉnh mở có f(S) là nhỏ nhất và gọi là đỉnh N •Nếu  N  là  đích:  đường  đi  từ  đỉnh  ban  đầu  đến  đỉnh  N  là  ngắn  nhất và và bằng g(N). Dừng (Success). •Nếu không tồn tại đỉnh mở nào: cây biểu diễn vấn đề không tồn  tại đường đi tới mục tiêu. Dừng (Fail). •Nếu có 2 đỉnh mở trở lên có cùng giá trị f(S) nhỏ nhất: ta phải  kiểm tra xem những đỉnh đó có đỉnh nào là đích hay không.

Thuật giải A* ­ tìm kiếm đường đi  trên đồ thị tổng quát (tt)

g’(S) thì bỏ qua S

+ Nếu có: đường đi từ đỉnh ban đầu đến đỉnh N là ngắn  nhất và bằng g(N). Dừng (Success). + Nếu không có: chọn ngẫu nhiên một trong các đỉnh  đó và gọi đỉnh đó là N. Bước 3: Đóng đỉnh N, và đối với mỗi đỉnh S sau N, chúng ta   tính: g’(S) = g(N) + cost(Sfi N) Nếu đỉnh S đã mở và g(S)£ Ngược lại mở S và đặt g(S) = g’(S), tính h(S) và f(S):  f(S) = g(S) + h(S) Bước 4: Quay lại bước 2.

Bản đồ của Romania với  khoảng cách tính theo km

Khoảng cách đường chim bay từ  một thành phố đến Bucharest.

Ví dụ 1

Ban đầu (bước 1) :

OPEN = {(Arad,g= 0,h’= 0,f’= 0)}

CLOSE = {} Do trong OPEN chỉ chứa một thành phố duy nhất nên thành phố

này sẽ là thành phố tốt nhất. Nghĩa là S0 = Arad.Ta lấy Arad ra  khỏi OPEN và đưa vào CLOSE(bước 2).

OPEN = {}      CLOSE = {(Arad,g= 0,h’= 0,f’= 0)}

Từ Arad có thể đi đến được 3 thành phố là Sibiu, Timisoara và

Zerind. Ta lần lượt tính giá trị f’, g và h’ của 3 thành phố này  (bước 3).

Ví dụ 1(tt)

h’(Sibiu) = 253 g(Sibiu) = g(Arad)+cost(Arad,Sibiu) = 0+140= 140 f’(Sibiu) = g(Sibiu)+h’(Sibiu) = 140+253 = 393

h’(Timisoara) = 329 g(Timisoara) = g(Arad)+cost(Arad, Timisoara) = 0+118= 118 f’(Timisoara) = g(Timisoara)+ h’(Timisoara) = 118+329 = 447

h’(Zerind) = 374 g(Zerind) = g(Arad)+cost(Arad, Zerind) = 0+75= 75 f’(Zerind) = g(Zerind)+h’(Zerind) = 75+374 = 449

Do cả 3 nút Sibiu, Timisoara, Zerind đều không có trong cả OPEN và  CLOSE nên ta bổ sung 3 nút này vào OPEN (bước 4).

OPEN = {

(Sibiu,g= 140,h’= 253,f’= 393) (Timisoara,g= 118,h’= 329,f’= 447) (Zerind,g= 75,h’= 374,f’= 449)}

CLOSE = {(Arad,g= 0,h’= 0,f’= 0)}

Ví dụ 1(tt)

Trong tập OPEN, nút Sibiu là nút có giá trị f’ nhỏ nhất nên  ta sẽ chọn Si = Sibiu. Ta lấy Sibiu ra khỏi OPEN và đưa vào  CLOSE.

OPEN = {(Timisoara,g= 118,h’= 329,f’= 447)

(Zerind,g= 75,h’= 374,f’= 449)}

CLOSE = {(Arad,g= 0,h’= 0,f’= 0)

(Sibiu,g= 140,h’= 253,f’= 393)} Từ Sibiu có thể đi đến được 4 thành phố là : Arad, Fagaras,  Oradea, Rimnicu. Ta lần lượt tính các giá trị g, h’, f’ cho các  nút này.

h’(Arad) = 366 g(Arad) = g(Sibiu)+cost(Sibiu,Arad)= 140+140= 280 f’(Arad) = g(Arad)+h’(Arad)= 280+366 = 646

Ví dụ 1(tt)

h’(Fagaras) = 178

g(Fagaras) = g(Sibiu)+cost(Sibiu, Fagaras) = 140+99= 239 f’(Fagaras) = g(Fagaras)+ h’(Fagaras) = 239+178= 417

h’(Oradea) = 380 g(Oradea) = g(Sibiu)+cost(Sibiu, Oradea) = 140+151 = 291 f’(Oradea) = g(Oradea)+ h’(Oradea) = 291+380 = 671

h’(R.Vilcea) = 193 g(R.Vilcea) = g(Sibiu)+cost(Sibiu, R.Vilcea) = 140+80 = 220 f’(R.Vilcea) = g(R.Vilcea)+ h’(R.Vilcea) = 220+193 = 413

Nút Arad đã có trong CLOSE. Tuy nhiên, do g(Arad) mới được tạo ra  (có giá trị 280) lớn hơn g(Arad) lưu trong CLOSE (có giá trị 0) nên ta sẽ  không cập nhật lại giá trị g và f’ của Arad lưu trong CLOSE. 3 nút còn  lại : Fagaras, Oradea, Rimnicu đều không có trong cả OPEN và  CLOSE nên ta sẽ đưa 3 nút này vào OPEN, đặt cha của chúng là  Sibiu. Như vậy, đến bước này OPEN đã chứa tổng cộng 5 thành phố.

Minh hoạ GT A*

Minh hoạ GT A*

Minh hoạ GT A*

Minh hoạ GT A*

Minh hoạ GT A*

Minh hoạ GT A*

Gọi n là tổng số đĩa cần chuyển.

m là số đĩa đã nằm đúng vị trí ở cột thứ 3. k là số đĩa nằm sai vị trí ở cột thứ 3.

Có thể thấy bạn cần chuyển các đĩa nằm  sai vị trí ra khỏi cột 3 (k đĩa), sau đó chuyển  các đĩa chưa đúng vị trí vào đúng vị trí của nó  (n­m­k đĩa), cuối cùng chuyển k đĩa sai vị trí  vào lại. Như vậy bạn sẽ có công thức là:

k + (n­m­k) + k = n­m+k.

VI DU 2 ­ THAP HA NO N=3

G=0

H=3

F=3

G=1

G=1

H=4

H=3

F=5

F=4

G=2

H=3

H=4

H=4

H=3

H=4

H=3

F=5

F=6

F=6

F=5

F=6

F=5

VI DU VE GT A* ­ THAP HA NOI N=3

G=3

H=3

H=3

F=6

F=6

H=5

H=3

H=3

H=6

H=2

H=3

F=9

F=7

F=7

F=10

F=6

F=7

H=3

H=4

H=2

F=8

F=9

F=7

Nhận xét

AT AKT A*

đỉnh đỉnh đỉnh

Cung Cung Cung

Giá thành cung Giá thành cung Giá thành cung

Tri thức bổ sung Tri thức bổ sung

Thao tác trên cây Thao tác trên cây Thao tác trên đồ thị

h(S) với 0 £ a £ 1

fi

fi

fi AT (không có tri thức bổ sung)  AKT (Phụ thuợc vào tri thức bổ sung)  A* Mối quan hệ giữa AT, AKT, A*: f(S) = (1 ­ a ) g(S) + a ­ Nếu a  = 0 ­ Nếu a  = 1 ­ Nếu a  = ½

Thuật giải GTS  (Greedy­Traveling Saleman)

GTS1: Xây dựng một lịch trình du lịch có chi phí Cost tối  thiểu cho bài toán trong trường hợp phải qua n thành phố  với ma trận chi phí C và bắt đầu tại một đỉnh U nào đó.

Thuật giải: Bước 1: {Khởi đầu} Đặt Tour := {}; Cost := 0; V := U; {V là đỉnh hiện tại đang làm việc}

Bước 2: {Thăm tất cả các thành phố}

For  k := 1 To n Do  qua bước 3;

Thuật giải GTS  (Greedy­Traveling Saleman)

Bước 3: {Chọn cung kế tiếp}

Đặt (V, W) là cung có chi phí nhỏ nhất tình từ  V đến các đỉnh W chưa dùng: Tour := Tour + {(V,W)}; Cost := Cost + Cost(V,W); Nhãn W được sử dụng Đặt V := W; {Gán để xét bước kế tiếp}

Bước 4: {Chuyến đi hoàn thành} Đặt Tour := Tour + {(V,U)}; Cost := Cost + Cost(V,U); Dừng.

A

5

1

1

2 4

7 4

5 3

1

E

¥ ø Ø œ Œ ¥ œ Œ

Ví dụ

=

C

1

3

B

7

4 4

1

2 3

2 7

2

2

3

2

3

5

3

4

4

1

D

C

¥ œ Œ œ Œ ¥ œ Œ œ Œ ¥ ß º

= A

˛ {B, C, D, E} {Các đỉnh có thể đến từ A} U =  A Tour = {} Cost = 0 V W

fi {Vì qua B có giá thành bé nhất} W = B

˛ Tour = {(A, B)} Cost = 1 V = B W {C, D, E}

fi W = E

= E

˛ Tour = {(A, B),(B, E)} Cost = 1 + 3 = 4 V W {C, D}

A

5

1

E

Ví dụ

3

B

7

2

2

3

4

4

1

D

fi W = C

C

˛ Tour = {(A, B), (B, E), (E, C)} Cost = 4 + 2 = 6 V = C W {D}

fi W = D

= D

Tour du lịch  A fi A với giá thành Cost = C fi D fi E fi B fi

A với C fi D fi B fi E fi

Tour = {(A, B), (B, E), (E, C), (C, D)} Cost = 6 + 1 = 7 V Tour = {(A, B), (B, E), (E, C), (C, D), (D, A)} Cost = 7 + 7 = 14 Kết quả: 14. Nhận xét: Tuy nhiên kết quả nhỏ nhất sẽ là A fi Cost=13. Sở dĩ không tối ưu do “háu ăn”: cứ hướng nào có chi phí thấp thì  đi, bất chấp về sau.

GTS2

GTS2: Tạo ra lịch trình từ p thành phố xuất phát riêng biệt. Tìm chu trình của  người bán hàng qua n thành phố (1

k := 0; {Đếm số thành phố đi qua} Best := {}; {Ghi nhớ chu trình tốt nhất tìm thấy có chi phí là Cost} Cost := ¥

;

Bước 2: {Bắt đầu chu trình mới}

Chuyển qua bước 3 khi k

Bước 3: {Tạo chu trình mới}

k := k + 1; Call (GTS1(Vk)) : Trả về một chu trình T(k) ứng với chi phí C(k).

Bước 4: {Cập nhật chu trình tốt nhất}

Nếu C(k)< Cost thì Best := T(k); Cost := C(k);

A

5

1

E

3

B

7

2

GTS2 (tt)

2

3

4

4

1

D

C

Ví dụ:(Giải lại ví dụ trên) p=3 K=0 Best={} Cost=∞ K=0T(0)={(A,B),(B,E),(E,C),(C,D),(D,A)},

C(0)=14

C(0)=14Best=T(0) Cost=14 K=1T(1)={(B,A),(A,C),(C,D),(D,E),(E,B)},

C(1)=10

C(1)=10Best=T(1) Cost=10 K=2T(2)={(C,D),(D,E),(E,B),(B,A),(A,C)},

C(2)=10 C(2)=10>=Cost

K=3>=p Dừng.

Vậy nếu nhập p=3 chu trình thì chúng ta bắt đầu từ thành phố B và  có Cost nhỏ nhất. Nếu ta chọn p khác thì ta sẽ có kết quả khác có  thể tốt hơn kết quả trên. Ví dụ p= 4 các bạn gỉai thử xem.

Thuật toán tô màu tối ưu trên đồ thị

Giả thiết 4 màu: Chúng ta nói 2 nước trên bản

đồ vẽ trên mặt cầu hoặc là mặt phẳng là láng  giềng của nhau nếu như chúng có chung  đường biên giới (chỉ xét những nước có đường  biên giới là một đường cong khép kín).

 Yêu cầu: tô toàn bộ bản đồ mà chỉ sử dụng 4  màu sao cho không có bất kỳ 2 nước láng  giềng nào có cùng chung một màu

Đ nhỉ

Lisbon L

Madrid M

Paris P

Berne Be

Rome R

Viene V

Berlin Ber

Luxemburg Lx

Brusen Bru

Hague H

1

2

6

4

3

3

6

3

4

2

B cậ

L i s b o n

3

1

B r u s e l s

P a r i s

L u x e m b u r g

1

4

T h e H a g u e

4

4

M a d r i d

B e r n e

3

2

2 B e r l i n

R o m e

1

V i e n e

Thuật toán: Lặp lại các bước sau cho đến khi nào tô màu  hết các đỉnh Bước 1: Chọn đỉnh có bậc lớn nhất tô màu i. Bước 2: Hạ bậc: ­ Đỉnh đã tô màu: bậc = 0 ­ Những đỉnh có liên hệ: bậc := bậc – 1 Bước 3: Đánh dấu các đỉnh liên hệ (bậc vừa trừ đi 1) cấm  tô màu i.

Màu c m tô ấ

3

2

2

2

3

3

1

1

1

1

1

1

2

2

L

M

P

Be

R

V

Ber

Lx

Bru

H

Đ nhỉ

Màu tô

1

2

1

3

2

2

1

4

3

1

1

2

6*

4

3

6

3

3

4

2

B cậ

1

1

0

3

2

5*

3

2

3

2

H b c l n 1 ạ ậ ầ

1

1

2

2*

0

2

1

2

1

H b c l n 2 ạ ậ ầ

1

1

1

1

1

2*

1

H b c l n 3 ạ ậ ầ

0

1*

1

1

1

0

0

0

H b c l n 4 ạ ậ ầ

0

1*

1

0

0

H b c l n 5 ạ ậ ầ

0

0

0

0

0

H b c l n 6 ạ ậ ầ

Ví dụ 2: Phân công, lịch công tác, lịch thi  đấu:

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

đề khác nhau, mỗi chủ đề diễn ra trong  một buổi.

•Các chủ đề sau không được đồng thời:  AE, BC, CD, ED, ABD, AHI, BHI, DFI, DHI,  FGH.

•Xây dựng lịch sao cho số buổi diễn ra là

ít nhất.

•Gợi ý: số màu = số buổi.

B

A

C

I

D

H

E

G

F

4

3 3

2 2 4 3 2 3 2

1 Màu cấm 1 1 1 1 1 2 1

A tô Đỉnh B C D H E F G I

3 Màu tô 4 2 1 2 2 3 1 5

5 Bậc 5 2 7* 6 2 4 2 5

4 Hạ bậc 4 1 0 5* 1 3 2 4

3* 3 1 0 1 2 1 3

0 2* 1 0 2 1 2

0 0 2* 1 1

0 0 0

Kết luận:  Buổi 1: G, D  Buổi 2: C, E, H  Buổi 3:  A, F  Buổi 4: B  Buổi 5: I

Tìm kiếm leo đồi

1. Leo đồi đơn giản 2. Leo đồi dốc đứng 3. Đánh giá

1. Leo đồi đơn giản

a. Định nghĩa:

b.

Tìm kiếm leo đồi là một trường hợp đặc  biệt của tìm kiếm theo chiều sâu nhưng  không thể quay lui. Trong tìm kiếm leo đồi,  việc lựa chọn trạng thái tiếp theo được quyết  định dựa trên một hàm Heuristic.  Hàm heuristic là gì ? là ước lượng về khả năng dẫn đến lời giải  . Ký hiệu là h

1. Leo đồi đơn giản (tt)

Tư tưởng

c. 1) Nếu trạng thái bắt đầu (T0) là trạng thái đích: thoát và

báo là đã tìm được lời giải.

Ngược lại, đặt trạng thái hiện hành (Ti) là trạng thái khởi

đầu (T0)

2) Lặp lại cho đến khi đạt đến trạng thái kết thúc hoặc cho

đến khi không tồn tại một trạng thái tiếp theo hợp lệ  (Tk) của trạng thái hiện hành :  a. Đặt Tk là một trạng thái tiếp theo hợp lệ của trạng thái hiện

hành Ti.

b.1. Nếu là trạng thái kết thúc thì trả về trị này và thoát.  b.2. Nếu không phải là trạng thái kết thúc nhưng tốt hơn trạng thái

hiện hành thì cập nhật nó thành trạng thái hiện hành.

b.3. Nếu nó không tốt hơn trạng thái hiện hành thì tiếp tục vòng lặp.

b. Đánh giá trạng thái Tk mới :

2. Leo đồi dốc đứng

a. Định nghĩa:

Giống như leo đồi đơn giản, chỉ khác ở  điểm là leo đồi dốc đứng sẽ duyệt tất  cả các hướng đi có thể và chọn đi theo  trạng thái tốt nhất trong số các trạng  thái kế tiếp có thể có (trong khi đó leo  đồi đơn giản chỉ chọn đi theo trạng  thái kế tiếp đầu tiên tốt hơn trạng thái  hiện hành mà nó tìm thấy).

2. Leo đồi dốc đứng (tt)

b. Tư tưởng 1) Nếu trạng thái bắt đầu cũng là trạng thái đích  thì thoát và báo là đã tìm được lời giải.

Ngược lại, đặt trạng thái hiện hành (Ti) là trạng

thái khởi đầu (T0)

2) Lặp lại cho đến khi đạt đến trạng thái kết thúc  hoặc cho đến khi (Ti) không tồn tại một trạng  thái kế tiếp (Tk) nào tốt hơn trạng thái hiện tại  (Ti) a) Đặt S bằng tập tất cả trạng thái kế tiếp có thể có

của Ti và tốt hơn Ti.

b) Xác định Tkmax là trạng thái tốt nhất trong tập S Đặt Ti  = Tkmax

Ví dụ

 Bước 1: n:=Startnode;  Bước 2: Nếu n là đích thì dừng (Success).  Bước 3: Triển khai n, Tính hàm h với ni là con  của n. Chọn ni tương ứng với h nhỏ nhất và  gọi là nextn.

 Bước 4: Nếu không có ni thì thoát (Fail).  Bước 5: n:=nextn;  Bước 6: Nhảy sang bước 2.

H(n)=‰ Tọa độ x của đích  – Tọa độ x của n‰ + ‰ Tọa độ y của đích  – Tọa độ y của n‰ n:=S

h(S)=|4­1|+|4­1|=6 (min) h(A)=|4­2|+|4­3|=3 (min) 

NextS = A n:=A

h(B)=|4­2|+|4­4|=2 (min)   h(C)=|4­2|+|4­2|=4  h(B)

h(E)=|4­3|+|4­4|=1 (min) < h(B)

NextA = B n:=B   NextB = E n:=E

h(G)=|4­4|+|4­4|=0 (min)   h(H)=|4­3|+|4­3|=2 h(G)

NextE = G (Đích­ Dừng)

3. Đánh giá

Một trường hợp thất bại của leo đèo kết hợp quay lui

Thủ tục Min­Max:

Áp dụng trong các trò chơi đối kháng 2 phía.

Để ước lượng nước đi tốt dựa trên hàm ước  lượng, chúng ta dùng thủ tục Min­Max như sau:

Giả sử một trong hai người chơi:

•Gọi một người là Max: tìm cách làm cực đại hàm  ước lượng qua việc xác định giá trị hàm ước lượng  ở mỗi nước đi có khả năng rồi chọn nước đi tương  ứng với giá trị lớn nhất. •Nhưng khi đó đối thủ của Max là Min thì lại tìm  cách làm cực tiểu giá trị hàm ước lượng này.

Như vậy ở mỗi mức của cây biểu diễn trò chơi: Nếu 1 đỉnh tương ứng với 1 nước đi của Max thì  giá trị của đỉnh này sẽ lấy giá trị cực đại của  các đỉnh tiếp sau đó. Nếu 1 đỉnh tương ứng với 1 nước đi của Min thì  giá trị của đỉnh này sẽ lấy giá trị cực tiểu của  các đỉnh tiếp sau đó.

 Ví dụ: Trò chơi Tic­Tac­Toe:

 Max = X (đi trước)  Min = O  Nguyên tắc: Nếu có 3 con thẳng hàng thì thắng.  Hàm ước lượng:

 f(x) = (Số dòng, số cột, số đường chéo còn  mở đối với Max)­(Số dòng, số cột, số đường  chéo còn mở đối với Min)

1

2

3

7

8

4

5

6

1

X

2

X

Ví dụ: Bài toán 8 hậu: + Cho 3 quân hậu đặt

3

X

A

B

C

4

trước vào bàn cờ A0  {(1,4), (2,2), (3,8)}

5

6

7

8

+ Hãy đặt tiếp 5 quân  hậu khác sao cho  các  con hậu không ăn nhau:

int  KTraXH(int A[][N], int x, int n) {

int i, j, kq = 0; for(I = 0; I < n; i++)

for(j = 0; j

if(A[i][j] == x) kq++;

return kq;

} void  Solve(int A[][N], int n) {

while(!KTraMT(A,n)) {

TimBuocDi(A,n); Xuat(A,n);

}

}

int  KTraMT(int A[][N], int x, int n) {

int kq = 1; if(A[0][0] != 1) kq = 0; if(A[0][1] != 2) kq = 0; if(A[0][2] != 3) kq = 0; if(A[1][0] != 8) kq = 0; if(A[1][1] != 0) kq = 0; if(A[1][2] != 4) kq = 0; if(A[2][0] != 7) kq = 0; if(A[2][1] != 6) kq = 0; if(A[2][2] != 5) kq = 0; return kq;

}

Void TimBuocDi(int A[][N], int n) {

int i, d, c; int h[4]; for(i = 0;I < 4; i++) h[i] = 32767; TimOTrong(A, n, d, c); if(c­1>0) swap(A[d][c],A[d][c­1]); h[0] = Heuristic(A,n); swap(A[d][c],A[d][c­1]); if(d­1>0) swap(A[d][c],A[d­1][c]); h[1] = Heuristic(A,n); swap(A[d][c],A[d­1][c]);

if(c+1

Void TimBuocDi(int A[][N], int n) {

…… int cs = 0; for (int i = 0 ; i < 4; i++)

if(h[cs] > h[i]) cs = i; if(cs == 0) swap(A[d][c],A[d][c­1]); if(cs == 1) swap(A[d][c],A[d­1][c]); if(cs == 2) swap(A[d][c],A[d][c+1]); if(cs == 3) swap(A[d][c],A[d+1][c]);

}

int  Heuristic(int A[][N], int n) {

int kq = 0; if(A[0][0] != 1) kq++; if(A[0][1] != 2) kq++; if(A[0][2] != 3) kq++; if(A[1][0] != 8) kq++; if(A[1][1] != 0) kq++; if(A[1][2] != 4) kq++; if(A[2][0] != 7) kq++; if(A[2][1] != 6) kq++; if(A[2][2] != 5) kq++; return kq;

}