Thuật giải AT ( Algorithm for Tree ) : Mỗi đỉnh n tương ứng với 1 số ít g ( n ) : giá tiền của đường đi từ đỉnh bắt đầ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 lập. Bước 1 : + Mọi đỉnh n, mọi giá trị g ( n ) đều là ẩn. + Mở đỉnh tiên phong và gọi đó là đỉnh S. Đặt g ( S ) = 0. Bước 2 : Chọn đỉnh mở với giá tiền g tương ứng là nhỏ nhất và gọi đó là đỉnh N. + Nếu N là tiềm năng : đường đi từ đỉnh khởi đầu đến N là đường đi ngắn nhất và bằng g ( N ). Dừng ( Success ). + Nếu không sống sót một đỉnh mở nào nữa : cây màn biểu diễn yếu tố không có đường đi tới tiềm năng. Dừng ( Fail ). + Nếu sống sót nhiều hơn 1 đỉnh N ( nghĩa là có 2 đỉnh N trở lên ) mà có cùng giá tiền 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 bắt đầ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 những đỉnh đó và gọi là đỉnh N. Bước 3 : Đóng đỉnh N và mở những đỉ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 ( N → S ) Bước 4 : Quay lại bước 2
32 trang |
Chia sẻ: candy98
| Lượt xem : 6389
| Lượt tải: 0
Bạn đang xem trước 20 trang
tài liệu Bài giảng Trí tuệ nhân tạo – Bài 2: Thuật giải AT, AKT – Văn Thế Thành, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
1Thuậ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(N→S)
Bước 4: Quay lại bước 2
2Thuật giải AT- Ví dụ
A B C
D
E
K
O
Q
S T
U
V
F
G H
L M
I J
N
P
R
Traïng thaùi ñích
1
1
1
1
1
1
1
1
100
17
1
1
1
10
1 1
20 12 1
1
1
1
Thuật giải AT- Ví dụ
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(S→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
A B C
D
E
K
O
Q
S T
U
V
F
G H
L M
I J
N
P
R
Traïng thaùi ñích
1
1
1
1
1
1
1
1
100
17
1
1
1
10
1 1
20 12 1
1
1
1
3Thuật giải AT- Ví dụ
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)
A B C
D
E
K
O
Q
S T
U
V
F
G H
L M
I J
N
P
R
Traïng thaùi ñích
1
1
1
1
1
1
1
1
100
17
1
1
1
10
1 1
20 12 1
1
1
1
Thuật giải AT- Ví dụ
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 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.
RPNJDS →→→→→ 11111
A B C
D
E
K
O
Q
S T
U
V
F
G H
L M
I J
N
P
R
Traïng thaùi ñích
1
1
1
1
1
1
1
1
100
17
1
1
1
10
1 1
20 12 1
1
1
1
4Thuật giải AKT – Tìm kiếm với tri thức bổ
sung (Algorithm for Knowledgeable Tree Search):
Thuật giải AT là thuật giải tìm kiếm đường đi tốt nhất đối với cây chỉ có
các thông tin về đỉnh, cung và giá trị của cung. Trong nhiều trường hợp
việc tìm kiếm đường đi sẽ được định hướng rõ thêm nếu sử dụng các
tri thức thu được dựa trên các hiểu biết về tình huống vấn đề ở mỗi
bước.
Tri thức bổ sung ở mỗi đỉnh được tương ứng với một giá trị h(n). Chẳng
hạn đó là ước lượng giá thành đường đi từ n đến mục tiêu. Ở ví dụ của
giải thuật AT, ở bước đầu tiên :
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 ước lượng được:
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
Bước 1:
Mọi đỉnh, cũng như các hàm g, h, f chưa biết.
Mở đỉnh đầu tiên S, gán g(S) = 0
Sử dụng tri thức bổ sung để ước tính hàm h(S)
Tính f(S) = g(S) + h(S)
Bước 2: Chọn đỉnh mở có f 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 nhỏ nhất: Chúng ta phải kiểm tra xem những đỉnh đó
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 đỉ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(S→N)
Sử dụng tri thức bổ sung để tính h(S) và f(S): f(S) = g(S) + h(S)
Bước 4: Quay lại bước 2.
5Bài toán Tháp Hà Nội với n = 2
S0 Sn
Các trường hợp của bài toán là với trạng thái cột thứ ba:
h(n) = 0 1 2 3
g = 0
h = 2
f = 2
g = 1
h = 2
f = 3 (min)
g = 1
h = 3
f = 4
g = 2
h = 2
f = 4
g = 2
h = 3
f = 5
g = 2
h = 1
f = 3 (min)
g = 3
h = 2
f = 5
g = 3
h = 1
f = 4
g = 3
h = 0
f = 3 (Ñích)
6Bài toán taci
1
2 3
4
5
6
7
8 21 3
4
567
8
S0 Sn
Cách 1:
≠
=
=δδ=∑
= i
i
ii
t
1i
ii b1
b0)b,a()b,a(H
i
i
a neáu
a neáu
vôùi
1
2 3
4
5
6
7
8
g = 0
h = 4 (coù 4 soá sai vò trí so vôùi Goal)
f = 4
1
2 3
4
5
6
7
8
g = 1
h = 5
f = 6
1
2 3
4
567
8
g = 1
h = 3
f = 4 (min)
1
2 3
4
5
6
7
8
g = 1
h = 5
f = 6
1
2 3
4
567
8
g = 2
h = 3
f = 5
1
2 3
4
567
8
g = 2
h = 3
f = 5 (min)
1
2 3
4
567
8
g = 2
h = 4
f = 6
1
2 3
4
567
8
g = 3
h = 2
f = 5 (min)
1
2 3
4
567
8
g = 3
h = 4
f = 7
1 2 3
4
567
8
g = 4
h = 1
f = 5 (min)
1 2 3
4
567
8
g = 5
h = 0
f = 5 (Ñích)
7Bài toán taci
Cách 2:
∑
=
η=
t
i
ii
)b,a(H
1
với η(ai,bi) là số lần ít nhất phải đẩy ô ai = a theo chiều dọc
hay ngang về đúng vị trí bi = b.
Giả sử:
1
2 3
4
5
6
7
8
1
1
Soá
Vò trí
Coäng2
1
3
0
4
0
5
0
6
1
7
0
8
2 5
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.
8Thuậ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:
S0 = E; {Trang thái ban đầu}
g(S0) = 0;
f(S0) = g(S0)+ h(S0) ;
θ= {S0}; {Gán S0 cho tập đỉnh mở}
C={}; {Gán tập đóng C bằng rỗng}
while θ ≠ {} do
Bước 2: Chọn một S trong θ với f(S) nhỏ nhất:
θ = θ – {S}
C = C + {S} {Đóng đỉnh 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)
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)
Bước 4: Đặt vào trong θ những Si không có trong θ lẫn
trong C. Với các Si đã có trong θ 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}
θ := θ + {Si} {Mở Si}
End A*
9Thuậ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)
+ 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(S→N)
Nếu đỉnh S đã mở và g(S)≤ g’(S) thì bỏ qua 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.
10
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.
11
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
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)}
12
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ố.
13
Minh hoạ GT A*
Minh hoạ GT A*
14
Minh hoạ GT A*
Minh hoạ GT A*
15
Minh hoạ GT A*
Minh hoạ GT A*
16
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.
G=0
H=3
F=3
G=1
H=3
F=4
G=1
H=4
F=5
G=2
H=3
F=5
H=4
F=6
H=4
F=6
H=3
F=5
H=4
F=6
H=3
F=5
VI DU 2 - THAP HA NO N=3
17
G=3
H=3
F=6
H=5
F=9
H=3
F=7
H=2
F=6
H=3
F=6
H=3
F=7
H=3
F=7
H=6
F=10
H=3
F=8
H=4
F=9
H=2
F=7
VI DU VE GT A* - THAP HA NOI N=3
Nhận xét
Mối quan hệ giữa AT, AKT, A*:
f(S) = (1 - α) g(S) + α h(S) với 0 ≤ α ≤ 1
- Nếu α = 0 → AT (không có tri thức bổ sung)
- Nếu α = 1 → AKT (Phụ thuợc vào tri thức bổ sung)
- Nếu α = ½ → A*
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ị
18
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.
19
Ví dụ
A
C
D
E
2
3
4
5
7
1
1
3
2
4
∞
∞
∞
∞
∞
=
3235
3147
2142
3441
5721
C
U = A
Tour = {}
Cost = 0
V = A
W ∈ {B, C, D, E} {Các đỉnh có thể đến từ A}
→ W = B {Vì qua B có giá thành bé nhất}
Tour = {(A, B)}
Cost = 1
V = B
W ∈ {C, D, E}
→ W = E
Tour = {(A, B),(B, E)}
Cost = 1 + 3 = 4
V = E
W ∈ {C, D}
Ví dụ
→ W = C
Tour = {(A, B), (B, E), (E, C)}
Cost = 4 + 2 = 6
V = C
W ∈ {D}
→ W = D
Tour = {(A, B), (B, E), (E, C), (C, D)}
Cost = 6 + 1 = 7
V = D
Tour = {(A, B), (B, E), (E, C), (C, D), (D, A)}
Cost = 7 + 7 = 14
Kết quả: Tour du lịch A → B → E → C → D → A với giá thành Cost
= 14.
Nhận xét: Tuy nhiên kết quả nhỏ nhất sẽ là A → B → D → C → E → A với
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.
A
C
D
E
2
3
4
5
7
1
1
3
2
4
20
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=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.
A
B
C
D
E
2
3
4
5
7
1
1
3
2
4
21
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
1
Lisbon
4
Madrid
1
Paris
Brusels
1
2
4
4
2
3
3
Luxemburg
The Hague
Berlin
Viene
Rome
Berne
Đỉnh Lisbon
L
Madrid
M
Paris
P
Berne
Be
Rome
R
Viene
V
Berlin
Ber
Luxemburg
Lx
Brusen
Bru
Hague
H
Bậc 1 2 6 4 3 3 6 3 4 2
22
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 3 2 2 3
1 1 1 2 1 1 1 2
Đỉnh L M P Be R V Ber Lx Bru H
Màu tô 1 2 1 3 2 1 2 4 3 1
Bậc 1 2 6* 4 3 3 6 3 4 2
Hạ bậc lần 1 1 1 0 3 2 3 5* 2 3 2
Hạ bậc lần 2 1 1 2 2* 2 0 1 2 1
Hạ bậc lần 3 1 1 1 0 1 1 2* 1
Hạ bậc lần 4 1* 1 1 1 0 0 0
Hạ bậc lần 5 0 1* 1 0 0
Hạ bậc lần 6 0 0 0 0 0
23
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.
A
I
H
G F
E
D
C
B
24
4
3 3
2 2 4 3 2 3 2
Màu cấm
tô
1 1 1 1 1 2 1 1
Đỉnh A B C D E F G H I
Màu tô 3 4 2 1 2 3 1 2 5
Bậc 5 5 2 7* 2 4 2 6 5
Hạ bậc 4 4 1 0 1 3 2 5* 4
3* 3 1 1 2 1 0 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
25
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:
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.
b. 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
26
1. Leo đồi đơn giản (tt)
c. Tư tưởng
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. Đánh giá trạng thái Tk mới :
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.
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).
27
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.
28
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)
