सबसे तेज़ क्रॉस-प्लेटफार्म ए * कार्यान्वयन?

Question

इतने सारे कार्यान्वयन उपलब्ध होने के साथ, सबसे तेज़ निष्पादन (कम से कम सीपीयू गहन, सबसे छोटी बाइनरी), क्रॉस-प्लेटफार्म (लिनक्स, मैक, विंडोज़, आईफोन) ए * एक छोटे ग्रिड का उपयोग कर सी ++ के लिए कार्यान्वयन क्या है?

क्रियान्वयन

गूगल रिटर्न:

• http://www.heyes-jones.com/astar.html (उस साइट पर सबसे लिंक मर चुके हैं।)
• http://www.grinninglizard.com/MicroPather (ने कहा 'Heyes-जोन्स की तुलना में धीमी होने के लिए।)
• http://www.ceng.metu.edu.tr/~cuneyt/codes.html (जेनेरिक सी ++ कोड।)
• http://swampthingtom.blogspot.com/2007/07/pathfinding-sample-using.html
• http://opensteer.sourceforge.net/ (खेल के लिए, ए * नहीं दिलचस्प।)
• Stack Overflow on Dijkstra's Algorithm

किसी भी दूसरों?

व्हील

सवाल है, के रूप में पूछा, (एक खेल में प्लग) का पुन: उपयोग से संबंधित है, नहीं पुनर्खोज (जब तक प्रदर्शन एक मुद्दा होना दिखाया गया है कम से कम नहीं)। यह पता चला है कि एक डिजस्ट्रा कार्यान्वयन (या सामान्य पथदर्शी एल्गोरिदम) बेहतर अनुकूल है, या सबसे तेज़ कार्यान्वयन पर्याप्त तेज़ नहीं हैं। मैं वैकल्पिक एल्गोरिदम के सुझावों की सराहना करता हूं, हालांकि सवाल यह नहीं है, "क्या मुझे अपना ए * रोल करना चाहिए?"

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

Answer 1

देखो और अपने परिदृश्य के लिए सकारात्मक और नकारात्मक वजन (सांस-सबसे पहले, गहराई-प्रथम, Minimax, Negmax आदि)।

बूस्ट has an A-star implementation भी बढ़ावा दें। आईफोन पर बढ़ावा देने के लिए these instructions का पालन करने का प्रयास करें, लेकिन यह आपके लिए काम नहीं कर सकता है: यह बढ़ावा का "पूर्ण बंदरगाह" नहीं है और यह त्रुटि हो सकती है।

निम्नलिखित Algorithms in a Nutshell से है (जावा, सी ++ नहीं लेकिन शायद आप इसे बंदरगाह करना चाहते हैं):

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

मेरा सुझाव है कि आप अपने आप से एल्गोरिथ्म को लागू। छद्म कोड का पालन करें: A* Search Algorithm और यह सीधे आगे होना चाहिए। "ओपनसेट" को एक मिनी-ढेर के रूप में कार्यान्वित किया जाना चाहिए, जो कि तुच्छ भी है; या आप एसटीएल से priority_queue का उपयोग कर सकते हैं।

Answer 3

जब आपके पास विशिष्ट सीमाएं हैं जिनके साथ आप काम कर सकते हैं, तो आप आमतौर पर एल्गोरिदम लिखने से बेहतर होते हैं। विशेष रूप से आपकी छोटी राज्य की जगह स्वयं को ऑप्टिमाइज़ेशन में उधार देती है जो सीपीयू समय को कम करने के लिए मेमोरी अप-फ्रंट खर्च करती है, और तथ्य यह है कि आप एक मनमानी राज्य स्थान की बजाय ग्रिड का उपयोग कर रहे हैं, जिससे आप अपने उत्तराधिकारी नोड पीढ़ी को अनुकूलित करने जैसी चीजों को करने की अनुमति देते हैं, या सभी आंशिक पथों का इलाज करने में सक्षम हो जो समान ग्रिड वर्ग पर बराबर के बराबर होते हैं (जो एक सामान्य ए * खोज नहीं करेगा और नहीं मान सकता)।

(पीएस ओपनस्टियर, स्टीयरिंग व्यवहार का संग्रह, ए * के साथ कुछ भी नहीं है, जो एक खोज एल्गोरिदम है, सिवाय इसके कि आप एक स्थान को पार करने के लिए एक दूसरे, या दोनों का उपयोग कर सकते हैं। एक ' सबसे उचित परिस्थितियों में अन्य के लिए एक स्थानापन्न टी)

Answer 4

मैं सलाह के दो सामान्य टुकड़े हैं:। आपके डोमेन एक ग्रिड के लिए प्रतिबंधित है, तो

• , हो सकता है आपको बेहतर परिणाम मिलेगा खोज "pathfinding" द्वारा बल्कि अधिक सामान्य ए *।
• यदि आपका डोमेन सख्ती से सतह के साथ पथ खोज नहीं रहा है, तो आप अपने प्रयास के लिए और अधिक लाभ प्राप्त कर सकते हैं यदि आप अपना समय एल्गोरिदम अनुकूलित करने की कोशिश करने के बजाय अपने हेरिस्टिक में सुधार करते हैं। अन्य मार्ग खोजने एल्गोरिदम पर

Answer 5

वहाँ एक सामान्य सी ++ http://www.ceng.metu.edu.tr/~cuneyt/codes.html पर एक * कार्यान्वयन है। ऐसा लगता है कि यह सभी क्रॉस-प्लेटफार्म मानक सी ++ है।