क्या यह संयोजी अनुकूलन समस्या एनपी-हार्ड है?

Question

मैं एक संयोजन अनुकूलन समस्या पर काम कर रहा हूं जो मुझे संदेह है कि एनपी-हार्ड है, और एक जेनेटिक एल्गोरिदम हमारे डेटासेट के साथ अच्छी तरह से काम कर रहा है। हम एक शोध समूह हैं और हमारे परिणामों को हमारे क्षेत्र (गणित या सीएस में नहीं) में प्रकाशित करने की योजना बना रहे हैं, और समीक्षा के लिए पांडुलिपि भेजने से पहले मैं एनपी-कड़ी प्रश्न का पता लगाना चाहता हूं।

1) मुझे पता है कि इस विशेष अनुकूलन समस्या का अध्ययन किया गया है कि क्या करना चाहते हैं:

दो मुख्य सवाल कर रहे हैं। मैंने ज्योतिष की भारी खोज की है लेकिन कुछ भी बिल्कुल नहीं देखा है।

2) यदि समस्या का अध्ययन नहीं किया गया है, तो मैं कम करने योग्य सबूत करने में एक क्रैक ले सकता हूं, और कुछ पॉइंटर्स को एनपी-पूर्ण उम्मीदवारों को कमी के लिए पसंद करना चाहूंगा।

समस्या को बाद के रूप में, और द्विपक्षीय ग्राफ समस्या के रूप में दो तरीकों से वर्णित किया जा सकता है।

बाद के स्वाद में, मैं एक "आराम" अनुवर्ती खोजना चाहता हूं जो क्रमपरिवर्तन की अनुमति देता है, और क्रमपरिवर्तन गणना को कम करने के लिए अनुकूलित करता है। (= किसी अन्य चार।)

क्वेरी:: abc, लक्ष्य: ..babc, परिणाम: एबीसी (सामान्य परिणाम को)

क्वेरी: एबीसी, लक्ष्य: ..baca, परिणाम: बक (परिणाम को उदाहरण के लिए एक क्रमपरिवर्तन के साथ)

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

प्रश्न 1 या 2 पर विशेषज्ञों से कोई विचार?

अग्रिम धन्यवाद!

Answer 1

बस कुछ विचार: क्या यह किसी सरणी (MIN-SBR) को सॉर्ट करने के लिए आवश्यक स्वैप की न्यूनतम संख्या को खोजने के बराबर है? यदि हां, तो यह NP-Hard है।

(Btw, आप कुछ similar to this पर काम कर रहे हैं?)

Answer 2

"शब्द समस्या" के साथ समस्या यह कठिन है, है ना होना चाहिए? - जे -16 एसडीआईजेड 14

हां, लक्ष्य में चार की कई घटनाएं होने से मेरी समस्या MIN-SBR से कठिन होती है, इसलिए उस कोण से मेरी समस्या कम से कम एनपी-पूर्ण के रूप में कठिन होगी। दूसरी तरफ, मैं अभी तक स्पष्ट नहीं हूं कि ब्लॉक रिवर्सल की उनकी केंद्रीय धारणा एनपी-पूर्णता के मेरे दावे को कैसे प्रभावित करेगी।

मुझे यकीन है कि यह जानना अच्छा होगा कि मेरे अनुकूलन को बहुपद समय में हल किया जा सकता है या नहीं। एक और तरीका रखो, यह निश्चित रूप से शर्मनाक होगा यदि कोई समीक्षक छद्म कोड की पांच पंक्तियों के साथ वापस आया जो ओ (एन) में वैश्विक अधिकतम पाता है ..

Answer 3

piccolbo करने के लिए

:

आप गणित या सीएस में प्रकाशित नहीं कर रहे हैं, तो एक एनपी पूर्णता परिणाम अप्रासंगिक हो जाएगा और सिर्फ जीवविज्ञानी जलन या एमडी समीक्षा कर रही है। वहाँ गया।

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

क्रमपरिवर्तन का आपका अर्थ क्या है? केवल दो अक्षर शामिल हैं? या केवल दो आसन्न लोग? एक सामान्य क्रम में मुझे लगता है कि एक क्रमपरिवर्तन आपको पूरी स्ट्रिंग को पुनर्व्यवस्थित करने की अनुमति देता है, लेकिन फिर समस्या तुच्छ हो जाती है?

यह लक्ष्य स्ट्रिंग में क्रमपरिवर्तन की अनियंत्रित संख्या है, और क्रमपरिवर्तन की संख्या को कम करने (यानी, द्विपक्षीय फॉर्मूलेशन में किनारे क्रॉसिंग) उद्देश्य कार्य है। क्रमपरिवर्तन कहीं भी हो सकते हैं और उन्हें स्वतंत्र रूप से वितरित किया जाता है, इसलिए मौके से आसन्नता (अकसर) होती है। क्वेरी और लक्ष्य तारों का क्रम तय किया गया है, इसलिए मैं कोई पुनर्गठन नहीं कर सकता।

यदि मैं इसे एनपी-हार्ड साबित करता हूं, तो क्या मुझे सह-लेखकता मिलती है? एबीसी लक्ष्य:: ..c.b.a.a परिणाम:

के सबूत :-)

Answer 4

होता है, क्वेरी देखते हैं CBA, तीन क्रमपरिवर्तन हो तो (अवधि के आपके उपयोग के अनुसार)? यदि ऐसा है, तो हो सकता है कि आप क्रमपरिवर्तन के बजाय पारदर्शिता का मतलब हो। एक पारदर्शिता दो आसन्न पात्रों का स्वैपिंग है।

अच्छा सवाल। हम क्वेरी से मैपिंग में रूचि रखते हैं -> लक्ष्य जिसमें क्रॉसिंग संभव है। मूल पोस्ट में द्विपक्षीय किनारे क्रॉसिंग का उल्लेख करने के लिए यह बहुत प्रेरणा है। वैकल्पिक रूप से, आप मानचित्रण पर स्पीरमैन के Rho जैसे रैंक आंकड़े को अधिकतम करने के बारे में सोच सकते हैं।

इसके अलावा, जिज्ञासा से, क्वेरी/लक्ष्य में कितने अद्वितीय वर्ण हैं? - जस्टिन छील 18

विशिष्ट क्वेरी: 100, सामान्य लक्ष्य: 1000. कॉम्बिनेटोरियल, यह एक विशाल समाधान स्थान है।

Answer 5

मुझे नहीं लगता कि यह एनपी-हार्ड है। पेवज़नर और हन्नाहली द्वारा काम देखें। एक पेपर जो दिमाग में आता है वह `गोभी से टर्निप 'शीर्षक है। विचार एक स्ट्रिंग से दूसरे स्ट्रिंग में जाने के लिए न्यूनतम संख्या में उलटा खोजना है। इसके लिए उनके पास पॉलीटाइम एल्गोरिदम है।