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.
Click & drag on the grid to draw walls · drag the green and red squares to move start / goal · then press Play. Want a challenge? Hit Tự chơi thử and solve the maze by hand.
Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.
Mã giả
Time · Space
Cách dùng
- 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 Nhấn Play để xem A* tiến về phía đích bằng cách sử dụng heuristic khoảng cách.
- 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 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).
Trình trực quan hóa thuật toán tìm đường A* là công cụ thuật toán miễn phí của Zerethon Tools. 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. Chạy hoàn toàn trong trình duyệt — không đăng ký, không tải lên.
- 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
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 →
So sánh
Công cụ liên quan
Trình trực quan hóa thuật toán Dijkstra
Trực quan hóa tìm đường Dijkstra trên lưới ô — vẽ tường, 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. Hoạt động ngay trên trình duyệt.
Mở công cụTrình trực quan Tìm kiếm theo chiều rộng (BFS)
Tìm kiếm theo chiều rộng tương tác trên lưới ô — vẽ tường, di chuyển điểm bắt đầu/đích, sinh mê cung, xem từng bước mở rộng theo từng lớp. Chạy ngay trên trình duyệt.
Mở công cụTrình trực quan hóa Tìm kiếm theo chiều sâu (DFS)
Tìm kiếm theo chiều sâu tương tác trên lưới ô vuông — vẽ tường, di chuyển điểm bắt đầu/đích, tạo mê cung, chạy từng bước quá trình khám phá đào sâu. Chạy ngay trong trình duyệt.
Mở công cụTrình mô phỏng Bubble Sort
Mô phỏng bubble sort có hoạt ảnh với các nút điều khiển từng bước, tốc độ, dữ liệu đầu vào tùy chỉnh, bộ đếm so sánh/hoán đổi trực tiếp và pseudocode. Chạy hoàn toàn trong trình duyệt của bạn.
Mở công cụ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.