Là A * thuật toán pathfinding tốt nhất?

Question

Người ta thường nói rằng A * là thuật toán tốt nhất để giải quyết các vấn đề về đường dẫn.

Có tình huống nào khi A * là không thuật toán tốt nhất để tìm giải pháp?

Làm thế nào tốt là A * so với BFS, DFS, UCS, vv?

Answer 1

A * là đặc biệt vì có thể được biến thành các thuật toán con đường tìm hiểu khác bằng cách chơi với nó như thế nào đánh giá các nút và các chẩn đoán nó sử dụng. Bạn có thể làm điều này để mô phỏng của Djikstra, tìm kiếm tốt nhất đầu tiên, tìm kiếm hơi thở đầu tiên và chiều sâu đầu tiên.

Hơn nữa, nó thường dễ dàng để tăng tốc độ nó lên. Ví dụ nếu bạn nhân một heuristic chấp nhận được bởi một hằng số, c, bạn có thể đảm bảo rằng chi phí của chuỗi kết quả của các nút không quá c lần kết quả tối ưu.

Ví dụ, hãy awesome paper này bởi Ian Davis (viết cho Star Trek hạm đội). A * được sử dụng với một tập hợp phân cấp các điểm tham chiếu, dẫn đến đường đi thô. THÌ, để làm mịn đường dẫn, chúng chạy lại A * trên một biểu đồ mới, được tạo ra có chứa các nút trên đường dẫn và những đường dẫn gần đó để có được một con đường hợp lý hơn. Cuối cùng, họ chạy dải cao su để loại bỏ các nút dư thừa.

Vì vậy, A * không phải là giải pháp cho mọi thứ, nhưng nó là một công cụ rất linh hoạt.

Answer 2

Câu trả lời ngắn gọn là có, có những tình huống trong đó A * không phải là thuật toán tốt nhất để giải quyết một vấn đề. Tuy nhiên, có một số cách để đánh giá những gì cấu thành thuật toán tốt nhất để tìm giải pháp.

Nếu bạn đang cân nhắc tốt nhất về hiệu suất của nhiều tìm kiếm từ một nguồn duy nhất để nhiều điểm đến, sau đó bạn nên xem xét sử dụng một cách tiếp cận phù hợp hơn (Dijkstra's algorithm).

Nếu bạn đang cân nhắc tốt nhất về hiệu suất, sau đó trong một số trường hợp đặc biệt DFS và BFS sẽ tốt hơn đáng kể A *. Từ kinh nghiệm quá khứ, điều này xảy ra đối với các đồ thị rất nhỏ, gần như tầm thường, nhưng sẽ yêu cầu kiểm tra cẩn thận và lược tả để đưa ra một tuyên bố mạnh mẽ hơn.

Nếu bạn đang cân nhắc tốt nhất về con đường dài, đó là bao lâu con đường cuối cùng được tạo bởi các thuật toán, sau đó A * tương đương với bất kỳ thuật toán tìm kiếm tối ưu khác.

Nếu bạn đang cân nhắc tốt nhất về đầy đủ, có nghĩa là, sẽ thuật toán luôn tìm thấy một con đường đến mục tiêu nếu một con đường như vậy tồn tại. Nếu vậy, thì A * tương đương với bất kỳ thuật toán hoàn chỉnh nào khác (ví dụ, tìm kiếm theo chiều rộng).

Nếu bạn đang cân nhắc tốt nhất trong trường hợp một số các trọng trong đồ thị dưới là âm, sau đó bạn sẽ cần phải sử dụng một thuật toán đặc biệt để giải quyết những vấn đề (ví dụ bellman-ford)

Nếu bạn đang xem xét tốt nhất trong trường hợp không có heuristic có sẵn thì bạn phải quay lại h(x,y)=0 forall states x and y. Trong trường hợp này A * tương đương với tìm kiếm đầu tiên tốt nhất.

Nếu bạn đang cân nhắc tốt nhất trong các trường hợp liên quan đến kế hoạch chuyển động trong không gian cấu hình liên tục, sau đó A * có thể làm việc đầy đủ trong kích thước thấp, nhưng lưu trữ của đồ thị tìm kiếm bắt đầu trở nên không thực tế ở kích thước cao, và cần phải sử dụng các thuật toán xác suất hoàn thành tăng (ví dụ RRT, Bi-RRT, RDT)

Nếu bạn đang cân nhắc tốt nhất trong trường hợp đồ thị là một phần quan sát được, bạn chỉ biết một tập hợp con của tất cả các đỉnh có thể và các cạnh trong biểu đồ tại ny thời gian, và bạn cần phải thay đổi trạng thái để quan sát nhiều hơn của đồ thị, sau đó bạn cần một thuật toán thay thế được thiết kế cho điều này (ví dụ, Keonig 's Lifelong Planning A *, LPA *, thực hiện chính xác điều này).

Nếu bạn đang cân nhắc tốt nhất trong trường hợp đồ thị thay đổi theo thời gian, mà xảy ra thường xuyên trong robot khi bạn kết hợp di chuyển trở ngại, sau đó bạn cần một thuật toán được thiết kế cho việc này (ví dụ Stentz của D* hoặc Koenig & Likhachev's D * -Lite).

Answer 3

Một giải pháp thay thế cực kỳ đơn giản (không có tranh cãi với chẩn đoán) là Collaborative Diffusion. Nó hoạt động tuyệt vời khi bạn cần phải nhắm mục tiêu một mục tiêu hoặc bất kỳ thành viên của một nhóm, một cách bừa bãi, và trong trường hợp này có thể nhanh hơn so với A *. Nó bắt chước trò chơi "Bạn đang trở nên ấm hơn/lạnh hơn".

Sự khuếch tán cộng tác tạo ra một bản đồ nhiệt cho mỗi "nhóm" bạn muốn nhắm mục tiêu ... nếu bạn muốn theo dõi một mục tiêu cụ thể, coi nó là nhóm riêng bằng cách tạo bản đồ nhiệt cho mục tiêu đó; Miền cộng tác của Diffusion là trò chơi như bóng đá (nơi cả hai đội đại lý theo dõi bóng và mục tiêu cụ thể, dẫn đến 3 bản đồ ảnh hưởng) hoặc Pacman (tương tự, nhiều đại lý theo dõi Pac) hoặc trò chơi quân đội nơi có một bản đồ kết hợp đại diện cho cơ thể (tổng hợp) của mỗi đội quân được xác định từ mỗi đại lý trong quân đội đó, để một đội quân có thể tiếp cận "quân đội khác" thay vì "các đơn vị cụ thể trong quân đội khác". Tính tổng quát này có thể đủ khả năng tăng hiệu suất.

Đi bộ bao gồm leo đồi (di chuyển từ ô hiện tại sang ô lân cận ấm hơn) cho đến khi chúng tôi đến đích (điểm nóng nhất). Phương pháp tiếp cận ngầm ám chỉ các chướng ngại vật di chuyển tức là các tác nhân khác. Đây là nơi phù hợp nhất với các bản đồ khá đông dân cư với nhiều đơn vị di chuyển, do đó biện minh cho sự phổ biến rộng rãi phải xảy ra trên toàn bộ không gian tìm kiếm trên mỗi bản cập nhật.Rõ ràng cách tiếp cận A * được điều chỉnh tốt có thể rẻ hơn nhiều trong bản đồ lớn, thưa thớt, nơi chúng tôi chỉ có một đơn vị nhắm mục tiêu chỉ một đơn vị khác, vì với A * trong trường hợp này bạn chỉ làm việc trên một phần nhỏ gạch bản đồ giữa người tìm kiếm và mục tiêu; trong khi với sự khuếch tán cộng tác, bạn thay vì khuếch tán trên toàn bộ bản đồ chỉ để làm điều tương tự, làm cho nó tốn kém hơn nhiều.