इष्टतम मिलान

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

एल्गोरिथम

मान लें $S=(s_{1},s_{2},s_{3},\ldots s_{T})$ संभव स्तिथियों के परिमित समुच्चय से संबंधित स्तिथि $s_{i}$ का अनुक्रम है। आइए ${\mathbf {S} }$ अनुक्रम स्थान को निरूपित करते हैं अर्थात जो स्तिथियों के सभी संभावित अनुक्रमों का समुच्चय है।

इष्टतम मिलान एल्गोरिदम सरल संचालन बीजगणित को परिभाषित करके कार्य करते हैं जो अनुक्रमों में परिवर्तन करते हैं, अर्थात संचालनोंका समुच्चय $a_{i}:{\mathbf {S} }\rightarrow {\mathbf {S} }$ है। सबसे सरल दृष्टिकोण में, अनुक्रमों को परिवर्तित करने के लिए मात्र तीन मूलभूत संक्रियाओं से बने समुच्चय का उपयोग किया जाता है-

• अनुक्रम $a_{s'}^{\rm {Ins}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{2},s_{3},\ldots ,s',\ldots s_{T})$ में स्थिति $s$ प्रविष्ट किया गया है,
• स्थिति को अनुक्रम $a_{s_{2}}^{\rm {Del}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s_{1},s_{3},\ldots s_{T})$ से विस्थापित कर दिया जाता है और
• स्थिति $s_{1}$ को स्थिति $s'_{1}$, $a_{s_{1},s'_{1}}^{\rm {Sub}}(s_{1},s_{2},s_{3},\ldots s_{T})=(s'_{1},s_{2},s_{3},\ldots s_{T})$ द्वारा प्रतिस्थापित किया जाता है।

अब कल्पना कीजिए कि व्यय $c(a_{i})\in {\mathbf {R} }_{0}^{+}$ प्रत्येक संचालन से जुड़ा है। दो अनुक्रमों $S_{1}$ और $S_{2}$ को देखते हुए, बीजगणित से संचालनों का उपयोग करके $S_{1}$ से $S_{2}$ प्राप्त करने के व्यय को मापने का विचार है। मान लें $A={a_{1},a_{2},\ldots a_{n}}$ संचालनों का अनुक्रम है जिस प्रकार इस अनुक्रम के सभी संचालनों के अनुप्रयोग $A$ को प्रथम अनुक्रम $S_{1}$ के लिए द्वितीय अनुक्रम $S_{2}$:$S_{2}=a_{1}\circ a_{2}\circ \ldots \circ a_{n}(S_{1})$ देता है, जहां $a_{1}\circ a_{2}$ मिश्रण संचालन को दर्शाता है।

इस समुच्चय से हम व्यय $c(A)=\sum _{i=1}^{n}c(a_{i})$ को जोड़ते हैं, यह परिवर्तन के कुल व्यय का प्रतिनिधित्व करता है। इस बिंदु पर विचार करना चाहिए कि इस प्रकार के विभिन्न अनुक्रम $A$ उपस्थित हो सकते हैं जो $S_{1}$ को $S_{2}$ में परिवर्तित करते हैं; इस प्रकार के दृश्यों में से सबसे अल्पमूल्य चयन करना उचित विकल्प है। इस प्रकार हम दूरी को $d(S_1,{}_{}$