2013-02-24 14 views
5

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

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

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

+3

ए * पहले कोशिश क्यों न करें और देखें कि यह कैसा प्रदर्शन करता है? –

+0

मैं निश्चित रूप से कर सकता था, लेकिन मुझे लगता है कि ए * बिना किसी हैक के टेलीपोर्टर्स की तरह "शॉर्टकट" नहीं लेता है। मुझे यह देखना होगा कि एल्गोरिदम कैसे थोड़ा और काम करता है। – Schilcote

+0

क्या हैक? मुझे लगता है कि ए * शून्य-लंबाई किनारों के साथ ठीक काम कर सकता है। मैं उत्सुक हूँ। –

उत्तर

2

ए * का उपयोग करने में एकमात्र समस्या आपकी समस्या के लिए admissible heuristic ढूंढ रही है। सौभाग्य से, यह पहले से ही here का उत्तर दिया गया है।

सिस्टम टेलीपोर्टर्स की आवश्यकता वाले क्षेत्रों की पहचान कैसे करेगा?

यह इस बात पर निर्भर करता है कि कछुए वास्तव में कहां से आगे बढ़ रहा है। यदि वह हमेशा एक ही प्रारंभ/समाप्ति बिंदु से/आगे बढ़ता रहता है, तो उत्तर छोटा होता है: शुरुआत और समाप्ति पर टेलीपोर्ट जोड़ें। अधिक जटिल सेटअप के लिए, मेरा अनुमान होगा कि यह एनपी-हार्ड है; यदि सही है, तो आपको global-optimization strategies(या केवल यादृच्छिक पदों का एक समूह आज़माएं और सबसे अच्छा लेना होगा) देखें।

संबंधित मुद्दे