Trong nhiều bài toán thực tế, giả định này không còn đúng. Các ô trên bản đồ có thể đại diện cho những loại địa hình khác nhau, với mức độ tốn kém khác nhau khi di chuyển. Lúc này, bài toán không còn là “đường ngắn nhất”, mà trở thành đường đi có tổng chi phí thấp nhất.
Thuật toán Dijkstra được thiết kế chính xác cho kịch bản này.
1. Bài toán tìm đường với trọng số (weighted pathfinding)
Xét một mê cung dạng lưới, trong đó mỗi ô đi được có một chi phí xác định:
- Đường thường (road): chi phí = 1
- Cát (sand): chi phí = 3
- Bùn (mud): chi phí = 7
- Tường / nước: không thể đi qua
Khi agent di chuyển từ ô này sang ô khác, tổng chi phí sẽ tăng thêm theo loại địa hình của ô mà agent bước vào. Mục tiêu của bài toán là tìm một đường đi từ điểm bắt đầu đến điểm đích sao cho tổng chi phí là nhỏ nhất, không nhất thiết là số bước ít nhất.
Điều này làm cho BFS không còn phù hợp, và A* chỉ hoạt động đúng nếu heuristic được thiết kế cẩn thận. Dijkstra là lựa chọn nền tảng và an toàn nhất trong trường hợp này.
2. Ý tưởng cốt lõi của thuật toán Dijkstra
Dijkstra là một thuật toán tìm đường trên đồ thị có trọng số không âm. Mỗi trạng thái (ô trong mê cung) được xem như một node, và mỗi bước di chuyển là một cạnh có trọng số.
Thuật toán duy trì một giá trị dist[v] – chi phí nhỏ nhất đã biết để đi từ điểm bắt đầu đến node v. Ban đầu:
dist[start] = 0- Tất cả các node khác có
dist = ∞
Ở mỗi bước, Dijkstra chọn node chưa xử lý có dist nhỏ nhất, đánh dấu nó là đã xử lý, và thử cải thiện (relax) các node lân cận.
for each neighbor v of u:
if dist[u] + cost(v) < dist[v]:
dist[v] = dist[u] + cost(v)
parent[v] = u
Quá trình này lặp lại cho đến khi:
- Đích được xử lý (đã tìm ra đường đi rẻ nhất), hoặc
- Không còn node nào có thể mở rộng
3. So sánh Dijkstra với BFS và A*
| Thuật toán | Tối ưu | Có trọng số? | Heuristic |
|---|---|---|---|
| BFS | Số bước | Không | Không |
| A* | Số bước / chi phí | Có | Có |
| Dijkstra | Tổng chi phí | Có | Không |
Có thể xem Dijkstra là một phiên bản tổng quát của BFS: khi mọi cạnh đều có trọng số bằng nhau, Dijkstra sẽ hoạt động giống hệt BFS.
4. Trực quan hóa Dijkstra trên mê cung có địa hình
Trong demo bên dưới, mỗi ô trong mê cung không chỉ là “đi được” hay “không đi được”, mà còn mang một loại địa hình với chi phí khác nhau. Bạn có thể trực tiếp tô địa hình lên mê cung trước khi chạy thuật toán.
- Dijkstra sẽ luôn mở rộng ô có tổng chi phí nhỏ nhất trước.
- Agent chỉ có một thực thể duy nhất và di chuyển liên tục trên mê cung.
- Khi thuật toán kết thúc, đường đi cuối cùng sẽ được vẽ rõ ràng.
Dijkstra Weighted Maze Demo
Demo này giúp làm rõ một điểm quan trọng: đường đi tối ưu theo chi phí có thể dài hơn về mặt hình học, nhưng vẫn là lựa chọn tốt hơn về tổng chi phí.
5. Kết luận
Dijkstra là thuật toán nền tảng cho bài toán tìm đường có trọng số, đóng vai trò quan trọng trong nhiều hệ thống thực tế như: bản đồ giao thông, game, robot, và hệ thống định tuyến.
Trong bài tiếp theo, chúng ta sẽ kết hợp ưu điểm của Dijkstra và A* để xây dựng Weighted A*: một thuật toán vừa nhanh hơn, vừa có khả năng kiểm soát mức độ tối ưu thông qua trọng số heuristic.
Bình luận