ए * एल्गोरिदम ठीक से काम नहीं कर रहा है

Question

मुझे अपने ए * एल्गोरिदम कार्यान्वयन के साथ कुछ मदद चाहिए। जब मैं एल्गोरिदम चलाता हूं तो उसे लक्ष्य मिल जाता है, लेकिन पथ निश्चित रूप से सबसे छोटा नहीं है :-P

यहां मेरा कोड है, कृपया मुझे बग स्पॉट करने में सहायता करें! मुझे लगता है कि यह पुनर्निर्माण पथ हो सकता है जो मेरी समस्या है लेकिन मुझे यकीन नहीं है।

public class Pathfinder { 

public List<Node> aStar(Node start, Node goal, WeightedGraph graph) { 
    Node x, y; 
    int tentative_g_score; 
    boolean tentative_is_better; 

    FScoreComparator comparator = new FScoreComparator(); 
    List<Node> closedset = new ArrayList<Node>(); 
    Queue<Node> openset = new PriorityQueue<Node>(10, comparator); 
    openset.add(start); 

    start.g_score = 0; 
    start.h_score = heuristic_cost_estimate(start, goal); 
    start.f_score = start.h_score; 

    while (!openset.isEmpty()) { 
     x = openset.peek(); 

     if (x == goal) { 
      return reconstruct_path(goal); 
     } 

     x = openset.remove(); 
     closedset.add(x); 

     for (Edge e : graph.adj(x)) { 

      if (e.v == x) { 
       y = e.w; 
      } else { 
       y = e.v; 
      } 

      if (closedset.contains(y) || y.illegal) { 
       continue; 
      } 

      tentative_g_score = x.g_score + e.weight; 

      if (!openset.contains(y)) { 
       openset.add(y); 
       tentative_is_better = true; 
      } else if (tentative_g_score < y.g_score) { 
       tentative_is_better = true; 
      } else { 
       tentative_is_better = false; 
      } 

      if (tentative_is_better) { 
       y.g_score = tentative_g_score; 
       y.h_score = heuristic_cost_estimate(y, goal); 
       y.f_score = y.g_score + y.h_score; 
       y.parent = x; 
      } 

     } 

    } 

    return null; 

} 

private int heuristic_cost_estimate(Node start, Node goal) { 
    return Math.abs(start.x - goal.x) + Math.abs(start.y - goal.y); 
} 

private List<Node> reconstruct_path(Node current_node) { 
    List<Node> result = new ArrayList<Node>(); 

    while (current_node != null) { 
     result.add(current_node); 
     current_node = current_node.parent; 
    } 

    return result; 
} 

private class FScoreComparator implements Comparator<Node> { 

    public int compare(Node n1, Node n2) { 
     if (n1.f_score < n2.f_score) { 
      return 1; 
     } else if (n1.f_score > n2.f_score) { 
      return -1; 
     } else { 
      return 0; 
     } 
    } 
} 

} सभी महान जवाब के लिए हर किसी के लिए

धन्यवाद! मेरा ए * एल्गोरिदम अब आपके लिए पूरी तरह से धन्यवाद करता है! :-)

यह मेरी पहली पोस्ट थी और यह मंच वाकई अद्भुत है!

Answer 1

आप PriorityQueue में एक तत्व की प्राथमिकता बदल रहे हैं में वस्तुओं। यह समर्थित नहीं है, क्योंकि प्राथमिकता कतार को पता नहीं है कि एक वस्तु बदल गई है। आप क्या कर सकते हैं जब यह बदलता है वस्तु को हटा दें और फिर से जोड़ें।

प्राथमिकता रेखा में बदल दी गई है: y.f_score = y.g_score + y.h_score;। यह पंक्ति प्राथमिकता कतार में y जोड़ने के बाद होती है। ध्यान दें कि लागत की गणना करने के बाद बस openset.add(y); को स्थानांतरित करना पर्याप्त नहीं होगा, क्योंकि y पिछले पुनरावृत्ति में जोड़ा जा सकता है।

यह आपके कोड से भी स्पष्ट नहीं है कि आपने उपयोग किया जाने वाला हेरिस्टिक admissible है। यदि ऐसा नहीं है तो यह आपको उप-पथ प्राप्त करने का कारण भी देगा।

अंत में, एक प्रदर्शन ध्यान दें: ArrayList और PriorityQueue पर contains विधि रैखिक बार चलाने के लिए है, जो अपने implememtation गैर इष्टतम का चलने का समय कर देगा लेता है। आप नोड्स में बुलियन गुण जोड़कर इसे सुधार सकते हैं ताकि यह इंगित किया जा सके कि वे बंद/खुले सेट में हैं या सेट डेटा संरचना का उपयोग कर रहे हैं।

Answer 2

प्राथमिकता कतार आइटम की स्थिति अपडेट नहीं करता है जब आप इसकी प्राथमिकता बदलते हैं। इसलिए ढेर संपत्ति पकड़ नहीं है। बदली गई प्राथमिकता अन्य वस्तुओं के जोड़/निकासी को प्रभावित करती है, लेकिन यह ढेर संपत्ति की मरम्मत नहीं करती है।

इसलिए आपको खुले से सर्वश्रेष्ठ आइटम नहीं मिलता है -> आपको सबसे कम रास्ता नहीं मिलता है।

आप कर सकते हैं: 1) अपने स्वयं के ढेर लिख सकते हैं और में सूचकांक को बनाए रखने के लिए यह 2) पीक्यू में किसी अन्य वस्तु को जोड़ने और पुराने वाले के रूप में चिह्नित अमान्य (आप वैधता ध्वज के साथ किसी वस्तु डाल दिया और में नोड को संदर्भित नोड के बजाय चाहिए कतार)।

2) खराब प्रदर्शन है और मैं इसके खिलाफ सलाह देता हूं, लेकिन कुछ नेविगेशन सॉफ़्टवेयर इस दृष्टिकोण का उपयोग करते हैं (या कम से कम कुछ साल पहले इसका उपयोग किया जाता है)।

संपादित करें: सर्वश्रेष्ठ अभ्यास, अपरिवर्तनीय (या कम से कम imutable भागों प्राथमिकता का मतलब है) के साथ सम्मिलित किया जाता है उसे डाला करने के बाद PriorityQueue