Chuyển tới nội dung chính
Z Graph & Pathfinding

Trình trực quan hóa thuật toán tìm đường A*

Tìm đường A* tương tác trên lưới ô vuông với heuristic Manhattan — vẽ tường chắn, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình tìm kiếm. Chạy hoàn toàn trên trình duyệt.

Miễn phí Không cần đăng ký Chạy trên trình duyệt Tôn trọng riêng tư Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

Mã giả

Cách dùng

  1. 1 Vẽ tường chắn bằng cách nhấn và kéo chuột; kéo điểm bắt đầu màu xanh lá hoặc điểm đích màu đỏ để đổi vị trí.
  2. 2 Nhấn Play để xem A* tiến về phía đích bằng cách sử dụng heuristic khoảng cách.
  3. 3 Dùng Maze để tạo chướng ngại vật tức thì, hoặc dùng Step để chạy qua từng nút một.
  4. 4 Chú ý xem A* duyệt qua ít ô như thế nào so với Dijkstra hoặc BFS.

Vì sao dùng công cụ này

  • Xem cách heuristic Manhattan kéo quá trình tìm kiếm đi thẳng về phía đích.
  • A* tìm ra đường đi ngắn nhất trong khi chỉ duyệt qua ít nút hơn nhiều so với tìm kiếm không có thông tin.
  • Chuyển đổi qua lại giữa công cụ này và các trình trực quan hóa Dijkstra / BFS để so sánh cách duyệt.
  • Chạy hoàn toàn trên trình duyệt của bạn. Không cần đăng ký, không cần tải lên.

Câu hỏi thường gặp

Thuật toán A* là gì?

A* (đọc là A-star) là một thuật toán tìm đường theo kiểu best-first, sắp xếp các nút biên (frontier) theo f = g + h, trong đó g là chi phí tính từ điểm bắt đầu và h là ước lượng heuristic của chi phí đến đích.

Công cụ này sử dụng heuristic nào?

Khoảng cách Manhattan (|Δrow| + |Δcol|), một heuristic chấp nhận được (admissible) trên lưới 4 hướng — nó không bao giờ ước lượng quá cao, nên A* luôn đảm bảo tìm ra đường đi ngắn nhất.

Độ phức tạp thời gian của A* là gì?

Trong trường hợp xấu nhất là O(E log V) giống Dijkstra, nhưng với một heuristic tốt, trên thực tế nó duyệt qua ít nút hơn rất nhiều.

Khi nào A* tốt hơn Dijkstra?

Bất cứ khi nào bạn có một đích duy nhất và một heuristic hữu ích. A* tập trung tìm kiếm về phía đích; còn Dijkstra thì duyệt đều theo mọi hướng.

Trình trực quan hóa thuật toán tìm đường A* là gì?

Trình trực quan hóa thuật toán tìm đường A* mô phỏng động thuật toán tìm kiếm A* trên một lưới ô vuông. A* sắp xếp thứ tự các nút biên (frontier) theo f = g + h (chi phí đã đi cộng với heuristic khoảng cách Manhattan), nhờ đó nó tìm kiếm theo hướng đến đích và tìm ra đường đi ngắn nhất trong khi chỉ cần duyệt qua ít ô hơn nhiều so với các thuật toán tìm kiếm không có thông tin (uninformed search).

Tính năng

Hoạt ảnh từng bước

Xem tập mở (open set) mở rộng dần về phía đích, được dẫn dắt bởi f = g + h.

Độ phức tạp

Phụ thuộc vào heuristic (trường hợp xấu nhất là theo cấp số mũ); heuristic khả chấp → đường đi tối ưu. Không gian bộ nhớ: O(V).

Riêng tư 100%

Chạy hoàn toàn trong trình duyệt của bạn — không có gì được tải lên.

Ví dụ

Input

grid with start, goal, obstacles

Output

expand lowest f = g + h toward goal → optimal path (with an admissible heuristic)

Trường hợp sử dụng

  1. 1

    Tìm đường trên lưới

    Tìm tuyến đường ngắn nhất vòng qua chướng ngại vật trong game và bản đồ.

  2. 2

    Heuristic so với Dijkstra

    Xem cách một heuristic tốt giúp A* khám phá ít nút hơn so với Dijkstra.

  3. 3

    Tính khả chấp & tính tối ưu

    Tìm hiểu lý do một heuristic khả chấp đảm bảo đường đi tối ưu.

Tóm tắt

Công cụ trực quan hóa thuật toán tìm đường A* của Zerethon mô phỏng từng bước tìm kiếm A* trên lưới ngay trong trình duyệt của bạn, mở rộng các nút theo thứ tự f = g + h (chi phí đã đi cộng với ước lượng heuristic đến đích). Với một heuristic khả chấp (admissible), A* tìm ra đường đi tối ưu trong khi thường khám phá ít nút hơn nhiều so với Dijkstra. Thời gian chạy phụ thuộc vào heuristic (trường hợp xấu nhất là theo cấp số mũ); không gian bộ nhớ là O(V) cho tập mở (open set) và tập đóng (closed set).

Danh mục
Thuật toán
Giá
Miễn phí
Quyền riêng tư
Chạy trên trình duyệt
Đăng ký
Không cần

Tài liệu tham khảo

Quyền riêng tư

Dữ liệu của bạn không bao giờ rời khỏi trình duyệt trừ khi được nêu rõ. Trình trực quan hóa thuật toán tìm đường A* chạy hoàn toàn phía client — không tải lên máy chủ, không ghi log, không theo dõi dữ liệu bạn nhập.

Mới làm quen? Đọc giải thích từng bước kèm phân tích Big-O: Tìm hiểu Graph Algorithms →

Xây dựng, chia sẻ và phát triển trên Zerethon Social

Đăng ký miễn phí. Kiếm điểm, sưu tầm thành tựu và kết nối với nhà sáng tạo khắp thế giới.

Đăng ký miễn phí