Chương 2. Thuật toán – Thuật giải

Ầ

TR N MINH THÁI Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn

1

Cập nhật: 05 tháng 09 năm 2015

Nội dung

#2

1.

Thuật toán?

2.

Thuật toán vs Thuật giải

3.

Thuật giải Heuristic & các nguyên lý

4.

Tìm kiếm chiều sâu & Tìm kiếm chiều rộng

5.

Tìm kiếm leo đồi

6.

Tìm kiếm ưu tiên tối ưu

7. Một số thuật giải cơ bản

Thuật toán?

#3

• Là một thủ tục tính toán xác định nhận các giá trị hoặc một tập

các giá trị (input) và sinh ra một vài giá trị hoặc tập giá trị (output)

è Cách thức/ quy trình thực hiện hoàn thành một công việc xác

định cụ thể nào đó.

VD Cộng 2 số, tính tổng dãy Fibonaci, …

Đặc trưng của Thuật toán

#4

1.

Tính đúng đắn

2.

Tính dừng

3.

Tính xác định

4.

Tính hiệu quả

5.

Tính phổ quát

??? Đặc trưng nào quan trọng nhất ???

Đặc trưng của Thuật toán …

#5

[1] Tính đúng đắn *

Đảm bảo kết quả đúng sau khi thực hiện đối với bộ dữ liệu

đầu vào

[2] Tính dừng

Dừng  Sau một vài bước thực hiện

Đặc trưng của Thuật toán …

#6

[3] Tính xác định

- Rõ ràng, cụ thể

- Không nhập nhằng, gây hiểu lầm  hiểu, cài đặt

[4] Tính hiệu quả

- Giải quyết trong thời gian, điều kiện cho phép

- Đáp ứng yêu cầu người dùng

[5] Tính phổ quát

Có thể giải quyết được một lớp bài toán tương tự

Cách biểu diễn thuật toán

#7

02 cách phổ biến

[1] Mô tả các bước thực hiện của thuật toán

[2] Sử dụng sơ đồ thuật toán

Cách biểu diễn thuật toán

#8

[1] Mô tả các bước thực hiện của thuật toán

- Ngôn ngữ tự nhiên

- Mã giả (Pseudocode): Lai ghép ngôn ngữ tự

nhiên với

mã của ngôn ngữ lập trình

#9

VD Mô tả các bước thực hiện của thuật toán tìm USCLN của hai số nguyên – NN tự nhiên • Input: Hai số nguyên a, b

• Output: USCLN của a và b

• Thuật toán:

• Bước 1: Nếu a = b thì USCLN là a

• Bước 2: Nếu a > b thì tìm USCLN của a - b và b, quay lại Bước 1

• Bước 3: Nếu a < b thì tìm USCLN của a và b - a, quay lại Bước 1

#10

VD Mô tả các bước thực hiện của thuật toán tìm USCLN của hai số nguyên – Mã giả • Input: Hai số nguyên a, b

• Output: USCLN của a và b

• Thuật toán:

WHILE (a ≠ b) DO

IF (a > b) THEN

a = a – b;

ELSE

b = b – a;

END WHILE

RETURN a;

Một số từ khóa mã giả cơ bản

#11

IF <Điều kiện> THEN …ENDIF

IF <Điều kiện> THEN ... ELSE ... ENDIF

WHILE <Điều kiện> DO … ENDWHILE

DO … UNTIL <Điều kiện>

DISPLAY …

RETURN …

Cách biểu diễn thuật toán

#12

[2] Sử dụng sơ đồ thuật toán (flowchart)

Dùng các ký hiệu hình học để biểu diễn quá trình thực hiện

Nhập/ xuất

Bắt đầu/ kết thúc

Trả về giá trị

Rẽ nhánh

Điều kiện

Khối xử lý

Luồng xử lý

VD Sơ đồ thuật toán tìm trị tuyệt đối của số nguyên

#13

• Input: Số nguyên n

• Output: Giá trị tuyệt đối của n

• Thuật toán:

Độ phức tạp thuật toán

#14

• Đánh giá độ tốt/ xấu của thuật toán cùng loại

• Đơn giản, dễ hiểu, dễ cài đặt

• Thời gian thực hiện, sử dụng tài nguyên hệ thống

??? Thực tế ???

- Thuật toán hiệu quả  Dễ hiểu, dễ cài đặt?

- Ước lượng số phép tính thực hiện  Thời gian?

VD Thuật toán sắp xếp mảng một chiều bằng phương pháp đổi chỗ trực tiếp

#15

• Input: Mảng một chiều a, kích thước N

• Ouput: Mảng a có thứ tự tăng dần

• Thuật toán:

Số phép tính cần thực hiện?

Bước 1: i=1; Bước 2: j = i+1; Bước 3: Trong khi j<=N thực hiện Nếu a[j]

Thuật toán vs Thuật giải

#16

Tuy nhiên

• Nhiều bài toán chưa tìm ra một cách giải theo kiểu thuật toán/

không biết là có tồn tại thuật toán?

• Nhiều bài toán đã có thuật toán nhưng không chấp nhận được

vì thời gian quá lớn/ điều kiện khó đáp ứng

• Nhiều bài toán được giải theo những cách giải vi phạm thuật

toán nhưng vẫn chấp nhận được

Thuật toán vs Thuật giải

#17

• Tiêu chuẩn: tính xác định và tính đúng đắn được mở rộng

 Tính xác định thay đổi: giải thuật đệ quy và ngẫu nhiên

 Tính đúng không còn bắt buộc: cách giải gần đúng

 Chấp nhận các cách giải thường cho kết quả tốt (nhưng không

phải lúc nào cũng tốt) nhưng ít phức tạp và hiệu quả.

Thuật toán vs Thuật giải

#18

Lựa chọn?

“giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm”

hay

“một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ”

Khái niệm thuật giải

#19

• Cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải

 Dễ dàng hơn trong việc tìm kiếm phương pháp để giải quyết

các bài toán được đặt ra

 Trong AI thường sử dụng cách giải theo kiểu Heuristic

Đặc điểm thuật giải Heuristic

#20

• Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt

nhất)

• Dễ dàng và nhanh chóng đưa ra kết quả hơn so với giải thuật

tối ưu  chi phí thấp hơn

• Thể hiện khá tự nhiên, gần gũi với cách suy nghĩ và hành động

của con người

Các phương pháp Heuristic

#21

1.

Nguyên lý vét cạn thông minh

2.

Nguyên lý tham lam (Greedy)

3.

Nguyên lý thứ tự

4.

Hàm Heuristic

Các phương pháp Heuristic

#22

[1] Nguyên lý vét cạn thông minh

Tìm cách giới hạn lại không gian tìm kiếm/ thực hiện một kiểu dò tìm đặc biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu

[2] Nguyên lý tham lam

từng

Chọn lựa hành động tối ưu cho phạm vi cục bộ của bước trong quá trình tìm kiếm lời giải

Các phương pháp Heuristic

#23

[3] Nguyên lý thứ tự

Dựa trên một cấu trúc thứ tự hợp lý của không gian khảo sát

nhằm nhanh chóng đạt được một lời giải tốt

[4] Hàm Heuristic

Hàm đánh giá thô, giá trị của hàm phụ thuộc vào trạng

thái hiện tại của bài toán tại mỗi bước giải

Giá trị của hàm  chọn được cách hành động tương đối

hợp lý trong từng bước của thuật giải

Các bài toán tiêu biểu

#24

• Bài toán hành trình ngắn nhất – Nguyên lý Greedy

• Bài toán phân việc – Nguyên lý thứ tự

• Bài toán Ta-canh – Hàm Heuristic

Bài toán hành trình ngắn nhất

#25

Travelling Salesman Problem - TSP

Cho trước một danh sách các điểm giao hàng và khoảng cách giữa chúng. Nhân viên giao hàng xuất phát từ một điểm cho trước. Tìm đường đi ngắn nhất sao cho tất cả các điểm phải được giao hàng và mỗi điểm chỉ viếng thăm đúng một lần

Ý tưởng

#26

• Từ điểm xuất phát, liệt kê tất cả đường đi từ điểm xuất phát

cho đến n điểm  chọn đi theo con đường ngắn nhất

• Khi đã đi đến một điểm, chọn đi đến điểm kế tiếp cũng theo

nguyên tắc trên

• Lặp lại quá trình cho đến lúc không còn điểm nào để đi

Xuất phát từ điểm A  đường đi?

#27

Bài toán phân việc

#28

Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2,...,Jm. Công ty có n máy gia công lần lượt là P1, P2, ...Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị ngắt ngang. Ðể gia công một công việc Ji trên một máy bất kỳ ta cần dùng một thời gian tương ứng là ti. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n chi tiết trong thời gian sớm nhất

Bài toán phân việc

#29

ệ

ả ử   s   có  3  máy  M1,  M2,  M3  và  6  công  vi c  § Gi ờ ớ v i  th i  gian  là  t1=2,  t2=5,  t3=8,  t4=1,  t5=5,  t6=1.  ươ

ể

ng án có th  có:

§ Ph

Phương án tối ưu

#30

t3 = 8

M1

t1 = 2

t2 = 5

M2

t4 = 1

t3 = 5

M3

t6 = 1

Ý tưởng

#31

• Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia

công

• Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều

thời gian nhất

M1

J1

M2

J4

M3

J2

J3

Bài tập

#32

• Giả sử có 3 máy M1, M2, M3 và 5 công việc có thời gian thực

hiện tương ứng như sau: j1=3, j2 = 2, j3 = 2, j4 = 3, j5 = 2.

• Áp dụng nguyên lý thứ tự phân công các công việc vào các

máy.

Bài toán Ta-canh

#33

Trò chơi bao gồm một hình vuông kích thước 3x3 ô. Có 8 ô có số, mỗi ô có một số từ 1 đến 8. Một ô còn trống. Mỗi lần di chuyển chỉ được di chuyển một ô nằm cạnh ô trống về phía ô trống.

Từ một trạng thái ban đầu bất kỳ, làm sao đưa được về trạng thái cuối là trạng thái mà các ô được sắp lần lượt từ 1 đến 8 theo thứ tự từ trái sang phải, từ trên xuống dưới, ô cuối dùng là ô trống

Bài toán Ta-canh

#34

3

1

4

3

1

2

?

7

6

6

4

5

8

2

5

7

8

ạ

ể

ể trên, d

i, ướ

ờ ỗ • T i m i th i đi m có 4 cách di chuy n ( ố ) ả ủ trái, ph i c a ô tr ng ề

ể

ể

ọ

• V n đ  là ch n ô nào đ  di chuy n

ố

ấ VD ô s  2, 1, 6 hay 7?

Bài toán Ta-canh

#35

• Gọi T0 là trạng thái đích của bài toán

• Gọi Tk là trạng thái hiện tại đang xét

• V(i, j) là giá trị của ô (i, j) – Số thể hiện trên ô (ô trống có giá trị

0)

• d(i, j) là số ô cần di chuyển để con số tại ô (i, j) về đúng vị trí

của nó ở trạng thái T0

• Hàm Fk = tổng các d(i, j) của những ô (i, j) khác trống: Hàm

trạng thái Tk

Bài toán Ta-canh

1

3

2

4

6

5

#36

7

8

T0

3

1

4

7

6

8

2

5

ố § S  1: d(1, 2) = 1 ố § S  7: d(2, 1) = 1 ố § S  6: d(2, 3) = 0 ố § S  5: d(3, 3) = 2 § …

Fk = 2 + 1 + 3 + 1 + 0 + 1 + 2 + 2 = 12

Bài toán Ta-canh

1

3

2

4

6

5

#37

7

8

ả ử ọ

ể

ố

Gi

s  ch n di chuy n ô s  1

T0

3

1

4

3

4

7

6

7

6

1

8

2

5

8

5

2

è Fk (1) = 2 + 2 + 3 + 1 + 0 + 1 + 2 + 2 = 13

Bài toán Ta-canh

1

3

2

4

6

5

#38

7

8

ả ử ọ

ể

ố

Gi

s  ch n di chuy n ô s  7

T0

3

1

4

3

1

4

7

6

7

6

8

2

5

8

2

5

è Fk (7) = 2 + 1 + 3 + 2 + 0 + 1 + 2 + 2 = 13

Bài toán Ta-canh

1

3

2

4

6

5

#39

7

8

ả ử ọ

ể

ố

Gi

s  ch n di chuy n ô s  6

T0

3

1

4

3

1

4

7

6

7

6

8

2

5

8

2

5

è Fk (6) = 2 + 2 + 3 + 1 + 1 + 1 + 2 + 2 = 13

Bài toán Ta-canh

1

3

2

4

6

5

#40

7

8

ả ử ọ

ể

ố

Gi

s  ch n di chuy n ô s  2

T0

3

1

4

3

1

4

7

6

7

2

6

8

2

5

8

5

è Fk (2) = 2 + 2 + 3 + 1 + 0 + 1 + 1 + 2 = 11

Bài toán Ta-canh

1

3

2

4

6

5

#41

7

8

T0

Fk (1) = 13

Fk (7) = 13

Fk (6) = 13

Fk (2) = 11

ô

ạ

ể

ố

ọ

è Ch n di chuy n ô s  2

ọ Ch n  di  ể chuy n  sao  cho  ớ tr ng  thái  m i  ấ ỏ có Fk nh  nh t

Bài tập

#42

• Tìm phương án sắp xếp tối ưu cho bài toán sau:

3

1

1

2

3

4

5

6

5

2

4

7

8

6

8

7

1

2

3

3

2

1

4

5

6

6

5

4

7

8

7

8

Không gian trạng thái - KGTT

#43

Một KGTT (state space) là 1 bộ [N, A, S, GD] trong đó:

• N (node): các nút/ trạng thái của đồ thị • A (arc): các cung/ các liên kết giữa các nút • S (solution): chứa trạng thái ban đầu của bài toán • GD (Goal Description): chứa các trạng thái đích của bài toán  Đường đi của lời giải (solution path) là một con đường đi qua đồ thị này từ một nút thuộc S đến một nút thuộc GD

Chiến lược tìm kiếm KGTT

#44

• TK hướng từ dữ liệu (Data-driven Search)

• Suy diễn tiến (forward chaining)

• TK hướng từ mục tiêu (Goal-driven Search)

• Suy diễn lùi (backward chaining)

Tìm kiếm hướng từ dữ liệu

#45

• Việc tìm kiếm đi từ

dữ liệu đến mục tiêu

• Thích hợp khi:

• Tất cả/ một phần dữ liệu được cho từ đầu

• Có nhiều mục tiêu, nhưng chỉ có một số ít các phép toán có thể áp

dụng cho một trạng thái bài toán

• Rất khó đưa ra một mục tiêu/ giả thuyết ngay lúc đầu

Tìm kiếm hướng từ mục tiêu

#46

• Việc tìm kiếm đi từ

mục tiêu trở về

dữ liệu

• Thích hợp khi:

• Có thể đưa ra mục tiêu/ giả thuyết ngay lúc đầu

• Có nhiều phép toán có thể áp dụng trên 1 trạng thái của

bài toán => sự bùng nổ số lượng các trạng thái

• Các dữ liệu của bài toán không được cho trước, nhưng hệ

thống phải đạt được trong quá trình tìm kiếm

Phương pháp TK trên đồ thị KGTT

#47

Phát triển từ giải thuật quay lui (back – tracking) • Tìm kiếm chiều rộng (breath-first search)

• Tìm kiếm chiều sâu (depth-first search)

• TK chiều sâu bằng cách đào sâu nhiều lần (depth-first search

with iterative deepening)

Tìm kiếm chiều rộng

#48

1. Khởi tạo Open = [A];

Closed = []

2.

Open = [B,C,D]

Closed = [A]

3.

Open = [C,D,E,F]

Closed = [B,A]

5. Open = [D,E,F,G,H];

Closed = [C,B,A]

7. Open = [E,F,G,H,I,J];

Closed = [D,C,B,A]

9. Open = [F,G,H,I,J,K,L];

Closed = [E,D,C,B,A]

11. Open = [G,H,I,J,K,L,M];

Closed = [F,E,D,C,B,A]

…

Tìm kiếm chiều sâu

#49

ở ạ

1. Kh i t o: Open = [A];

Closed = []

3. Open = [B,C,D];

Closed = [A]

5. Open = [E,F,C,D]; Closed = [B,A]

7. Open = [K,L,F,C,D];

Closed = [E,B,A]

9. Open = [S,L,F,C,D];

Closed = [K,E,B,A]

6.

Open = [L,F,C,D];

Closed = [S,K,E,B,A]

7.

Open = [T,F,C,D];

Closed = [L,S,K,E,B,A]

8.

Open = [F,C,D];

Closed = [T,L,S,K,E,B,A]

…

Tìm kiếm chiều sâu hay chiều rộng?

#50

• Có cần thiết tìm một đường đi ngắn nhất đến mục tiêu hay

không?

• Sự phân nhánh của không gian trạng thái

• Tài nguyên về không gian & thời gian sẵn có

• Khoảng cách trung bình của đường dẫn đến trạng thái mục tiêu

• Yêu cầu đưa ra tất cả các lời giải/chỉ là lời giải tìm được đầu

tiên

#51

Tìm kiếm chiều sâu bằng cách đào sâu nhiều lần • Độ sâu giới hạn (depth bound): giải thuật TK sâu sẽ quay lui khi trạng thái đang xét đạt đến độ sâu giới hạn đã định

• TK chiều sâu bằng cách đào sâu nhiều lần: TK sâu với độ sâu giới hạn là 1, nếu thất bại, nó sẽ lặp lại GT TK chiều sâu với độ sâu là 2,… GT tiếp tục cho đến khi tìm được mục tiêu, mỗi lần lặp lại tăng độ sâu lên 1

• GT này có độ phức tạp về thời gian cùng bậc với TK Rộng và TK

Sâu

Tìm kiếm leo đồi

#52

• Giải thuật:

• Mở rộng trạng thái hiện tại và đánh giá các trạng thái con của nó bằng

hàm đánh giá heuristic

• Con “tốt nhất” sẽ được chọn để đi tiếp

• Giới hạn:

• Giải thuật có khuynh hướng bị sa lầy ở những cực đại cục bộ:

Ø 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 lưu giữ thông tin về

các trạng thái đã duyệt

Tìm kiếm leo đồi

#53

1. Khởi tạo ngăn xếp S chỉ chứa trạng thái đầu;

2. Lặp

2.1 If S rỗng then

{thông báo thất bại; stop};

2.2 Lấy trạng thái u ở đầu ngăn xếp S;

2.3 If u là trạng thái kết thúc then

{thông báo thành công; stop};

2.4 For mỗi trạng thái v kề u do

đặt v vào danh sách L;

2.5 Sắp xếp L theo thứ tự: trạng thái tốt nhất ở đầu danh

sách;

2.6 Chuyển danh sách L vào ngăn xếp S;

Tìm kiếm leo đồi

#54

ở ạ

1. Kh i t o Open = [A5]; Closed = [] 2. Đánh giá A5: Open = [B4,C4,D6];

Closed = [A5]

3. Đánh giá B4:  Open = [C4,E5,F5,D6];

Closed = [B4,A5]

4. Đánh giá C4:

Open = [H3,G4,E5,F5,D6]; Closed =

[C4,B4,A5] 5. Đánh giá H3:

Open = [O2,P3,G4,E5,F5,D6];  Closed = [H3,C4,B4,A5]

ả 6. Đánh giá O2: Open = [P3,G4,E5,F5,D6];  Closed = [O2,H3,C4,B4,A5] ượ ờ c l 7. Đánh giá P3: tìm đ i gi i!

Tìm kiếm ưu tiên tối ưu (Best-First Search)

#55

• Tìm kiếm chiều sâu: không quan tâm đến sự mở rộng của tất

cả các nhánh

• Tìm kiếm chiều rộng: không bị rơi vào các nhánh cụt

• Tìm kiếm ưu tiên tối ưu: kết hợp tìm kiếm chiều sâu + tìm kiếm

chiều rộng

 Mở rộng cây theo các nút có nhiều tiềm năng chứa trạng thái đích hơn các nút khác

Tìm kiếm BFS - Ví dụ

#56

Thuật giải BFS

#57

1. Đặt OPEN chứa trạng thái khởi đầu.

2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :

2.1. Chọn trạng thái tốt nhất (Tmax) trong OPEN (và xóa Tmaxkhỏi OPEN)

2.2. Nếu Tmax là trạng thái kết thúc thì thoát.

2.3. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện:

Tính f(Tk);

Thêm Tk vào OPEN

Thuật giải AT

#58

1. Đặt OPEN chứa trạng thái khởi đầu.

2. Cho đến khi tìm được trạng thái đích hoặc không còn nút nào trong OPEN, thực hiện :

2.1. Chọn trạng thái (Tmax) có giá trị g nhỏ nhất trong OPEN

(và xóa Tmax khỏi OPEN)

2.2. Nếu Tmax là trạng thái kết thúc thì thoát.

2.3. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể có từ

trạng thái Tmax. Đối với mỗi trạng thái kế tiếp Tk thực hiện :

g(Tk) = g(Tmax) + cost(Tmax, Tk);

Thêm Tk vào OPEN.

#59

Thuật giải AKT (Algorithm for Knowlegeable Tree Search) 1. Đặt OPEN chứa trạng thái khởi đầu.

2. Cho đến khi tìm được trạng thái đích/ không còn nút nào trong OPEN:

2.1. Chọn trạng thái (Tmax) có giá trị f nhỏ nhất trong xóa Tmax khỏi OPEN)

OPEN (và

2.2. Nếu Tmax là trạng thái kết thúc thì thoát.

2.3. Ngược lại, tạo ra các trạng thái kế tiếp Tk có thể trạng thái Tmax. Đối với mỗi trạng thái kế tiếp

có từ Tk

thực hiện :

g(Tk) = g(Tmax) + cost(Tmax, Tk);

Tính h’(Tk)

f(Tk) = g(Tk) + h’(Tk);

Thêm Tk vào OPEN.

Thuật giải A*

1. Open:={s}; Close:={};

#60

2. Trong khi (Open khác rỗng )

2.1 Chọn đỉnh p tốt nhất trong Open

2.2 Nếu p là đỉnh kết thúc thì thoát.

2.3 Di chuyển đỉnh p qua Close và tạo danh sách các đỉnh q có nối với

p

2.3.1 Nếu q có trong Open:

Nếu (g(q) > g(p) +cost(p,q)) thì

g(q) = g(p) +cost(p,q)

f(q) = g(q) + h(q);

Nút trước của q là p;

2.3.2 Nếu q chưa có trong Open thì

g(q) = g(p) + cost(p,q);

f(q) = g(q) + h(q);

Thêm q vào Open;

Nút trước q là p;

2.3.3 Nếu q có trong Close thì

Nếu (g(q)>g(p)+cost(p,q)) thì

Di chuyển q vào Open;

Nút trước của q là p;

3. Không tìm được.

Thuật giải A* - Ví dụ

#61

• Cho đồ thị, trạng thái ban đầu A. Tìm đường đi ngắn nhất đến

trạng thái đích B

ị ạ

ỗ ỉ i  m i  đ nh  ị tr   hàm  h  ng  ng ị ạ

§ Giá  tr   t là  giá  ươ ứ t § Giá tr  t

ữ

ỉ

ỗ ạ i m i c nh  ườ ộ là  đ   dài  đ ng  đi  gi a hai đ nh

Thuật giải A* - Ví dụ

#62

Đỉnh đã có trong Open

Đỉnh đã có trong Closed

ố ớ

ỉ

B cướ

Open

Ch n pọ

Closed

Các đ nh q n i v i p

A

1

E có trong  Open: C p ậ nh t gEậ

A

A

2

C (gC=9, hC=15, fC=24) D (gD=7, hD=6, fD=13) E (gE=13, hE=8, fE=21) F (gF=20, hF=7, fF=27)

D

D, E, C, F

A, D

3

E (gE=gD+kc(D,E)=7+4, hE=8, fE=19) H (gH=gD+kc(D,H)=7+8, hH=10, fH=25)

E

E, C, H, F

A, D, E

4

I (gI=gE+kc(E,I)=11+3, hI=4, fI=18) K (gK=gE+kc(E,K)=11+4, hK=2, fK=17)

B (gB=gK+kc(K,B)=15+6, hB=0, fB=21)

K

5

K, I, C, H, F

A, D, E, K

ữ

K trong Closed

I

I, B, C, H, F

A, D, E, K, I

6

K (gK

B

B, C, H, F

A, D, E, K, I, B

7

Cây tìm kiếm tìm được

#63

14

7

A

F

9

7

13

15

8

C

4

6

D

E

4

3

8

9

4

2

I

K

10

H

6

5

0

B

Thuật giải A* - Bài tập

#64

• Cho đồ thị, trạng thái ban đầu A. Tìm đường đi ngắn nhất đến

trạng thái đích K

15

9

3

8

A

B

11

C

11

6

5

6

7

7

8

2

D

5

6

3

F

7

3

4

E

5

5

9

G

5

K

2

0

8

6

H

1

Bài toán tô màu đồ thị

#65

• Cho đồ thị vô hướng, hãy tô màu tất cả các đỉnh với số màu ít

nhất, sao cho 2 đỉnh nối với nhau được tô khác màu

Bài toán tô màu đồ thị

#66

Gọi k là số màu đã được dùng để tô màu

k=1;

Trong khi chưa tô hết các đỉnh {

Chọn đỉnh p có bậc cao nhất

Lặp từ màu 1 đến màu k

{

Nếu tồn tại màu i khác với màu các đỉnh kề với p thì chọn màu

i

} Nếu đỉnh p chưa tô màu. Tô màu cho đỉnh p với màu mới k +1

}

Bài toán tô màu đồ thị - Ví dụ

#67

A

I

C

E

D

H

B

F

G

C D F

E H

I

A B G

Đ nhỉ B cậ

6

5

4

3

3

3

2

2

2

Bài toán tô màu đồ thị - Ví dụ

#68

A

I

C

E

ỉ ỉ

D

H

ỉ

B

F

[1] Tô màu 1 cho đ nh Cỉ [2] Tô màu 2 cho đ nh Dỉ [3] Tô màu 1 cho đ nh F [4] Tô màu 3 cho đ nh E [5] Tô màu 3 cho đ nh Hỉ [6] Tô màu 1 cho đ nh I [7] Tô màu 2 cho đ nh Aỉ [8] Tô màu 2 cho đ nh Bỉ [9] Tô màu 2 cho đ nh Gỉ

G

Bài toán tô màu đồ thị

#69

• Vấn đề cài đặt:

• Loại bỏ đỉnh đã tô

• Đánh dấu những màu bị cấm tô của mỗi đỉnh

Bài toán tô màu đồ thị

#70

Gọi k là số màu đã được dùng để tô màu

k=1;

Trong khi chưa tô hết các đỉnh {

Chọn đỉnh p có bậc cao nhất

Lặp từ màu 1 đến màu k

Nếu tồn tại màu i không bị cấm tô thì màu tô p = i

Nếu đỉnh p chưa tô màu thì

k=k+1, màu tô p = k

Với những đỉnh q có nối với p

Hạ bậc q, thêm màu tô p vào danh sách màu cấm tô của q

Gán bậc của đỉnh p = 0

}

Bài toán tô màu đồ thị - Ví dụ

#71

ồ ị

ụ

Áp d ng tô màu cho đ  th  sau

A

I

Đ nhỉ C B cậ 6

D 5

C

F 4

E

E 3

D

H

H 3

I 3

B

F

A 2

B 2

G

G 2

Bài toán tô màu đồ thị - Ví dụ

#72

• Bước 1: Chọn

đỉnh C

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B c ậ m iớ

1 C 6 0

• Các đỉnh nối với C: A, B, D, E, G, H, G

D 5 1 4

F 4 4

A

E 3 1 2

I

C

H 3 1 2

E

I 3 3

D

H

A 2 1 1

B

F

B 2 1 1

G

G 2 1 1

Bài toán tô màu đồ thị - Ví dụ

#73

• Bước 2: Chọn

đỉnh D

Đ nhỉ B cậ ấ Màu c m tô Màu tô

• Các đỉnh nối

B c ậ m iớ

D 4 1 2 0

với D: E, F, H, I

F 4 2 3

E 2 1, 2 1

A

I

H 2 1, 2 1

C

I 3 2 2

E

D

A 1 1 1

H

B

B 1 1 1

F

G 1 1 1

G

C 0 1 0

Bài toán tô màu đồ thị - Ví dụ

#74

• Bước 3: Chọn

đỉnh F

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B c ậ m iớ

• Các đỉnh nối với F: B, H, G

F 3 2 1 0

E 1 1 1, 2

H 1 1, 2 0

A

I 2 2 2

I

A 1 1 1

C

E

B 1 1 0

D

H

G 1 1 0

B

F

C 0 1

G

D 0 2

Bài toán tô màu đồ thị - Ví dụ

#75

• Bước 4: Chọn

đỉnh I

Đ nhỉ B cậ ấ Màu c m tô Màu tô

• Các đỉnh nối với I: A, E

I 2 B c ậ m iớ 0 2 1

A 1 1 0

E 1 1, 2 0

A

B 0 0 1

I

H 0 0 1, 2

C

E

G 0 0 1

D

H

C 0 1

B

F

D 0 2

G

F 0 1

Bài toán tô màu đồ thị - Ví dụ

#76

• Bước 5: Chọn

đỉnh A

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B c ậ m iớ 0 1 A 0 2

0 1 B 0

0 1, 2 E 0

0 1, 2 H 0

A

I

0 1 G 0

C

E

C 0 1

D

H

D 0 2

B

F

F 0 1

G

I 0 1

Bài toán tô màu đồ thị - Ví dụ

#77

• Bước 6: Chọn

đỉnh B

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B 0 B c ậ m iớ 0 1 2

E 0 0 1, 2

H 0 0 1, 2

G 0 0 1

A

I

C 0 1

C

E

D 0 2

D

H

F 0 1

B

F

I 0 1

G

A 0 2

Bài toán tô màu đồ thị - Ví dụ

#78

• Bước 7: Chọn

đỉnh E

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B c ậ m iớ 0 1, 2 E 0 3

0 1, 2 H 0

0 1 G 0

C 0 1

A

I

D 0 2

C

E

F 0 1

D

H

I 0 1

B

F

A 0 2

G

B 0 2

Bài toán tô màu đồ thị - Ví dụ

#79

• Bước 8: Chọn

đỉnh H

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B c ậ m iớ 0 1, 2 H 0 3

0 1 G 0

C 0 1

D 0 2

A

I

F 0 1

C

E

I 0 1

D

H

A 0 2

B

F

B 0 2

G

E 0 3

Bài toán tô màu đồ thị - Ví dụ

#80

• Bước 9: Chọn

đỉnh G

Đ nhỉ B cậ ấ Màu c m tô Màu tô

B c ậ m iớ 0 1 G 0 2

C 0 1

D 0 2

F 0 1

A

I

I 0 1

C

E

A 0 2

D

H

B 0 2

B

F

E 0 3

G

H 0 3

Bài toán tô màu đồ thị - Bài tập

#81

A

I

C

E

D

H

B

F

G

Bài tập

#82

• Áp dụng giải thuật A* cho bài toán Ta-Canh

• Áp dụng giải thuật tô màu đồ thị cho bài toán xếp lịch, cuộc họp

và bố trí đèn tín hiệu giao thông

• Cài đặt các thuật toán trên

Q&A

#83