झंझट की समस्या और ग्रे कोड

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


KDPV: एक जीवंत उदाहरण पर एक व्यंग्य समस्या

प्रागितिहास

यह सब 10 साल पहले शुरू हुआ था जब मैं नौवीं कक्षा में था। मैंने गलती से एक कंप्यूटर विज्ञान के शिक्षक की बातचीत को बड़ों में से एक को पहेली सुनकर सुनाया: संख्याओं का एक समूह दिया गया था, और एक अन्य संख्या एक नियंत्रण थी। सेट से अधिकतम संख्या का पता लगाना आवश्यक है, जो नियंत्रण संख्या से अधिक नहीं होगा।

किसी कारण के लिए कार्य मेरी आत्मा में डूब गया। घर लौटने के बाद, मैंने जल्दी से एक समाधान निकाला: सर्वश्रेष्ठ की पसंद के साथ सभी संभव राशियों की एक भोली खोज। मुझे सभी एन-बिट बाइनरी नंबरों के माध्यम से सॉर्ट करने और उन प्रारंभिक नंबरों की रकम लेने के लिए संयोजन मिला, जिनके लिए इकाइयां अनुरूप हैं। लेकिन मुझे अफसोस हुआ कि 30 के आसपास कहीं से शुरू होने वाले तत्वों की संख्या के साथ, कार्यक्रम बहुत लंबे समय तक चलता है। यह आश्चर्य की बात नहीं है, क्योंकि इस तरह के एक एल्गोरिथ्म का संचालन समय n * 2 ^{n है} (योग की लंबाई से संयोजन की संख्या)।

5 साल हो गए। मैं स्कूल खत्म करने और विश्वविद्यालय जाने में कामयाब रहा, लेकिन यह कार्य अभी भी मेरे साथ था। एक बार, "एलगोरिदम ट्रिक्स फॉर प्रोग्रामर्स" (हैकर डिलाइट / हेनरी एस। वॉरेन जूनियर) पुस्तक के माध्यम से, मैं ग्रे कोड के विवरण के साथ आया: यह द्विआधारी संख्याओं का एक क्रम है, जिनमें से प्रत्येक पिछले एक से केवल एक बिट से भिन्न होता है। "बंद करो!" मैंने सोचा। "इसका मतलब है ... हाँ!" इसका मतलब है कि खोज के प्रत्येक चरण में बहुत समस्या में, आप पूरी राशि की गणना नहीं कर सकते हैं, लेकिन केवल एक संख्या जोड़ या घटा सकते हैं। " और मैं तुरंत विषय के अध्ययन में गहरा गया।

बिल्डिंग ग्रे कोड

ग्रे कोड का निर्माण किसी भी बिट गहराई के लिए किया जा सकता है। एक श्रेणी के लिए, यह स्पष्ट है:

0
1

दूसरा अंक जोड़ने के लिए, आप इस क्रम में उसी पीछे की ओर जोड़ सकते हैं

0
1
1
0

और दूसरी छमाही में इकाइयों को जोड़ें:

00
01
11
10

इसी तरह तीन अंकों के लिए:

000
001
011
010
110
111
101
100

इस तरह के कोड को कम बिट क्षमता के एक कोड के प्रतिबिंब द्वारा प्राप्त किया जाता है, इसे रिफ्लेक्स (परावर्तित) ग्रे कोड कहा जाता है। अन्य क्रम हैं, लेकिन व्यवहार में यह आमतौर पर उपयोग किया जाता है।

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


फ्रैंक ग्रे पेटेंट चित्रण

ग्रे कोड का सबसे स्पष्ट उपयोग कोण सेंसर में है। पुराने यांत्रिक चूहों में जो था, उसके समान सेंसर, लेकिन सापेक्ष विस्थापन नहीं, बल्कि कोण का निरपेक्ष मान निर्धारित करता है। ऐसा करने के लिए, प्रत्येक सेंसर के लिए आपको कई ऑप्टोकोप्लर्स और कई स्लेटेड झंझरी की आवश्यकता होती है। इसके अलावा, सेंसर के प्रत्येक बाद की स्थिति केवल एक बिट की स्थिति में पिछले एक से भिन्न होनी चाहिए, अन्यथा सीमाओं पर गैर-समकालिक स्विचिंग संभव है, और, परिणामस्वरूप, डिवाइस के रीडिंग में तेज कूदता है। यहां आप ग्रे कोड की एक जिज्ञासु विशेषता देख सकते हैं: अंतिम संख्या भी पहले एक से एक बिट से भिन्न होती है, इसलिए इसे "लूप" किया जा सकता है।


रोटेशन के निरपेक्ष कोण का सेंसर। ग्रे स्लॉट के अनुसार ऑप्टिकल स्लॉट की व्यवस्था की जाती है।

क्नैप्सैक समस्या में आवेदन

लेकिन वापस थप्पड़ समस्या के लिए। मानक सूत्र हमें संख्या द्वारा ग्रे कोड देता है:

G = i ^ (i >> 1) 

इसके अनुसार, हम केवल सभी आवश्यक तत्वों की राशि की गणना कर सकते हैं। और हम प्रत्येक पुनरावृत्ति पर एक मान जोड़ने या घटाने जा रहे थे, है ना? तो, हमें संशोधित बिट्स की संख्या प्राप्त करने की आवश्यकता है। बहु अंकों वाली संख्याओं के लिए, ये संख्याएँ इस तरह होंगी:

0
1
0
2
0
1
0
3
0
1
0
2
0
1
0
4
...

क्या कुछ भी समान नहीं है? यह वह संख्या है जिसे हम साधारण बाइनरी संख्याओं की सूची में रखते हुए एकता के लिए निर्धारित करते हैं। या फिर - एक बाइनरी संख्या में मामूली इकाई की संख्या। इस ऑपरेशन को फाइंड फ़र्स्ट सेट कहा जाता है और अधिकांश प्रोसेसर पर एक अलग निर्देश के रूप में मौजूद होता है। Visual C ++ इस निर्देश को _BitScanForward फ़ंक्शन के रूप में प्रदान करता है।

इसलिए, अब हम एक प्रोग्राम लिखने के लिए तैयार हैं, जो ग्रे कोड के माध्यम से नॅप्सैक समस्या को हल करता है। हम समस्या को इस प्रकार बनाते हैं:

Input.txt फ़ाइल में, पहली पंक्ति बैकपैक की क्षमता को इंगित करती है, और शेष लाइनें चीजों के आकार को इंगित करती हैं। कंसोल में आपको बैकपैक का अधिकतम भार और चयनित चीजों के आकार को प्रदर्शित करने की आवश्यकता होती है। इनपुट आदि की शुद्धता की जाँच - देखें।

हम उपयोग की गई चीजों के एक बिटमास्क को स्टोर करेंगे, और उनमें से एक को आवश्यक रूप से जोड़ या हटा देंगे। Ints के साथ प्राप्त करने के लिए, हम चीजों की संख्या (और प्रयुक्त बिट्स) को इकतीस तक सीमित करते हैं।

 #include <iostream> #include <fstream> #include <bitset> #include <intrin.h> using namespace std; void main() { int target; //   int nItems = 0; //   int weight[31]; //   ifstream inFile("input.txt"); inFile >> target; while(inFile >> weight[nItems]) nItems++; inFile.close(); const unsigned int nIterations = 1 << nItems; //  , 2^n int sum = 0; //    int bestSum = 0; //   (  ) bitset<31> mask; //     bitset<31> bestMask; //     for (unsigned int i = 1; i < nIterations; i++) { unsigned long position; //      _BitScanForward(&position, i); mask[position] = !mask[position]; if (mask[position]) //        sum += weight[position]; else sum -= weight[position]; if (sum > target) //  continue; if (sum > bestSum) //  !  ... { bestSum = sum; bestMask = mask; } } cout << "Best approximation: " << bestSum << endl; cout << "Used weights:" << endl; for (int i = 0; i < 31; i++) if (bestMask[i]) cout << weight[i] << endl; cin.get(); } 

मैं संभव खुरदरापन के लिए माफी माँगता हूँ; दुर्भाग्य से, C ++ लंबे समय तक मेरी मुख्य भाषा नहीं रही।

यह वास्तव में सभी नंबरों को खरोंचने से इकट्ठा करने की तुलना में तेजी से काम करता है, अंतर पहले से ही 20 संख्याओं पर ध्यान देने योग्य है, और 30 पर मैं अभी भी भोली एल्गोरिथ्म के पूरा होने का इंतजार नहीं करता, जबकि नया संस्करण 7 सेकंड में पूरा होता है। हालांकि, घातीय जटिलता को देखते हुए, यह काफी कुछ है: 50 संख्याओं के लिए, इस एल्गोरिथ्म का उपयोग करने से अब कोई मतलब नहीं है। दुर्भाग्य से, कोई भी सटीक एल्गोरिदम 2 ^{एन की} तुलना में तेजी से काम नहीं करेगा; तेजी से केवल एक अनुमानित समाधान संभव है। (अपडेट: कुछ मामलों में, डायनेमिक प्रोग्रामिंग और बीच-बीच में समस्या को तेजी से हल करते हैं। विवरण के लिए टिप्पणियां देखें।)

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