Tìm kiếm ưu tiên chiều rộng
Tìm kiếm ưu tiên chiều rộng (BFS)
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)
Mã:
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 đây là một số bổ đề, hướng chứng minh:
Ký hiệu S(s,v) là số cạnh ít nhất trên một đường đi nào đó giữa s và v, giá trị này còn được gọi là khoảng cách giữa s và v. Nếu không có đường đi thì d(s,v)= \infty . Một đường đi từ s đến v có số cạnh là S(s,v) được gọi là đường đi ngắn nhất (theo số cạnh) giữa s và v.
Bổ đề 1: Với mọi cạnh (u,v) thuộc G, ta có S(s,v)= S(s,u)+1
Bổ đề 2: Sau khi kết thúc thuật toán loang, với mọi đỉnh v giá trị d[v] trả về thỏa d[v] \geq S(s,v)
Chứng minh: có thể quy nạp theo số phép toán đẩy vào hàng đợi
Bổ đề 3: Giả sử trong qúa trình thực hiện thuật toán loang, hàng đợi Q chứa các đỉnh v1, v2, ... , vr, với v1 ở đầu hàng đợi và vr ở cuối. Thế thì d[vr] ≤ d[v1] + 1 và d[vi ] ≤ d[vi+1] với mọi i = 1, 2,..., r - 1.
Chứng minh: có thể quy nạp theo số phép toán hàng đợi
Hệ qủa 1: Giả sử đỉnh vi và vj được đưa vào hàng đợi trong qúa trình thực hiện thuật toán loang, và vi được đưa vào trước vj, thế thì d[vi] ≤ d[vj] ngay khi vj được đưa vào hàng đợi
Chứng minh: trực tiếp từ bổ đề 3 và tính chất mỗi đỉnh chỉ nhận giá trị d nhiều nhất một lần
Định lý: Sau khi kết thúc thuật toán loang, d[v]= S(s,v) với mọi đỉnh v thuộc G
Chứng minh:
Phản chứng. Gọi v là đỉnh có giá trị S(s,v) nhỏ nhất mà bị gán sai nhãn d[v], từ đó suy ra điều mâu thuẫn
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
, những bài toán cơ bản cho newbie đang học thuật
*
