2 Thuật toán tìm đường đơn giản áp dụng trong đồ thị


Định nghĩa: Trong đồ thị, tìm kiếm nghĩa là di chuyển theo các cạnh trong đồ thị đó để tìm ra các nút trong đồ thị.



Ví dụ chúng ta có 1 đồ thị như hình trên: nút khởi đầu là nút số 2 và chúng ta muốn tìm đường đi ngắn nhất tới nút số 7. Để tìm ra đường đi ngắn nhất, chúng ta có thể áp dụng 2 thuật toán đơn giản sau đây:


  1. Breadth-first search
  2. Depth-first search

Breadth-first search


  • Mục tiêu: tìm ra đường đi ngắn nhất từ nút số 2 tới nút số 7
  • Giải thích thuật toán: Thuật toán sẽ tìm đường đi từ nút S1 (nút khời đầu) tới các nút kết nối với nó (có độ dài k). Sau đó tìm đường đi từ các nút đó tới những nút con khác (độ dài k+1)
  • Lợi thế: Đảm bảo tìm ra đường đi ngắn nhất giữa 2 nút.
  • Bất lợi: Tốn bộ nhớ (do áp dụng hàng đợi queue)
  • Giải thích bằng đồ hoạ:

Ví dụ: tìm đường đi ngắn nhất từ nút 2 tới nút 7


B1: Tìm tất cả các nút con kết nối với 2 và đánh dấu khoảng cách k = 1



            B2: Với mỗi nút vừa tìm thấy, tìm các nút kết nối với chúng với điều kiện đó là những nút chưa được tìm thấy (vd: 3, 6, 7), những nút tìm thấy sẽ có khoảng cách là k+1



Khoảng cách ngắn nhất giữa nút 2 và nút 7 là 2.


Đường đi: N2->N5->N7


Cây được tạo bởi Bread-first search:


Depth-first search


  • Mục tiêu: tìm ra đường đi từ nút số 2 tới nút số 7
  • Giải thích thuật toán: Thuật toán sẽ tìm 1 nút nối với nút khởi đầu, từ đó sẽ tìm tới những nút khác cho tới khi tìm ra nút kết thúc
  • Lợi thế: Không tốn bộ nhớ (do áp dụng stack)
  • Bất lợi: Không đảm bảo sẽ tìm ra được đường ngắn nhất
  • Giải thích:

Ví dụ: tìm đường đi ngắn nhất từ nút 2 tới nút 7 


      B1: Chọn 1 nút kết nối với nút khởi đầu (nút 2)



B2: Tại nút mới tìm thấy, tìm nút con kết nối với nút đó



B3: Lặp lại bước 2



B4: Tuy nút 4 kết nối với nút 2, nhưng do nút 2 đã được “tìm thấy”, thuật toán sẽ quay về nút 3 để tìm các nút con khác kết nối với nó, trong đồ thị trên các nút 3, 1 không còn nút con nào khác nên thuật toán sẽ quay về nút 2 và đi tới nút 5.



B5: Lặp lại bước 2. (Chú ý: depth-first search có khả năng tìm ra đường ngắn nhất chứ không phải là không thể nhưng điều này tuỳ thuộc vào kích thước của đồ thị, số nút con của mỗi nút, v..v...). Trong trường hợp này chúng ta sẽ giả sử nó tìm ra nút 6 trước nút 7.



B6: Lặp lại bước 2



Thuật toán đã tìm ra đường đi từ nút 2 tới nút 7, nhưng không đảm bảo nó là đường ngắn nhất (Trong trường hợp này khoảng cách giữa nút 2 và 7 là 3).


Cây được tạo bởi Depth-first search: 


Kết: Đây là 2 thuật toán khá đơn giản được áp dụng để tìm ra đường đi giữa các nút trong đồ thị. Từ những thuật toán trên, chúng ta có thể điều chỉnh để tạo ra 1 thuật toán tìm kiếm tốt hơn là Best-first search và A* Search (Áp dụng priority queue và heuristic để tăng hiệu quả của thuật toán) với lợi thế không tốn bộ nhớ của Depth-first search và vẫn đảm bảo tìm ra đường đi ngắn nhất của Breadth-first search.