Tìm kiếm ưu tiên chiều rộng - Một số bài tập áp dụng
Ngô Minh Đức
Trình bày sơ lược
Tìm kiếm ưu tiên chiều rộng , hay còn gọi là “loang”, là một trong những thuật toán duyệt
đồ thị đơn giản nhất. Ý tưởng của nó được sử dụng trong nhiều thuật toán, chẳng hạn thuật
toán Prim tìm cây khung nhỏ nhất, thuật toán Dijkstra tìm đường đi ngắn nhất, v.v...
Loang chủ yếu được sử dụng để tìm đường đi ngắn nhất theo số cạnh giữa hai đỉnh của
một đồ thị. Ta hình dung từ một đỉnh nguồn s, ban đầu thuật toán loang khám phá các đỉnh
đến được từ s, đó là lớp thứ nhất, sau đó lại khám phá các đỉnh chưa thăm và đến được từ
lớp thứ nhất, đó là lớp thứ hai, v.v... Nghĩa là các đỉnh đến từ có khoảng cách k từ s luôn
được khám phá trước các đỉnh có khoảng cách k+1 từ s.
Sau đây là mã giả của thuật toán loang: (thực ra là mã Pascal)
For i:=1 to n do {n là số đỉnh}
Trace[i]:=0;
Trace[s]:=-1; {s là đỉnh nguồn}
d[s]:=0; {d[i] là khoảng cách từ nguồn đến đỉnh i}
i:=1; j:=1; q[i]:=s; {q là hàng đợi}
While i<=j do
Begin
For k Adj[q[i]] do
If Trace[k]=0 then
Begin
Trace[k]:=q[i];
D[k]:=D[q[i]]+1;
Inc(j);
q[j]:=k;
End;
Inc(i);
End;
Về mặt trực quan, ta thấy thuật toán loang luôn tìm được đường đi ngắn nhất theo số cạnh
giữa hai đỉnh của một đồ thị. Nhưng thực ra, cũng cần phải chứng minh điều này. Dưới

phép biến đổi ít nhất để từ từ nguồn thu được từ đích.
Giới hạn: từ điển chứa không qúa 200 từ
Hướng dẫn:đây là bài toán loang đơn giản. Mỗi từ là một đỉnh của đồ thị, nhưng không cần
xây dựng đồ thị một cạnh tường minh mà dùng một hàm để kiểm tra trực tiếp (i,j) có phải
là cạnh của đồ thị hay không
Bộ sưu tập (Đề thi quốc gia bảng B 2005)
Một bộ sưu tập tiền xu cổ là có giá trị phải gồm không ít hơn Zo đồng vàng, S0 đồng bạc,
M0 đồng đồng. Cho biết các qui tắc đổi gói tiền (Z1, S1, M1) sang (Z2, S2, M2). Mỗi hội
viên (hội sưu tập tiền cổ) không được giữa qúa 4 đồng tiền mỗi loại. Các đồng tiền nhận
được sau mỗi lần đổi được gộp lại với các đồng tiền mà hội viên đang có để thành một bộ
sưu tập mới và có thể được sử dụng để đổi trong những lần sau nếu cần.
Yêu cầu: Cho số lượng Z,S,M các đồng tiền mà Alibaba có ban đầu và các quy tắc đổi tiền.
Hãy chỉ ra một phương án đổi tiền nào đó để Alibaba có được một bộ sưu tập có giá trị.
Hướng dẫn: đây cũng là một bài toán loang đơn giản. Mỗi đỉnh của đồ thị là một bộ
(Z,S,M), do điều kiện 0≤Z,S,M≤4 nên chỉ có 53=125 đỉnh. Từ các quy tắc đổi tiền giúp ta
xác định được các cạnh của đồ thị. Chú ý cài đặt cẩn thận để đạt kết qủa tốt.
Đường kính của cây
Đường kính của cây T=(V,E) được cho bởi giá trị
max(d(u,v)), với u,v T
nghĩa là giá trị lớn nhất trong các khoảng cách ngắn nhất trên cây đó
Chỉ ra một thuật toán hiệu qủa để tính đường kính của một cây.
Hướng dẫn: Loang từ một đỉnh bất kỳ s. Giả sử u là đỉnh xa nhất khi đi từ s. Lại tiến hành
loang từ u. Giả sử v là đỉnh xa nhất khi đi từ u. Thế thì u->v chính là đường kính của cây
Trạng thái xa nhất
Trò chơi 8-puzzle gồm một khay hình vuông với 8 mảnh vuông được đặt lên 8 ô vuông. Ô
vuông còn lại rỗng. Mỗi mảnh có ghi một con số. Một mảnh kề với ô rỗng có thể được đẩy
sang ô rỗng này. Một ván chơi bao gồm trạng thái bắt đầu và trạng thái kết thúc. Người
chơi phải biến đổi đến trạng thái kết thúc bằng cách di chuyển các mảnh vuông. Bài toán 8-
puzzle yêu cầu phải biến đổi với số bước ít nhất
Nhưng trong bài toán này (bài toán trạng thái xa nhất), bạn được cho một trạng thái bắt

chuyển được thì đưa ra số -1.
Hướng dẫn: Xây dựng đồ thị G=(V,E) với mỗi đỉnh là một cặp (x,y) thể hiện vị trí đang
đứng của 2 quân cờ. Tập cạnh có dạng ((x,y),(x,y’)) nếu ey,y’</SUB>=Cx hoặc ((x,y),
(x’,y)) nếu ex,x’</SUB>=Cy. Với mô hình đồ thị trên thì bài toán của chúng ta sẽ là: tìm
đường đi ngắn nhất (theo số cạnh) từ đỉnh (1,2) đến đỉnh có dạng (p,n) hoặc (n,q). Đến đây
ta có thể dùng thuật toán loang để giải quyết bài toán.
Một số bài tập khác
1.Mã trên bàn cờ 5x5
Có các quân mã trắng và đen trên một bàn cờ 5x5. Có 12 quân mỗi loại và chỉ có một ô
rỗng. Tại mỗi thời điểm, một quân mã có thể di chuyển đến một ô rỗng (cách đi của quân
mã như luật cờ vua thông thường).
Cho một trạng thái ban đầu của bàn cờ, hãy xác định số bước đi ít nhất để đạt được trạng
thái sau: