मैं सोच रहा था कि क्या इस रस्सी पुल की समस्या को ग्राफ़िंग एल्गोरिदम खोज के साथ हल किया जा सकता है:एक एल्गोरिदम के साथ रस्सी ब्रिज समस्या को हल करने के लिए कैसे?
मेरी आंत महसूस डीएफएस कहती है लेकिन मुझे राज्यों को कैसे परिभाषित करना चाहिए?
यह कार्य एक कंप्यूटर के बिना हल किया जा करने के लिए माना जाता है (यही कारण है कि अगर डीएफएस भी जाने का रास्ता है।)।
हालांकि, यदि आप मामले को सामान्यीकृत करते हैं, तो मुझे लगता है कि आप इसे ग्राफ खोज के साथ कर सकते हैं, लेकिन आपको ग्राफ़ का आकार खाते में लेना चाहिए। यदि प्रत्येक चरम "राज्य" है, तो इन राज्यों की संख्या 2 एन ⋅L के रूप में अनुमानित है, जहां एन लोगों की संख्या है, और एल फ्लैशलाइट की लंबाई है। प्रत्येक राज्य में जानकारी होती है, शेष फ्लैशलाइट अवधि के प्रत्येक पक्ष, और पर कौन सा पक्ष होता है। यदि शुरुआती राज्य से उन राज्यों में से एक का मार्ग है जहां हर कोई शिविर के पक्ष में है, तो यह मार्ग समाधान है।
यह राज्य बनाने का सबसे स्पष्ट तरीका है, लेकिन हो सकता है कि आप इसे अधिक कुशल तरीके से कर सकें (राज्यों की वर्तमान संख्या, इसलिए रनटाइम, इनपुट आकार के लिए घातीय है)।
हालांकि, आपके द्वारा प्रदान किए गए नमूने में छोटे आकार के लिए, घातीय रनटाइम (ग्राफ़ के साथ) स्वीकार्य है। साक्षात्कारकर्ता इसे भी पसंद कर सकता है, अगर आप इसे हाथ से करने के बजाय प्रोग्रामेटिक समाधान का सुझाव देते हैं।
आप EWD 1255 पर देख सकते हैं।
TheMachineCharmer, लिंक के लिए धन्यवाद, मुझे यह एक दिलचस्प पढ़ने के लिए मिला। अगर मैं समझता हूं कि प्रोफेसर डिजस्ट्रा क्या संदेश दे रहा है, तो रस्सी ब्रिज की समस्या में कोई "जोर" नहीं है। शायद वहाँ हैं और मैं उन्हें नहीं देखता हूं? – NickPoussin
मैंने अभी कुछ संबंधित और जानकारीपूर्ण के रूप में पोस्ट किया है। इसे सी-विकी बना दिया। : डी –
फ्लैशलाइट की लंबाई ??? मुझे लगता है कि आप या तो पुल या फ्लैशलाइट रनटाइम की लंबाई थी। – sharptooth
उसका मतलब फ्लैशलाइट में छोड़ा गया समय (या जैसे ही आप इसे फ्लैशलाइट रनटाइम डालते हैं)। – NickPoussin
धन्यवाद पावेल। राज्य की आपकी व्याख्या "प्रत्येक राज्य में जानकारी होती है, प्रत्येक पक्ष किस तरफ है, और शेष फ्लैशलाइट अवधि" ने मुझे बहुत मदद की। मुझे लगता है कि मैं कल मजेदार के लिए प्रोग्रामिंग करने की कोशिश करूंगा। – NickPoussin