Triển khai A * đa nền tảng nhanh nhất?

Question

Với nhiều triển khai sẵn có, thực thi nhanh nhất (ít nhất là CPU, nhị phân nhỏ nhất), triển khai đa nền tảng (Linux, Mac, Windows, iPhone) cho C++ bằng lưới nhỏ?

Triển khai

Google trả về:

• http://www.heyes-jones.com/astar.html (Hầu hết các liên kết trên trang web đó đã chết.)
• http://www.grinninglizard.com/MicroPather (Said là chậm hơn so với Heyes-Jones'.)
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html (Mã C++ chung).
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/ (Thú vị cho các trò chơi, không phải A *.)
• Stack Overflow on Dijkstra's Algorithm

Bất kỳ những người khác?

The Wheel

Câu hỏi đặt ra, như hỏi, gắn liền với tái sử dụng (cắm vào một trò chơi), không tái tạo (ít nhất là không cho đến khi thực hiện được thể hiện là một vấn đề). Nó có thể chỉ ra rằng một thực hiện Dijkstra (hoặc thuật toán pathfinding chung) là phù hợp hơn, hoặc rằng việc triển khai nhanh nhất không đủ nhanh. Tôi đánh giá cao các đề xuất của các thuật toán thay thế, tuy nhiên câu hỏi không phải là, "Tôi có nên cuộn A * của riêng mình không?"

• Joel on Software - Not Invented Here Syndrome
• Coding Horror: Don't Reinvent the Wheel
• Overcoming the "Not Invented Here Syndrome"

Answer 1

Nhìn vào các thuật toán tìm đường khác (như Breath-First, Depth-First, Minimax, Negmax vv) và cân nhắc các tích cực và âm bản cho kịch bản của bạn.

Tăng cường cũng has an A-star implementation. Hãy thử theo dõi these instructions để xây dựng tăng trên iPhone, nhưng nó có thể không hoạt động cho bạn: nó không phải là một "cổng đầy đủ" của tăng và nó có thể lỗi.

Sau đây là từ Algorithms in a Nutshell (Java, C++ không nhưng có lẽ bạn muốn đến cổng nó):

public Solution search(INode initial, INode goal) { 
    // Start from the initial state 
    INodeSet open = StateStorageFactory.create(StateStorageFactory.TREE); 
    INode copy = initial.copy(); 
    scoringFunction.score(copy); 
    open.insert(copy); 

    // Use Hashtable to store states we have already visited. 
    INodeSet closed = StateStorageFactory.create(StateStorageFactory. HASH); 
    while(!open.isEmpty()) { 
    // Remove node with smallest evaluation function and mark closed. 
    INode n = open.remove(); 

    closed.insert(n); 

    // Return if goal state reached. 
    if(n.equals(goal)) { return new Solution(initial, n); } 

    // Compute successor moves and update OPEN/CLOSED lists. 
    DepthTransition trans = (DepthTransition)n.storedData(); 
    int depth = 1; 

    if(trans ! = null) { depth = trans.depth + 1; } 

    DoubleLinkedList<IMove> moves = n.validMoves(); 

    for(Iterator<IMove> it = moves.iterator(); it.hasNext();) { 
     IMove move = it.next(); 

     // Make move and score the new board state. 
     INode successor = n.copy(); 
     move.execute(successor); 

     // Record previous move for solution trace and compute 
     // evaluation function to see if we have improved upon 
     // a state already closed 
     successor.storedData(new DepthTransition(move, n, depth)); 
     scoringFunction.score(successor); 

     // If already visited, see if we are revisiting with lower 
     // cost. If not, just continue; otherwise, pull out of closed 
     // and process 
     INode past = closed.contains(successor); 

     if(past ! = null) { 
     if(successor.score() >= past.score()) { 
      continue; 
     } 

     // we revisit with our lower cost. 
     closed.remove(past); 
     } 

     // place into open. 
     open.insert(successor); 
    } 
    } 

    // No solution. 
    return new Solution(initial, goal, false); 
} 

Answer 2

tôi đề nghị bạn thực hiện các thuật toán của mình. Thực hiện theo các mã giả tại: A* Search Algorithm và nó phải thẳng về phía trước. Các "openset" nên được thực hiện như là một min-heap, đó cũng là tầm thường; hoặc bạn có thể sử dụng priority_queue từ STL.

Answer 3

Khi bạn có giới hạn cụ thể mà bạn có thể làm việc, bạn thường tự mình viết tốt hơn thuật toán. Đặc biệt, không gian trạng thái nhỏ của bạn tự cho phép tối ưu hóa bộ nhớ phía trước để giảm thời gian CPU và thực tế là bạn đang sử dụng lưới thay vì không gian trạng thái tùy ý cho phép bạn thực hiện những việc như tối ưu hóa thế hệ nút kế thừa của bạn hoặc có thể xử lý tất cả các đường dẫn một phần kết thúc trên cùng một ô vuông tương đương (mà tìm kiếm A * bình thường sẽ không và không thể giả định).

(PS. OpenSteer, tập hợp các hành vi chỉ đạo, không liên quan gì đến A *, là thuật toán tìm kiếm, ngoại trừ việc bạn có thể sử dụng một cách khác, một hoặc cả hai để đi qua một không gian. t một sự thay thế cho người khác trong những hoàn cảnh hợp lý nhất)

Answer 4

tôi có hai mảnh chung của lời khuyên:.

• Nếu tên miền của bạn được giới hạn cho một mạng lưới, có thể bạn sẽ tìm thấy kết quả tốt hơn bằng cách tìm kiếm "tìm đường" thay vì A * chung chung hơn.
• Nếu tên miền của bạn không tìm kiếm đường dẫn dọc theo bề mặt, bạn có thể nhận được nhiều lợi ích hơn nếu bạn dành thời gian cải thiện chẩn đoán của mình thay vì cố gắng tối ưu hóa thuật toán.

Answer 5

Có một C++ generic Một thực hiện * tại http://www.ceng.metu.edu.tr/~cuneyt/codes.html. Có vẻ như đó là tất cả tiêu chuẩn đa nền tảng C++.