Cố định
Trong hàng đợi
Cạnh đã xét

  • Hiện tại
  • Trong hàng đợi
  • Cố định
  • Đường đi
  • Ước lượng đường thẳng
Nhấp vào đỉnh để đặt

Tìm hiểu thêm về tìm kiếm A*

Tìm kiếm A*

Tìm kiếm A* tìm đường đi ngắn nhất từ điểm xuất phát đến đích, giống thuật toán Dijkstra, nhưng nó biết đại khái đích ở đâu. Mỗi đỉnh nhận một ước lượng quãng đường còn lại, tức đường thẳng đến đích, và quá trình tìm kiếm luôn tiếp tục từ đỉnh có khoảng cách đến lúc đó cộng ước lượng nhỏ nhất. Nhấp vào một đỉnh để xuất phát từ đó, chọn đích, rồi đi từng bước để thấy quá trình tìm kiếm hướng về đích, để lại nguyên vẹn cả những góc lớn của đồ thị. Nhấn Phát để xem quá trình tìm kiếm, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Nhấp vào một đỉnh để chọn làm điểm xuất phát; chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác để chọn làm đích. Số trên mỗi cạnh là độ dài của cạnh, số trên mỗi đỉnh là khoảng cách tìm được đến lúc đó, còn đường nét đứt là ước lượng theo đường thẳng của quãng đường còn lại. Hàng dưới đồ thị là hàng đợi, điểm thấp nhất đứng đầu, kèm điểm của từng đỉnh: khoảng cách đến lúc đó cộng ước lượng. Đồ thị mới tạo một đồ thị khác; chọn số đỉnh và số cạnh. Khi bảng đang được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.

Cách nó hoạt động

  1. Nhấp vào một đỉnh để chọn làm điểm xuất phát. Chuyển thao tác nhấp sang Đích rồi nhấp vào đỉnh khác để chọn làm đích.
  2. Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình tìm kiếm.
  3. Theo dõi điểm trong hàng đợi và ước lượng đường thẳng nét đứt. Cuối cùng, so sánh số đỉnh A* cần với thuật toán Dijkstra.

Cách tìm kiếm A* hoạt động

Gán cho điểm xuất phát khoảng cách 0 và đưa nó vào hàng đợi. Mỗi đỉnh trong hàng đợi có một điểm: khoảng cách đến lúc đó cộng ước lượng quãng đường còn lại. Lặp lại: lấy đỉnh có điểm thấp nhất và đánh dấu khoảng cách của nó là cố định. Nếu đó là đích thì dừng. Nếu không, với mỗi đỉnh kề chưa cố định, cộng độ dài cạnh vào khoảng cách của đỉnh đang xét; nếu kết quả ngắn hơn khoảng cách hiện có của đỉnh kề, hạ nó xuống, ghi nhớ đỉnh đang xét là đường đến đó, và đưa đỉnh kề vào hàng đợi với điểm mới.

Vì sao ước lượng không được quá dài

A* tìm được đường đi ngắn nhất miễn là ước lượng không bao giờ cho rằng đích xa hơn thực tế: một ước lượng chấp nhận được. Đường thẳng là một ước lượng như vậy, vì không con đường nào giữa hai nơi ngắn hơn đường thẳng. Ước lượng quá dài có thể khiến A* bỏ qua tuyến tốt nhất; ước lượng bằng 0 ở mọi nơi biến A* thành thuật toán Dijkstra, an toàn nhưng tìm theo mọi hướng. Ước lượng càng tốt, A* càng cần ít đỉnh. Trong ứng dụng, mỗi cạnh dài đúng bằng độ dài được vẽ, làm tròn lên, nên đường thẳng là một ước lượng an toàn.

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

Tìm kiếm A* là gì?

Một thuật toán tìm đường, tìm đường đi ngắn nhất từ điểm xuất phát đến đích. Nó hoạt động giống thuật toán Dijkstra, nhưng sắp hàng đợi theo khoảng cách đến lúc đó cộng ước lượng quãng đường còn lại, nên nó hướng về đích thay vì lan ra mọi hướng.

Heuristic chấp nhận được là gì?

Một ước lượng khoảng cách đến đích không bao giờ dài hơn khoảng cách ngắn nhất thật. Với ước lượng chấp nhận được, A* luôn tìm được đường đi ngắn nhất. Khoảng cách đường thẳng trên bản đồ là ví dụ kinh điển.

A* có nhanh hơn thuật toán Dijkstra không?

Thường là có, khi bạn cần đường đến một đích và có ước lượng tốt: A* cố định ít đỉnh hơn, vì các đỉnh nằm xa đích nhận điểm cao. Với ước lượng bằng 0, nó làm đúng như thuật toán Dijkstra. Thuật toán Dijkstra là lựa chọn tốt hơn khi bạn cần khoảng cách đến mọi đỉnh.

A* được dùng ở đâu?

Trong trò chơi điện tử để di chuyển nhân vật vòng qua chướng ngại vật, trong công cụ lập lộ trình, trong lập kế hoạch chuyển động robot, và trong các bộ giải câu đố như trò chơi 15 ô, nơi ước lượng đếm xem các ô cách vị trí của chúng bao xa.

Đồ thị của tôi có bị gửi đi đâu không?

Không. Đồ thị được tạo và tìm kiếm ngay trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Tới trình chỉnh sửa