Week 4 Lab — Answer Key

Bài 1

Đồ thị G — 7 thuật toán tìm kiếm

h(n): S=11, A=9, B=8, C=3, D=8, E=6, F=4, G=4, H=5, I=3, J=5, T=0 | Quy tắc hoà: alphabet | Cạnh: S→A:2, S→B:7, S→C:1, A→D:4, A→E:2, B→E:1, B→F:5, C→G:3, C→F:9, D→H:8, D→E:1, E→H:6, E→I:3, F→I:2, F→J:8, G→F:3, G→J:2, H→I:2, H→T:5, I→T:4, I→J:2, J→T:6

1. BFS (Breadth-First Search)

OPEN = hàng đợi FIFO. Bỏ qua nút đã có trong OPEN hoặc CLOSED khi mở rộng.

Step	u	Edge(u)	OPEN (đầu → cuối)
0	—	—	S
1	S	A, B, C	A, B, C
2	A	D, E	B, C, D, E
3	B	F (skip: E∈OPEN)	C, D, E, F
4	C	G (skip: F∈OPEN)	D, E, F, G
5	D	H (skip: E∈OPEN)	E, F, G, H
6	E	I (skip: H∈OPEN)	F, G, H, I
7	F	J (skip: I∈OPEN)	G, H, I, J
8	G	(skip: F∈CLOSED, J∈OPEN)	H, I, J
9	H	T (skip: I∈OPEN)	I, J, T
10	I	(skip: J∈OPEN, T∈OPEN)	J, T
11	J	(skip: T∈OPEN)	T
12	T	GOAL ✓	—

Đường đi: S → A → D → H → T | Chi phí: 2+4+8+5 = 19 | 12 nút mở rộng

2. DFS (Depth-First Search)

OPEN = ngăn xếp LIFO (top = trái). Đẩy con theo thứ tự đảo ngược alphabet. Cho phép trùng lặp; bỏ qua khi pop nếu đã ở CLOSED. Dấu * = bản sao trong OPEN.

Step	u	Edge(u) đẩy vào stack	OPEN (top →)
0	—	—	S
1	S	A, B, C	A, B, C
2	A	D, E	D, E, B, C
3	D	H, E*	E, H, E, B, C
4	E	H, I	H, I, H, E, B, C
5	H	I*, T	I, T, I, H, E, B, C
6	I	J, T*	J, T, T, I, H, E, B, C
7	J	T*	T, T, T, I, H, E, B, C
8	T	GOAL ✓	—

Đường đi: S → A → D → E → H → I → J → T | Chi phí: 2+4+1+6+2+2+6 = 23 | 8 nút mở rộng

3. Depth-Limited DFS (L = 4)

Chạy như DFS nhưng không mở rộng nút có độ sâu = L. Không dùng CLOSED toàn cục — chỉ tránh lặp trên đường đi hiện tại.

S (d=0)

└─ A (d=1)

   ├─ D (d=2)

   │  ├─ E (d=3)

   │  │  ├─ H (d=4) ← giới hạn, không phải đích → quay lui

   │  │  └─ I (d=4) ← giới hạn, không phải đích → quay lui

   │  └─ H (d=3)

   │     ├─ I (d=4) ← giới hạn, không phải đích → quay lui

   │     └─ T (d=4) ← ĐÍCH ✓

Đường đi: S → A → D → H → T | Chi phí: 19

4. Iterative Deepening DFS (IDDFS)

Lần lặp	Giới hạn L	Kết quả
1	0	Chỉ xét S — không phải đích → Thất bại
2	1	Xét S, A, B, C — không phải đích → Thất bại
3	2	Xét đến độ sâu 2 — T chưa đến được → Thất bại
4	3	Xét đến độ sâu 3 — T ở sâu nhất d=4 → Thất bại
5	4	Tìm thấy T theo DL-DFS(L=4) → Thành công ✓

Đường đi: S → A → D → H → T (giống DL-DFS với L=4) | Chi phí: 19

5. Greedy Best-First Search

OPEN = hàng đợi ưu tiên sắp xếp tăng dần theo h(n). Ký hiệu: X^h = nút X với h(X) = h.

Step	u	Edge(u)	OPEN (h↑)
0	—	—	S¹¹
1	S	C³, B⁸, A⁹	C³, B⁸, A⁹
2	C	F⁴, G⁴	F⁴, G⁴, B⁸, A⁹
3	F	I³, J⁵	I³, G⁴, J⁵, B⁸, A⁹
4	I	T⁰ (skip: J∈OPEN)	T⁰, G⁴, J⁵, B⁸, A⁹
5	T	GOAL ✓	—

Bước 2: C→F(h=4) và C→G(h=4) cùng h → alphabet: F trước G. h(C)=3 thấp nhất con của S — Greedy bị hút vào C ngay, chọn đoạn C→F tốn 9 mà không nhận ra vì không theo dõi g(n).

Đường đi: S → C → F → I → T | Chi phí: 1+9+2+4 = 16 | 5 nút mở rộng

6. Beam Search (w = 2)

Mỗi bước giữ lại w = 2 nút có h nhỏ nhất từ toàn bộ con của các nút trong beam. Mở rộng đồng thời tất cả nút trong beam.

Step	Beam hiện tại	Mở rộng → con (h)	Beam mới (top‑2)
0	{ S(11) }	A(9), B(8), C(3)	{ C(3), B(8) }
1	{ C(3), B(8) }	C→G(4),F(4) ; B→E(6),F(4)	{ F(4), G(4) }
2	{ F(4), G(4) }	F→I(3),J(5) ; G→J(5)	{ I(3), J(5) }
3	{ I(3), J(5) }	I→T(0) ; J→T(0)	T tìm thấy! ✓

Bước 1: F xuất hiện từ cả C và B → giữ một (cha = C vì h(C) < h(B)). E(6) bị loại vì đứng thứ 3.

Đường đi: S → C → F → I → T | Chi phí: 16 | Cùng kết quả với Greedy

7. Hill Climbing (Steepest Ascent)

Tại mỗi bước, di chuyển đến nút con có h nhỏ nhất. Dừng nếu không có con nào cải thiện h. Không có OPEN list, không backtrack.

Step	Nút hiện tại	h	Các nút con (h)	Quyết định
0	S	11	A(9), B(8), C(3)	→ C
1	C	3	G(4), F(4) — đều > 3	KẸT ⚑

⚠ Hill Climbing không tìm được T. C là cực tiểu địa phương: h(C)=3 < h của mọi con. HC không có OPEN list để quay lui.

Câu hỏi — Đáp án

Câu 1. So sánh kết quả của 7 thuật toán.

Greedy và Beam tìm chi phí 16 (thấp hơn BFS/DFS/DL-DFS/IDDFS là 19 hoặc 23) nhờ dùng h(n) định hướng về đích. Tuy nhiên cả hai đều không tối ưu (tối ưu = 11). HC không tìm được lời giải.

Câu 2. Giải thích tại sao Greedy chọn C→F→I→T dù C→F tốn 9.

Greedy chọn C vì h(C)=3 thấp nhất trong con của S. Từ C, Greedy tiếp tục F→I→T vì h giảm dần. Greedy không theo dõi g(n) nên không nhận ra C→F đắt. BFS bỏ qua h(n) hoàn toàn, khám phá theo lớp (số cạnh), không bị ảnh hưởng bởi h(C)=3.

Câu 3. Đường tối ưu là gì? Thuật toán nào đảm bảo tìm được?

Đường tối ưu: S → A → E → I → T, chi phí = 2+2+3+4 = 11. Không thuật toán nào trong 7 phương pháp trên tìm được. Cần A* (kết hợp g(n)+h(n)) mới đảm bảo tối ưu với heuristic chấp nhận được.

Bài 2

Đồ thị G2 — Hill Climbing & Beam Search

h(n): S=14, A=10, B=11, C=5, D=8, E=7, F=9, G=9, H=4, T=0 | Cạnh: S→A:4, S→B:2, A→C:3, A→D:5, B→E:6, B→F:3, C→G:2, D→G:4, D→H:2, E→H:5, F→H:1, G→T:11, H→T:3

1. Hill Climbing (Steepest Ascent)

Step	Nút hiện tại	h	Các nút con (h)	Quyết định
0	S	14	A(10), B(11)	→ A (10 < 11)
1	A	10	C(5), D(8)	→ C (5 < 8)
2	C	5	G(9) — 9 > 5	KẸT ⚑

⚠ HC dừng tại C (h=5). G là con duy nhất của C với h(G)=9 > 5. Không tìm được T.

2. Beam Search (w = 2)

Step	Beam hiện tại	Mở rộng → con (h)	Beam mới (top‑2)
0	{ S(14) }	A(10), B(11)	{ A(10), B(11) }
1	{ A(10), B(11) }	A→C(5),D(8) ; B→E(7),F(9)	{ C(5), E(7) }
2	{ C(5), E(7) }	C→G(9) ; E→H(4)	{ H(4), G(9) }
3	{ H(4), G(9) }	H→T(0) ; G→T(0)	T tìm thấy! ✓

Bước 1: D(8) và F(9) bị loại vì đứng thứ 3 và 4. H(4) đến từ nhánh B (qua E) — nhánh mà HC đã bỏ qua ngay bước đầu.

Đường đi: S → B → E → H → T | Chi phí: 2+6+5+3 = 16

Câu hỏi — Đáp án

Câu 1. Tại sao HC dừng tại C?

C chỉ có một con là G với h(G)=9 > h(C)=5. Không có con nào cải thiện h nên HC dừng — không tìm được lời giải.

Câu 2. Beam Search thoát được vì sao?

Ở bước 0, Beam giữ lại cả A(10) và B(11) cùng lúc. HC bỏ qua B vì h(B)=11 > h(A)=10. Khi A dẫn đến C (ngõ cụt), nhánh B đã đến H(h=4) rồi T. Chiều rộng w=2 cho phép khám phá song song, tránh bẫy cực tiểu địa phương.

Câu 3. Đường tối ưu là gì? Beam Search có tìm được không?

Đường tối ưu: S → B → F → H → T, chi phí = 2+3+1+3 = 9. Beam bỏ F(h=9) ở bước 1 vì E(h=7) < F(h=9), không khám phá nhánh B→F→H→T. Cần A* để đảm bảo tối ưu.

Bài 3

Truyền giáo & Người ăn thịt người — BFS & Hill Climbing

Trạng thái: (ML, CL, b) — ML/CL = số người bờ trái, b = vị trí thuyền (L/R). Xuất phát: (3,3,L). Đích: (0,0,R). Hợp lệ: (ML=0 hoặc ML≥CL) và (MR=0 hoặc MR≥CR). Nước đi: thuyền chở 1–2 người.

Không gian trạng thái — BFS Tree

Nút indigo = thuộc đường giải BFS. Nút xám đứt = ngõ cụt [×]. Tie-breaking: ML↑ trước, CL↑ sau.

Xuất phát

Đích ✓

Đường giải BFS

Ngõ cụt [×]

Được khám phá

(3,3,L) → (2,2,R) → (3,2,L) → (3,0,R) → (3,1,L) → (1,1,R) → (2,2,L) → (0,2,R) → (0,3,L) → (0,1,R) → (0,2,L) → (0,0,R) ✓

BFS — Bảng khai triển

Step	u	Edge(u)	OPEN (đầu → cuối)
0	—	—	(3,3,L)
1	(3,3,L)	(2,2,R), (3,1,R), (3,2,R)	(2,2,R), (3,1,R), (3,2,R)
2	(2,2,R)	(3,2,L)	(3,1,R), (3,2,R), (3,2,L)
3	(3,1,R)	→(3,2,L)∈OPEN ; →(3,3,L) đã thăm	(3,2,R), (3,2,L)
4	(3,2,R)	→(3,3,L) đã thăm — ngõ cụt	(3,2,L)
5	(3,2,L)	(3,0,R)	(3,0,R)
6	(3,0,R)	(3,1,L)	(3,1,L)
7	(3,1,L)	(1,1,R)	(1,1,R)
8	(1,1,R)	(2,2,L)	(2,2,L)
9	(2,2,L)	(0,2,R)	(0,2,R)
10	(0,2,R)	(0,3,L)	(0,3,L)
11	(0,3,L)	(0,1,R)	(0,1,R)
12	(0,1,R)	(0,2,L), (1,1,L)	(0,2,L), (1,1,L)
13	(0,2,L)	(0,0,R) ✓	—

11 bước (6 lượt sang phải, 5 lượt về trái). 13 nút được mở rộng.

Bước	Trạng thái	Hành động
0	(3,3,L)	Xuất phát
1	(2,2,R)	→1M1C
2	(3,2,L)	←1M
3	(3,0,R)	→2C
4	(3,1,L)	←1C
5	(1,1,R)	→2M
6	(2,2,L)	←1M1C
7	(0,2,R)	→2M
8	(0,3,L)	←1C
9	(0,1,R)	→2C
10	(0,2,L)	←1C
11	(0,0,R)	→2C → ĐÍCH ✓

Hill Climbing — h(ML, CL, b) = ML + CL

Step	Trạng thái	h	Kề hợp lệ (h)	Quyết định
0	(3,3,L)	6	(2,2,R):4, (3,1,R):4, (3,2,R):5	→(2,2,R)
1	(2,2,R)	4	(3,2,L):5 — 5 > 4	DỪNG ⚑

⚠ HC dừng tại (2,2,R). Để tiếp tục phải đưa thuyền trở về (h tăng) — HC từ chối và không có OPEN list để thử hướng khác.

Câu hỏi — Đáp án

Câu 1. BFS cần bao nhiêu bước? Bao nhiêu trạng thái duyệt?

BFS cần 11 bước để đến đích, duyệt qua 13 trạng thái. Đây là lời giải ít bước nhất vì BFS đảm bảo tìm đường ngắn nhất theo số bước.

Câu 2. HC dừng ở đâu? Tại sao?

HC dừng tại (2,2,R) (h=4). Để tiếp tục phải đưa thuyền ngược về làm h tăng lên 5 — HC từ chối. HC không có OPEN list để thử hướng khác.

Câu 3. Tại sao HC đặc biệt không phù hợp cho bài toán này?

Bài toán bắt buộc có bước đưa thuyền ngược chiều (h tạm thời tăng) để tiếp tục vận chuyển — đây là dấu hiệu của bề mặt heuristic có cực tiểu địa phương không phải cực tiểu toàn cục. HC từ chối những bước "xấu hơn" đó; BFS không bị ảnh hưởng vì không dùng heuristic để định hướng.

Bài 4

Lập kế hoạch Cứu trợ Lũ lụt — Hill Climbing & Greedy

h(n): S=9, A=5, B=7, C=6, D=3, E=6, F=5, G=4, H=4, I=2, T=0 | Cạnh: S→A:2, S→B:3, S→C:4, A→D:1, A→E:3, B→E:2, B→F:4, C→F:2, C→G:5, D→H:6, D→G:7, E→G:3, E→H:2, F→H:3, F→I:4, G→I:2, G→T:4, H→T:5, I→T:2

Ký hiệu	Địa điểm
S	Trung tâm Điều phối (Xuất phát)
A	Thị trấn Phố Cũ
B	Đồn Biên phòng Bắc
C	Bến Xe Liên Tỉnh
D	Cầu Ngập Khe Đá (cực tiểu địa phương)
E	Trường THPT Hòa Bình
F	Điểm Tiếp tế Nam
G	Ngã Tư Bản Đồng
H	Trạm Y tế Vùng Cao
I	Chốt Kiểm soát Lũ
T	Xã Bị Cô Lập (Đích)

Đồ thị bài toán (có hướng, trọng số = giờ)

S — Xuất phát (h=9)

T — Đích (h=0)

Nút trung gian — số trên cạnh = giờ

1. Hill Climbing (Steepest Ascent)

Step	Nút hiện tại	h	Các nút con (h)	Quyết định
0	S	9	A(5), B(7), C(6)	→ A (h=5)
1	A	5	D(3), E(6)	→ D (h=3)
2	D	3	G(4), H(4) — đều > 3	KẸT ⚑

⚠ HC không tìm được đường đến T. Cầu Ngập Khe Đá (D, h=3) là cực tiểu địa phương: tuy D gần đích theo đường chim bay, đường bộ vượt cầu ngập tốn 6–7 giờ. HC không có OPEN list để backtrack.

2. Greedy Best-First Search

OPEN = hàng đợi ưu tiên sắp xếp tăng dần theo h(n). Ký hiệu: X^h = nút X với h(X) = h.

Step	u	Edge(u)	OPEN (h↑)
0	—	—	S⁹
1	S	A⁵, C⁶, B⁷	A⁵, C⁶, B⁷
2	A	D³, E⁶	D³, C⁶, E⁶, B⁷
3	D	G⁴, H⁴	G⁴, H⁴, C⁶, E⁶, B⁷
4	G	I², T⁰	T⁰, I², H⁴, C⁶, E⁶, B⁷
5	T	GOAL ✓	—

Bước 3: G và H cùng h=4 → G trước H (alphabet). Greedy cũng bị h(D)=3 thu hút nhưng khác HC — Greedy có OPEN list nên mở rộng tiếp sang G→T. Đoạn D→G tốn 7 giờ (đắt nhất đồ thị) khiến tổng đường đi xa hơn tối ưu nhiều.

Đường đi: S → A → D → G → T | Thời gian: 2+1+7+4 = 14 giờ (không tối ưu)

Câu hỏi — Đáp án

Câu 1. Hill Climbing kẹt ở đâu? Tại sao không tìm được đường?

HC dừng tại Cầu Ngập Khe Đá (D, h=3). Tất cả con của D (G và H, đều h=4) có h cao hơn h(D)=3. HC không có cơ chế backtrack — bị tắc tại cực tiểu địa phương do heuristic deceptive: D trông gần đích theo đường chim bay nhưng thực tế đường bộ bị lầy hoàn toàn.

Câu 2. Greedy tìm được đường nào? Đường đó tốt không?

Greedy tìm: S → A → D → G → T, tổng 14 giờ. Đường này đi qua D→G tốn 7 giờ — đoạn đắt nhất đồ thị. Greedy không phải tối ưu.

Câu 3. Có bao nhiêu đường tối ưu? Cần thuật toán nào?

Có 3 đường tối ưu, đều đạt 12 giờ:

Đường đi	Chi phí
S → A → E → H → T	2+3+2+5 = 12h
S → B → E → H → T	3+2+2+5 = 12h
S → C → F → I → T	4+2+4+2 = 12h

Cần A* (kết hợp g(n)+h(n)) để đảm bảo tối ưu và không bị cực tiểu địa phương đánh lừa.