पॅकमैन पथ के साथ कुछ प्रश्न

Question

मैंने ए *, बीएफएस, डीएफएस के बारे में सीखा है और उन्हें बहुत अच्छी तरह कार्यान्वित कर सकते हैं। हालांकि, जब मैं पैकमैन पथ खोजने की समस्या को हल करने में ऐसा करने की कोशिश करता हूं तो कुछ समस्याएं उत्पन्न होती हैं। आइए मान लें कि केवल दो प्रकार के मैज हैं: किसी के पास पूर्ण वस्तुएं हैं, जैसे कि रिक्त वर्ग में, सबकुछ या तो पॅकमैन या आइटम-टू-कलेक्ट या दीवार है; और केवल एक ही वस्तुएं (4 या उससे कम) होती हैं।

1. यदि एक से अधिक आइटम एकत्र करने के लिए बीएफएस और डीएफएस लागू होते हैं तो वास्तव में कैसे लागू होते हैं? ऐसे मामले में, क्या वे अभी भी इष्टतम परिणाम उत्पन्न करते हैं?

2. पूर्ण-आइटम मानचित्र के लिए सबसे अच्छा एल्गोरिदम/हेरिस्टिक क्या है? जो कुछ मैंने अभी तक किया है वह लालची ह्युरिस्टिक की तरह कुछ है, लेकिन नक्शा के कारण यह बहुत यादृच्छिक है क्योंकि नक्शा इकट्ठा करने के लिए बहुत सारी चीजें हैं और इसलिए, इस तरह के भूलभुलैया को हल करने का अच्छा विचार नहीं है।

3. कुछ आइटम मानचित्र में ए * का उपयोग करके, यह निर्धारित करने का कोई अच्छा तरीका है कि कौन सा आइटम पहले लिया जाना चाहिए? मैंने महात्मा दूरी का उपयोग किसी न किसी अनुमान के रूप में करने का प्रयास करने के बारे में सोचा, लेकिन यह विशेष रूप से कुछ मुश्किल परिस्थितियों में सही नहीं लगता है।

Answer 1

यदि आप अधिक खाना जोड़ते हैं तो एल्गोरिदम नहीं बदलते हैं। एकमात्र चीज जो बदलती है वह राज्य की जगह है। आपको अपनी समस्या का प्रतिनिधित्व करने के लिए एक नए तरीके के बारे में सोचना होगा। जब आपके पास खाने के लिए केवल 1 भोजन होता है, तो आपको केवल x, y pacman की स्थिति की आवश्यकता होती है। जब आपके पास खाने के लिए 3 बिंदु हैं, उदाहरण के लिए, आपको इन जानकारी को अपने मॉडल में जोड़ना होगा। आप संकेत देते हैं कि पॅकमैन डॉट के माध्यम से पारित हो गया है, तो आप 3 बूलियन चर जोड़ सकते हैं। अब आप राज्य अंतरिक्ष एक ग्राफ में निम्न प्रकार के नोड्स से बना है:

((x,y),FALSE,FALSE,FALSE) -> state that indicates that pacman has not eat any food 
((x,y),FALSE,TRUE,FALSE) -> state that indicates that pacman has eat only one food 
((x,y),TRUE,TRUE,TRUE) -> this is the goal state 

समस्या को हल करने तुम सिर्फ अपने नए मॉडल में एक ही एल्गोरिथ्म चलाते हैं। बीएफएस उत्तर ए * हमेशा आपको इष्टतम समाधान देगा। समस्या यह है कि: जितना अधिक खाना आप डालते हैं, धीमी गति से समाधान मिल जाता है। तो ये एल्गोरिदम उचित समय में उत्तर नहीं देंगे। आपको ऐसा करने का नया तरीका मिल गया है।

Answer 2

1) इस स्थिति में बीएफएस या डीएफएस का उपयोग करने के साथ मुझे समस्या यह है कि यह कैसे अक्षम होगा, खासकर पूर्ण मानचित्र उदाहरण में। एकाधिक लक्ष्यों के साथ काम करने के लिए या तो एल्गोरिदम प्राप्त करने के लिए, आप या तो खोज बना सकते हैं ताकि पहले पथ के बाद यह समाप्त न हो, लेकिन यह आपको अभी भी मानचित्र पर भोजन के प्रत्येक टुकड़े के लिए "इष्टतम" पथ नहीं देगा , या आप पैकमैन से निकटतम भोजन तक पहुंच सकते हैं, कि अगले निकटतम भोजन, आदि, उन पथों को ढूंढें, फिर उनको तुलना करें, वास्तव में इष्टतम पथ खोजने के लिए, लेकिन मैं इस बारे में नहीं सोचना चाहता कि यह कितना समय होगा लेना।

2) मैं शायद एक लालची ए * के साथ रहूंगा, जो केवल निकटतम भोजन को देखता है (मुझे ज्यादातर मामलों में मैनहट्टन दूरी के साथ कोई समस्या नहीं दिखाई देती है, क्योंकि पैकमैन के लिए नक्शा पहले से ही ग्रिड है; यह होगा किनारों के मामलों के लिए उपोष्णकटिबंधीय हो जहां दीवारें निकटतम तक पहुंचने से पॅकमैन को रोकती हैं, लेकिन यह हल करने में एक कठिन समस्या है। मैनहट्टन एक सभ्य व्यक्ति होगा, संभवतः केवल दूरी की बजाय भोजन की घनत्व द्वारा संशोधित किया जाएगा, जैसे: (मैनहट्टन दूरी)/(भोजन के 3x3 वर्ग के भीतर कुल भोजन)

3) प्रत्येक आइटम पर पथदर्शी का उपयोग करने का छोटा, फिर सबसे छोटा चुनना, मुझे लगता है कि मैनहट्टन कुछ आइटम परिदृश्य में ठीक काम करेगा। यह हमेशा सर्वश्रेष्ठ नहीं चुनता है, लेकिन 100% इष्टतम एआई आमतौर पर गेमिंग के लिए सबसे अच्छा लक्ष्य नहीं है।

इस मामले में, मैं वजन एक सरल, शालीनता से तेज समाधान के रूप में आइटम के समूहों के पक्ष के साथ लालची एक प्रयास करने के लिए * चाहते हैं।

एक अधिक जटिल समाधान है कि Pacman के लिए इष्टतम पथ के करीब लौटना चाहिए पालन करने के लिए एक एल्गोरिथ्म का उपयोग करने के लिए एक Minimum Spanning Tree http://en.wikipedia.org/wiki/Minimum_spanning_tree को खोजने के लिए होगा, लेकिन मैं नहीं जानता कि यह कैसे आसान लागू करने के लिए किया जाएगा। यहां दो न्यूनतम स्पैनिंग ट्री एल्गोरिदम की योग्यता पर चर्चा करने का एक प्रश्न है: Kruskal vs Prim