बहुपद समय में बेल्टवे की समस्याओं की विलेयता के बारे में

छात्रों को जैव सूचना विज्ञान पाठ्यक्रम लेने से बेल्टवे की समस्या का पता चलता है, विशेष रूप से, उच्चतम गुणवत्ता में से एक और प्रोग्रामर के लिए आत्मा में निकटतम - बायोइनफॉरमैटिक्स (पावेल पेवेज़र) कैलिफोर्निया विश्वविद्यालय सैन डिएगो से पाठ्यक्रम पर। समस्या कथन की सादगी, व्यावहारिक महत्व और इस तथ्य से ध्यान आकर्षित करती है कि इसे अभी भी सरल कोडिंग के साथ हल करने की स्पष्ट क्षमता के साथ अनसुलझा माना जाता है। समस्या इस तरह से सामने आती है। क्या बहुपद समय में बिंदुओं के एक सेट के निर्देशांक को पुनर्स्थापित करना संभव है$$ $ इनलाइन $ X $ इनलाइन $ अगर उनके बीच सभी जोड़ीदार दूरी का सेट ज्ञात है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ ?

यह प्रतीत होता है कि सरल कार्य अभी भी कम्प्यूटेशनल ज्यामिति की अनसुलझी समस्याओं की सूची में है। इसके अलावा, स्थिति भी बहुआयामी रिक्त स्थान, विशेष रूप से घुमावदार वाले बिंदुओं पर चिंता नहीं करती है, समस्या पहले से ही सबसे सरल विकल्प है - जब सभी बिंदुओं में पूर्णांक निर्देशांक होते हैं और एक ही पंक्ति पर स्थानीय होते हैं।

पिछली लगभग आधी सदी में जब से इस कार्य को गणितज्ञों ने एक चुनौती (शमोस, 1975) के रूप में मान्यता दी थी, कुछ परिणाम प्राप्त हुए थे। हम एक आयामी समस्या के लिए दो मामलों को संभव मानते हैं:

1. अंक एक सीधी रेखा (टर्नपाइक समस्या) पर स्थित हैं
2. बिंदु एक वृत्त (बेल्टवे समस्या) पर स्थित हैं

इन दो मामलों को एक कारण के लिए अलग-अलग नाम प्राप्त हुए - उन्हें हल करने के लिए अलग-अलग प्रयास होते हैं। वास्तव में, पहला कार्य काफी जल्दी (15 वर्षों में) हल हो गया था और एक बैकग्राउंडिंग एल्गोरिथ्म बनाया गया था, जो कि द्विघात समय में औसतन समाधान को पुनर्स्थापित करता है$$ $ इनलाइन $ O (n ^ 2 \ log n) $ इनलाइन $ जहाँ$$ $ इनलाइन $ n $ इनलाइन $ - अंकों की संख्या (स्कीना, 1990); दूसरे कार्य के लिए यह अब तक नहीं किया गया है, और सबसे अच्छा प्रस्तावित एल्गोरिथ्म में घातीय कम्प्यूटेशनल जटिलता है$$ $ इनलाइन $ O (n ^ n \ log n) $ इनलाइन $ (लेमके, 2003)। नीचे दी गई छवि एक अनुमान दिखाती है कि आपका कंप्यूटर कितने अंकों के साथ सेट के लिए समाधान प्राप्त करने के लिए काम करेगा।



यही है, मनोवैज्ञानिक रूप से स्वीकार्य समय (~ 10 सेकंड) में, आप कई को पुनर्स्थापित कर सकते हैं$$ $ इनलाइन $ X $ इनलाइन $ एक शलजम मामले में 10 हजार अंक तक और बेल्टवे मामले के लिए केवल ~ 10 अंक हैं, जो व्यावहारिक अनुप्रयोगों के लिए बिल्कुल बेकार है।

थोड़ा स्पष्टीकरण। यह माना जाता है कि टर्नपाइक समस्या व्यावहारिक उपयोग के संदर्भ में हल की गई है, जो कि अधिकांश डेटा का सामना करना पड़ा है। इस मामले में, शुद्ध गणितज्ञों की आपत्तियां इस तथ्य पर हैं कि विशेष डेटा सेट हैं जिनके लिए समाधान प्राप्त करने का समय तेजी से अनदेखा किया जाता है$$ $ इनलाइन $ O (2 ^ n \ log n) $ इनलाइन $ (झांग, 1982)। शलजम के विपरीत, इसके घातांक एल्गोरिथ्म के साथ बेल्टवे समस्या को किसी भी तरह से हल नहीं माना जा सकता है।

जैव सूचना विज्ञान के संदर्भ में बेल्टवे की समस्याओं को हल करने का महत्व

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

एकमात्र सवाल यह है कि एनआरपी को कैसे और कहां देखना है? वे बहुत प्रभावी हैं, इसलिए सेल को बड़ी मात्रा में उन्हें उत्पादन करने की बिल्कुल आवश्यकता नहीं है, और उनकी सांद्रता नगण्य है। इसलिए ~ 1% की कम सटीकता और विशाल अभिकर्मक और समय की लागत के साथ रासायनिक निष्कर्षण विधियां बेकार हैं। अगला। वे डीएनए में एन्कोडेड नहीं हैं, जिसका अर्थ है कि सभी डेटाबेस जो जीनोम के डिकोडिंग के दौरान जमा हुए थे, और जैव सूचना विज्ञान और जीनोमिक्स के सभी तरीके भी बेकार हैं। किसी चीज़ को खोजने का एकमात्र तरीका भौतिक तरीकों के माध्यम से है, अर्थात्, मास स्पेक्ट्रोस्कोपी। इसके अलावा, आधुनिक स्पेक्ट्रोमीटर में पदार्थों का पता लगाने का स्तर इतना अधिक है कि यह किसी को नगण्य मात्रा में खोजने की अनुमति देता है, कुल मिलाकर> ~ 800 अणु (अटो-मोलर रेंज या एकाग्रता)$$ $ इनलाइन $ 10 ^ {- 18} $ इनलाइन $ )।

"

मास स्पेक्ट्रोमीटर कैसे काम करता है? डिवाइस के कामकाजी कक्ष में, अणुओं को टुकड़ों में विभाजित किया जाता है (अक्सर एक दूसरे के साथ उनकी टक्करों के माध्यम से, बाहरी प्रभावों के कारण कम अक्सर)। इन टुकड़ों को आयनित किया जाता है, और फिर एक बाहरी विद्युत चुम्बकीय क्षेत्र में त्वरित और अलग किया जाता है। विभाजक या तो उस समय तक होता है जब डिटेक्टर पहुंचता है, या चुंबकीय क्षेत्र में मोड़ के कोण से, क्योंकि टुकड़े का द्रव्यमान बड़ा होता है और इसका चार्ज कम होता है, यह उतना ही अधिक भद्दा होता है। इस प्रकार, द्रव्यमान स्पेक्ट्रोमीटर टुकड़ों के द्रव्यमान का "वजन" करता है। इसके अलावा, "वजन" चरणों में एक ही द्रव्यमान (अधिक सटीक, एक मूल्य के साथ) को बार-बार फ़िल्टर करके किया जा सकता है$$ $ इनलाइन $ m / z $ इनलाइन $ ) और आगे अलगाव के साथ विखंडन के माध्यम से उन्हें ड्राइविंग। दो-चरण द्रव्यमान वाले स्पेक्ट्रोमीटर व्यापक रूप से वितरित किए जाते हैं और इन्हें टेंडेम मास स्पेक्ट्रोमेटर्स कहा जाता है, मल्टी-स्टेज मास स्पेक्ट्रोमेटर्स अत्यंत दुर्लभ हैं, और बस के रूप में नामित हैं$$ $ इनलाइन $ एमएस ^ एन $ इनलाइन $ जहाँ$$ $ इनलाइन $ n $ इनलाइन $ - चरणों की संख्या। और यहां यह कार्य दिखाई देता है कि कैसे, किसी भी अणु के सभी प्रकार के टुकड़ों के द्रव्यमान को जानने के लिए, इसकी संरचना को जानने के लिए? तो हम क्रमशः रैखिक और चक्रीय पेप्टाइड्स के लिए शलजम और बेल्टवे की समस्याओं के लिए आए थे।

मैं और अधिक विस्तार से बताऊंगा कि एक चक्रीय पेप्टाइड के उदाहरण का उपयोग करके संकेतित समस्याओं के लिए एक बायोमोलेक्यूल की संरचना को बहाल करने का कार्य कैसे किया जाता है।



विखंडन के पहले चरण में चक्रीय पेप्टाइड एबीसीडी को 4 स्थानों में तोड़ा जा सकता है, या तो डीए लिंकेज द्वारा, या एबी, बीसी या सीडी द्वारा, 4 संभव रैखिक पेप्टाइड्स का निर्माण - या तो एबीसीडी, बीसीडीए, सीडीएबी या डीएबीसी। चूंकि बड़ी संख्या में समान पेप्टाइड्स स्पेक्ट्रोमीटर से गुजरते हैं, इसलिए हमारे पास आउटपुट पर सभी 4 प्रकार के टुकड़े होंगे। इसके अलावा, हम ध्यान दें कि सभी टुकड़ों में समान द्रव्यमान है, और इसे पहले चरण में अलग नहीं किया जा सकता है। दूसरे चरण में, अलग-अलग द्रव्यमान A और BCD, AB और CD, ABC और D के साथ छोटे टुकड़े बनाकर और संबंधित द्रव्यमान स्पेक्ट्रम का निर्माण करते हुए, रैखिक टुकड़े ABCD को तीन स्थानों पर तोड़ा जा सकता है। इस स्पेक्ट्रम में, x अक्ष के साथ खंड द्रव्यमान और y अक्ष के साथ दिए गए द्रव्यमान के साथ छोटे टुकड़ों की संख्या होती है। इसी तरह, बीसीडीए, सीडीएबी और डीएबीसी के शेष तीन रैखिक अंशों के लिए स्पेक्ट्रा का गठन किया जाता है। चूंकि सभी 4 बड़े टुकड़े दूसरे चरण में चले गए, इसलिए उनके सभी स्पेक्ट्रा को जोड़ दिया गया। कुल मिलाकर, परिणाम कुछ द्रव्यमान है$$ $ इनलाइन $ \ {m_1 ^ {n_1}, m_2 ^ {n_2}, .., m_q ^ {n_q} \} $ इनलाइन $ जहाँ$$ $ इनलाइन $ m_i $ इनलाइन $ - कुछ द्रव्यमान, और$$ $ इनलाइन $ n_i $ इनलाइन $ - इसकी पुनरावृत्ति की आवृत्ति। इसी समय, हम नहीं जानते कि यह द्रव्यमान किस टुकड़े का है और क्या यह टुकड़ा अद्वितीय है, क्योंकि विभिन्न टुकड़ों में एक द्रव्यमान हो सकता है। पेप्टाइड में बंध एक दूसरे से जितने दूर होते हैं, उनके बीच पेप्टाइड टुकड़े का द्रव्यमान उतना ही अधिक होता है। अर्थात्, चक्रीय पेप्टाइड में तत्वों के क्रम को बहाल करने का कार्य एक बेल्टवे समस्या को कम करता है, जिसमें सेट के तत्व होते हैं$$ $ इनलाइन $ X $ इनलाइन $ पेप्टाइड में बंधन हैं, और एक भीड़ के तत्व हैं$$ $ इनलाइन $ \ Delta X $ इनलाइन $ - बांड के बीच टुकड़ों का द्रव्यमान।

बेल्टवे की समस्याओं को हल करने के लिए बहुपद समय के साथ एक एल्गोरिथ्म के अस्तित्व की प्रत्याशा

मेरे अनुभव से और उन लोगों के साथ संवाद करने से जिन्होंने इस समस्या को हल करने के लिए वास्तव में कुछ करने की कोशिश की है, मैंने देखा कि अधिकांश लोग इसे सामान्य मामले में या पूर्णांक डेटा के लिए एक संकीर्ण सीमा में हल करने की कोशिश करते हैं, जैसे कि (1,) 50)। दोनों विकल्प विफलता के लिए बर्बाद हैं। सामान्य मामले के लिए, यह साबित हुआ कि बेल्टवे समस्याओं के समाधान की कुल संख्या एक आयामी मामले में$$ $ इनलाइन $ S_1 (n) $ इनलाइन $ मूल्यों द्वारा सीमित (लेमके, 2003)

$$$$ प्रदर्शन $ $ e ^ {2 ^ {\ frac {\ nn n} {\ ln \ ln n} + o (1)}} \ leq S_1 (n) \ leq \ frac {1} {2} ^ {n-2} $ $ प्रदर्शन $ $

जिसका अर्थ है कि एसिम्पोटिक्स में समाधानों की एक घातीय संख्या की उपस्थिति$$ $ इनलाइन $ n \ rightarrow \ infty $ इनलाइन $ । जाहिर है, अगर समाधानों की संख्या तेजी से बढ़ती है, तो उनकी प्राप्ति का समय अधिक धीरे-धीरे नहीं बढ़ सकता है। यही है, सामान्य मामले के लिए, बहुपद समय समाधान प्राप्त करना असंभव है। एक संकीर्ण श्रेणी में पूर्णांक डेटा के लिए, सब कुछ प्रयोगात्मक रूप से सत्यापित किया जा सकता है, क्योंकि यह कोड लिखना बहुत मुश्किल नहीं है जो संपूर्ण खोज द्वारा समाधान की तलाश में है। छोटे के लिए$$ $ इनलाइन $ n $ इनलाइन $ ऐसा कोड बहुत लंबा नहीं लगेगा। इस तरह के कोड के परीक्षण के परिणाम से पता चलेगा कि इस तरह की डेटा शर्तों के तहत किसी भी सेट के लिए विभिन्न समाधानों की कुल संख्या$$ $ इनलाइन $ \ Delta X $ इनलाइन $ पहले से ही छोटे पर$$ $ इनलाइन $ n $ इनलाइन $ भी बहुत तेजी से बढ़ रहा है।

इन तथ्यों के बारे में जानने के बाद, आप इस कार्य को पूरा कर सकते हैं। मैं मानता हूं कि यह एक कारण है कि बेल्टवे की समस्या को अभी भी अनसुलझा माना जाता है। हालांकि, कमियां मौजूद हैं। स्मरण करो कि घातीय कार्य$$ $ इनलाइन $ e ^ {\ अल्फा x} $ इनलाइन $ बहुत दिलचस्प व्यवहार करता है। सबसे पहले, यह बहुत धीरे-धीरे बढ़ता है, 0 से 1 से एक बड़े अंतर से बढ़ता है$$ $ इनलाइन $ \ infty $ इनलाइन $ 0 तक, फिर इसकी वृद्धि अधिक से अधिक बढ़ जाती है। हालांकि, मूल्य कम है$$ $ इनलाइन $ \ अल्फा $ इनलाइन $ अधिक से अधिक मूल्य होना चाहिए$$ $ इनलाइन $ x $ इनलाइन $ ताकि फ़ंक्शन का परिणाम कुछ निर्धारित मूल्य से अधिक हो$$ $ इनलाइन $ y = \ xi $ इनलाइन $ । इस तरह के एक मूल्य के रूप में, एक संख्या चुनना सुविधाजनक है$$ $ इनलाइन $ \ xi = 2 $ इनलाइन $ , उससे पहले एकमात्र समाधान, उसके बाद कई निर्णय हैं। प्रश्न। और क्या किसी ने इनपुट पर क्या डेटा मिलता है उस पर निर्णय की संख्या की निर्भरता की जांच की? हां, मैंने किया। क्रोएशियाई महिला गणितज्ञ तमारा डाकिस (डैसिक, 2000) द्वारा एक अद्भुत पीएचडी शोध प्रबंध किया गया है, जिसमें उन्होंने निर्धारित किया है कि बहुपद समय में समस्या को हल करने के लिए इनपुट डेटा को किन परिस्थितियों में संतुष्ट करना होगा। उनमें से सबसे महत्वपूर्ण समाधान की विशिष्टता और इनपुट डेटा के सेट में दोहराव की अनुपस्थिति है।$$ $ इनलाइन $ \ Delta X $ इनलाइन $ । उसके पीएचडी शोध प्रबंध का स्तर बहुत अधिक है। यह दुर्भाग्यपूर्ण है कि इस छात्र ने खुद को केवल एक टर्नपाइक समस्या तक सीमित कर दिया, मुझे विश्वास है कि अगर उसने बेल्टवे की समस्या में अपनी रुचि को बदल दिया होता, तो यह लंबे समय तक हल हो जाता।

बहुपद समय सुलझाने वाली बेल्टवे समस्याओं के साथ एक एल्गोरिथ्म प्राप्त करना

डेटा को खोजना संभव था जिसके लिए संयोग से वांछित एल्गोरिदम का निर्माण करना संभव है। इसने अतिरिक्त विचार रखे। अवलोकन से मुख्य विचार उत्पन्न हुआ (ऊपर देखें) कि चक्रीय पेप्टाइड का स्पेक्ट्रम सभी रैखिक पेप्टाइड्स के स्पेक्ट्रा का योग है जो सिंगल रिंग टूटने पर बनता है। चूंकि पेप्टाइड में अमीनो एसिड का क्रम किसी भी तरह के रैखिक पेप्टाइड से बहाल किया जा सकता है, इसलिए स्पेक्ट्रम में लाइनों की कुल संख्या महत्वपूर्ण है ($$ $ इनलाइन $ n $ इनलाइन $ समय कहाँ$$ $ इनलाइन $ n $ इनलाइन $ - पेप्टाइड में अमीनो एसिड की संख्या) अत्यधिक है। प्रश्न केवल यह है कि किस लाइन को स्पेक्ट्रम से बाहर रखा जाना चाहिए ताकि अनुक्रम को पुनर्स्थापित करने की क्षमता न खो जाए। चूंकि दोनों कार्य (बड़े पैमाने पर स्पेक्ट्रम और बेल्टवे समस्या से चक्रीय पेप्टाइड अनुक्रम की बहाली) गणितीय रूप से आइसोमॉर्फिक हैं, इसलिए कई का पतला होना भी संभव है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ ।

पतले संचालन$$ $ इनलाइन $ \ Delta X $ इनलाइन $ सेट के स्थानीय समरूपता का उपयोग करके निर्माण किया गया था$$ $ इनलाइन $ \ Delta X $ इनलाइन $ (फ़ोमिन, 2016 ए)।

• समभागीकरण। पहला ऑपरेशन सेट के एक मनमाने तत्व का चयन करना है$$ $ इनलाइन $ x _ {\ mu} \ in \ Delta X $ इनलाइन $ और से हटा दें$$ $ इनलाइन $ \ Delta X $ इनलाइन $ उन सभी तत्वों को छोड़कर जिनके पास अंक के संबंध में सममित जोड़े हैं$$ $ इनलाइन $ x _ {\ mu} / 2 $ इनलाइन $ और$$ $ इनलाइन $ (L + x _ {\ mu}) / 2 $ इनलाइन $ जहाँ$$ $ इनलाइन $ एल $ इनलाइन $ - परिधि (मुझे याद है कि बेल्टवे मामले में, सभी बिंदु सर्कल पर स्थित हैं)।
• आंशिक समाधान दृढ़ संकल्प। दूसरा ऑपरेशन समाधान के बारे में अनुमान का उपयोग करता है, अर्थात्, व्यक्तिगत बिंदुओं का ज्ञान जो समाधान से संबंधित है, तथाकथित आंशिक समाधान। कई में से$$ $ इनलाइन $ \ Delta X $ इनलाइन $ सभी तत्व भी हटा दिए गए हैं, सिवाय इसके कि स्थिति को संतुष्ट करें - यदि हम एक आंशिक समाधान के सभी बिंदुओं के लिए परीक्षण किए जा रहे बिंदु से दूरी को मापते हैं, तो सभी प्राप्त मानों में हैं$$ $ इनलाइन $ \ Delta X $ इनलाइन $ । मैं स्पष्ट करूँगा कि यदि प्राप्त की गई कम से कम एक दूरी अनुपस्थित है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ तब बात को नजरअंदाज कर दिया जाता है।

सिद्ध किया गया कि दोनों ऑपरेशन सेट से बाहर पतले हैं$$ $ इनलाइन $ \ Delta X $ इनलाइन $ , लेकिन इसमें अभी भी समाधान को बहाल करने के लिए पर्याप्त तत्व बाकी हैं$$ $ इनलाइन $ X $ इनलाइन $ । इन ऑपरेशनों का उपयोग करते हुए, बेल्टवे समस्या (फ़ोमिन, 2016 बी) को हल करने के लिए सी ++ में एक एल्गोरिथ्म बनाया और कार्यान्वित किया गया था। एल्गोरिथ्म क्लासिकल बैकट्रैकिंग एल्गोरिथ्म से थोड़ा अलग है (अर्थात, हम संभव विकल्पों की गणना करके एक समाधान बनाने की कोशिश करते हैं और अगर हमें निर्माण के दौरान कोई त्रुटि मिलती है)। फर्क सिर्फ इतना है कि सेट को संकीर्ण करना$$ $ इनलाइन $ \ Delta X $ इनलाइन $ हमें परखने के लिए काफी कम विकल्प हो जाते हैं।

यहाँ कितने का एक उदाहरण है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ जब पतला हो।



कम्प्यूटेशनल प्रयोगों लंबाई के बेतरतीब ढंग से उत्पन्न चक्रीय पेप्टाइड्स के लिए प्रदर्शन किया गया$$ $ इनलाइन $ n $ इनलाइन $ 10 से 1000 अमीनो एसिड (एक लघुगणकीय पैमाने पर अक्षीय अक्ष)। एब्सिस्सा एक लॉगरिदमिक पैमाने पर भी दिखाता है कि सेट में तत्वों की संख्या विभिन्न ऑपरेशनों से कम हो गई है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ इकाइयों में$$ $ इनलाइन $ n $ इनलाइन $ । इस तरह का प्रतिनिधित्व बिल्कुल असामान्य है, इसलिए मैं इसे एक उदाहरण पर पढ़ा जाता हूं। हम बाएं आरेख को देखते हैं। पेप्टाइड की लंबाई है$$ $ इनलाइन $ n = 100 $ इनलाइन $ । उसके लिए, सेट में तत्वों की संख्या$$ $ इनलाइन $ \ Delta X $ इनलाइन $ है$$ $ इनलाइन $ n ^ 2 = 10000 $ इनलाइन $ (यह ऊपरी धराशायी रेखा पर एक बिंदु है$$ $ इनलाइन $ y = n ^ 2 $ इनलाइन $ )। सेट से हटाने के बाद$$ $ इनलाइन $ \ Delta X $ इनलाइन $ तत्वों को दोहराते हुए, तत्वों की संख्या$$ $ इनलाइन $ \ Delta X $ इनलाइन $ तक घट जाती है$$ $ इनलाइन $ n_D \ लगभग n ^ {1.9} \ लगभग 6300 $ इनलाइन $ (क्रॉस के साथ सर्कल)। समरूपता के बाद, तत्वों की संख्या घट जाती है$$ $ इनलाइन $ n_S \ लगभग n ^ {1.75} \ लगभग 3100 $ इनलाइन $ (काले घेरे), और आंशिक समाधान द्वारा सजा के बाद$$ $ इनलाइन $ n_C \ लगभग n ^ {1.35} \ लगभग 500 $ इनलाइन $ (क्रॉस)। कुल, सेट की कुल मात्रा$$ $ इनलाइन $ \ Delta X $ इनलाइन $ केवल 20 बार घटाया गया। एक ही लंबाई के पेप्टाइड के लिए, लेकिन सही आरेख में, संकुचन से आता है$$ $ इनलाइन $ n ^ 2 = 10000 $ इनलाइन $ को$$ $ इनलाइन $ N_C \ लगभग n \ लगभग 100 $ इनलाइन $ , यानी 100 गुना।

ध्यान दें कि बाएं आरेख के लिए परीक्षण मामलों की पीढ़ी का प्रदर्शन किया जाता है ताकि दोहराव का स्तर$$ $ इनलाइन $ k_ {डुप} $ इनलाइन $ में$$ $ इनलाइन $ \ Delta X $ इनलाइन $ 0.1 से 0.3 की सीमा में था, और दाईं ओर - 0.1 से कम था। दोहराव के स्तर को परिभाषित किया गया है$$ $ इनलाइन $ k_ {dup} = 2- \ log {N_u} / \ log {n} $ इनलाइन $ जहाँ$$ $ इनलाइन $ N_u $ इनलाइन $ - सेट में अद्वितीय तत्वों की संख्या$$ $ इनलाइन $ \ Delta X $ इनलाइन $ । ऐसी परिभाषा एक स्वाभाविक परिणाम देती है: सेट में डुप्लिकेट की अनुपस्थिति में$$ $ इनलाइन $ \ Delta X $ इनलाइन $ इसकी शक्ति बराबर है$$ $ इनलाइन $ N_u = n ^ 2 $ इनलाइन $ और$$ $ इनलाइन $ k_ {डुप} = 0 $ इनलाइन $ अधिकतम संभव दोहराव पर$$ $ इनलाइन $ N_u = n $ इनलाइन $ और$$ $ इनलाइन $ k_ {डुप} = 1 $ इनलाइन $ । नकल के विभिन्न स्तरों को प्रदान करना संभव कैसे करें, मैं थोड़ी देर बाद कहूंगा। आरेख दिखाते हैं कि नकल का स्तर जितना कम होगा, उतना ही पतला होगा$$ $ इनलाइन $ \ Delta X $ इनलाइन $ जब$$ $ इनलाइन $ k_ {डुप} <0.1 $ इनलाइन $ पतले में तत्वों की संख्या$$ $ इनलाइन $ \ Delta X $ इनलाइन $ आम तौर पर अपनी सीमा तक पहुँचता है$$ $ इनलाइन $ O (n ^ 2) \ rightarrow O (n) $ इनलाइन $ , क्योंकि निर्धारित सेट से कम है$$ $ इनलाइन $ O (n) $ इनलाइन $ तत्व प्राप्त नहीं किए जा सकते हैं (एक समाधान प्राप्त करने के लिए ऑपरेशन पर्याप्त तत्व संग्रहीत करते हैं$$ $ इनलाइन $ n $ इनलाइन $ तत्व)। सेट की शक्ति को कम करने का तथ्य$$ $ इनलाइन $ \ Delta X $ इनलाइन $ निचली सीमा बहुत महत्वपूर्ण है, यह वह है जो समाधान प्राप्त करने की कम्प्यूटेशनल जटिलता में नाटकीय परिवर्तन की ओर जाता है।

बैकग्राउंडिंग एल्गोरिथ्म में थिनिंग ऑपरेशन डालने और बेल्टवे की समस्या को हल करने के बाद, टमारा डैक ने टर्नपाइक समस्या के बारे में जो बात की, उसका एक पूरा एनालॉग सामने आया था। मैं आपको याद दिला दूं। उन्होंने कहा कि टर्नपाइक समस्याओं के लिए बहुपद समय में समाधान प्राप्त करना संभव है यदि समाधान अद्वितीय है और इसमें कोई दोहराव नहीं है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ । यह पता चला कि दोहराव की पूर्ण अनुपस्थिति आवश्यक नहीं है (यह वास्तविक डेटा के लिए शायद ही संभव है), यह पर्याप्त है कि इसका स्तर काफी छोटा होगा। नीचे दिए गए आंकड़े से पता चलता है कि पेप्टाइड की लंबाई और अंदर दोहराव के स्तर के आधार पर बेल्टवे समस्या का समाधान प्राप्त करने के लिए कितना समय आवश्यक है$$ $ इनलाइन $ \ Delta X $ इनलाइन $ ।



आकृति में, फरस्किसा और ऑर्डिनेट दोनों एक लघुगणकीय पैमाने पर दिए गए हैं। यह आपको स्पष्ट रूप से देखने की अनुमति देता है कि क्या अनुक्रम लंबाई पर गिनती समय की निर्भरता है$$ $ इनलाइन $ T = f (n) $ इनलाइन $ घातीय (सीधी रेखा) या बहुपद (लॉग-आकार वक्र)। जैसा कि आरेखों में देखा जा सकता है, निम्न स्तर के दोहराव (सही आरेख) के साथ, समाधान को बहुपद समय में प्राप्त किया जाता है। खैर, अधिक सटीक होने के लिए, समाधान द्विघात समय में प्राप्त किया जाता है। यह तब होता है जब थिनिंग ऑपरेशन सेट की शक्ति को कम सीमा तक कम कर देता है।$$ $ इनलाइन $ O (n ^ 2) \ rightarrow O (n) $ इनलाइन $ इसमें कुछ बिंदु शेष हैं, रिटर्न जब विकल्पों पर पुनरावृत्ति एकल हो जाती है, और संक्षेप में एल्गोरिथ्म विकल्पों पर पुनरावृति करना बंद कर देता है, लेकिन बस जो बचा है उससे एक समाधान का निर्माण करता है।

PS खैर, मैं दोहराव के विभिन्न स्तरों पर सेट की पीढ़ी के बारे में अंतिम रहस्य प्रकट करूंगा। यह डेटा प्रस्तुति की विभिन्न सटीकता के कारण है। यदि डेटा कम सटीकता (उदाहरण के लिए, पूर्णांक पर गोलाई) के साथ उत्पन्न होता है, तो दोहराव का स्तर ऊंचा हो जाता है, 0.3 से अधिक।यदि डेटा अच्छी सटीकता के साथ उत्पन्न होता है, उदाहरण के लिए, 3 दशमलव स्थानों तक, तो दोहराव का स्तर तेजी से घट जाता है, 0.1 से कम। और यहाँ से अंतिम सबसे महत्वपूर्ण टिप्पणी इस प्रकार है।

वास्तविक आंकड़ों के लिए, माप की निरंतर बढ़ती सटीकता की स्थितियों में, बेल्टवे समस्या वास्तविक समय में हल करने योग्य हो जाती है।


साहित्य।

1. डाकिक, टी। (2000)। टर्नपाइक समस्या पर। पीएचडी थीसिस, साइमन फ्रेजर विश्वविद्यालय।
2. फ़ोमिन। ई। (२०१६) एन ^ २ के बहुस्तरीय बिंदु से अंक के एक सेट के पुनर्निर्माण के लिए एक सरल दृष्टिकोण 2 सीक्वेंसिंग प्रॉब्लम के लिए २ चरण: आई थ्योरी। जे कंपुत बायोल। 2016, 23 (9): 769-75।
3. फ़ोमिन। ई। (२०१६) एन ^ २ के मल्टीसेट से पॉइंट्स के एक सेट के पुनर्निर्माण के लिए एक साधारण दृष्टिकोण 2 सीक्वेंसिंग प्रॉब्लम के लिए २ कदम २: २। एल्गोरिथ्म। जे कंपुत बायोल। 2016, 23 (12): 934-942।
4. लेमके, पी।, स्कीना, एस।, और स्मिथ, डब्ल्यू। (2003)। इंटरपॉइंट डिस्टर्बेंस से रीकंस्ट्रक्टिंग सेट। असतत और कम्प्यूटेशनल ज्यामिति एल्गोरिदम और संयोजन, 25: 597–631।
5. स्कीना, एस।, स्मिथ, डब्ल्यू।, और लेमके, पी। (1990)। इंटरपॉइंट दूरियों से सेट का पुनर्निर्माण। कम्प्यूटेशनल ज्यामिति पर छठे एसीएम संगोष्ठी की कार्यवाही में, पृष्ठ 332-339। बर्कले, सीए
6. झांग, जेड 1982। आंशिक रूप से डाइजेस्ट मैपिंग एल्गोरिथ्म के लिए एक घातीय उदाहरण। जे। कॉम्प। बॉय। 1, 235-240।