ए * ह्युरिस्टिक: एकाधिक बिंदुओं में एक बार गुजरने वाला सबसे छोटा रास्ता

Question

मैं स्पष्ट मानचित्र पैकमैन गेम के लिए एक अच्छा और तेज़ ह्युरिस्टिक के साथ आने की कोशिश कर रहा हूं।

मेरा उत्तराधिकारी संभवतः छोटी दूरी की गणना करने की कोशिश कर रहा है कि पैकमैन को नक्शे पर भोजन के साथ हर बिंदु पर जाने की यात्रा करने की आवश्यकता है। मेरा वर्तमान एल्गोरिदम मूल रूप से प्राइम एमएसटी है जो मुझे ओ (एन लॉगन) चलने का समय देता है, लेकिन उन परिस्थितियों के लिए खाता नहीं है जहां पैकमैन को खाने के किनारे का पालन करना पड़ता है, और पिछले वर्टेक्स पर वापस लौटना पड़ता है ...

क्या कुछ बेहतर है?

एक और तरीके से कह रहा है: मेरी कलम उठाए बिना कई बिंदुओं को जोड़ने की न्यूनतम लागत क्या है?

धन्यवाद

Answer 1

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