कवरिंग सेट के निर्माण के लिए एल्गोरिदम

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

यह स्पष्ट करने के लिए कि क्या दांव पर है, कल्पना करें कि हमें एक कार्यक्रम या साइट का परीक्षण करने की आवश्यकता है। एक बहुत अच्छा उदाहरण एक वेब फॉर्म का परीक्षण कर रहा है, उदाहरण के लिए, पंजीकरण या खोज करने के लिए। सवाल यह है कि इसमें कौन सी त्रुटियां होने की सबसे अधिक संभावना है? हमें फॉर्म में 6 प्रश्न हैं, जिनमें से प्रत्येक के लिए 10 संभावित उत्तर संभव हैं। मान लें कि पूरे उपयोगकर्ताओं ने पृष्ठ का दौरा किया, और उनमें से प्रत्येक ने विशिष्ट रूप से उत्तर दिया। अब कल्पना करें कि उत्तर भरने के लिए फॉर्म में एक त्रुटि छिपी हुई है। यदि सभी 6 प्रश्नों के उत्तरों के एक निश्चित संयोजन के साथ एक त्रुटि का पता लगाया जाता है, तो केवल एक व्यक्ति उस पर ठोकर खाएगा। यदि कुछ 3 प्रश्नों के विशिष्ट उत्तरों का एक समूह एकत्र होने पर त्रुटि होती है, तो त्रुटि खोजने वालों की संख्या बढ़कर एक हजार हो जाएगी। जाहिर है, एक त्रुटि के लिए आवश्यक संयोजन में जितने कम तत्व होंगे, उतने अधिक लोग इसके साथ मिलेंगे। तदनुसार, अब हम चुनौती का सामना करते हैं: यदि हम सभी त्रुटियों को नहीं पा सकते हैं, तो कम से कम हम सबसे महत्वपूर्ण वाले मिलेंगे, अर्थात, जो कि अधिकांश उपयोगकर्ता ठोकर खाएंगे।
इस प्रकार, हम परीक्षण मामलों (और कम, बेहतर), जब हम सबसे आसानी से सुलभ त्रुटियों के पार आ जाएगा जो enumerating बनाना होगा। मान लीजिए कि हमारे पास बहुत सारे प्रश्न हैं, जो हम उनमें से प्रत्येक के लिए उत्तर विकल्पों की संख्या से पूछते हैं: ए = {2, 3, 5, 2, ...}। आज्ञा देना प्रश्नों की संख्या हो, और 1≤ m ; n त्रुटियों की आलोचनात्मकता की डिग्री; यह कवरेज की डिग्री या कवर सेट की गहराई भी है। M मान जितना छोटा होगा, त्रुटि उतनी ही महत्वपूर्ण होगी। कवरेज की डिग्री निर्धारित करके, हम एक परीक्षण सूट का निर्माण करते हैं जो उन सभी त्रुटियों का पता लगाएगा जिनकी आलोचना किसी दिए गए मीटर से कम है। यदि m = n, तो सभी विकल्पों की गणना करने के लिए त्रुटियों की खोज नीचे आती है। हम जितनी कम डिग्री निर्धारित करेंगे, उतने ही कम परीक्षण मामले बनेंगे और उतनी ही कम त्रुटियां होंगी।


मैट्रिक्स के रूप में परीक्षणों के कवरिंग सेट को प्रस्तुत करना सुविधाजनक है, जहां पंक्तियाँ परीक्षण के अनुरूप हैं और कॉलम प्रश्नों के उत्तर की पसंद के अनुरूप हैं। उदाहरण के लिए, प्रश्नों की सूची A = {3, 3, 3, 3} और दाईं ओर चित्र के अनुसार ग्यारह परीक्षणों का एक सेट लें। इस तरह का एक सेट डिग्री एम = 2 को कवर करने के लिए एकदम सही है, क्योंकि जब इस सेट में किसी भी दो कॉलम को चुनते हैं, तो उनके बीच सभी प्रकार के संयोजन हल हो जाएंगे।
लाइनों की संख्या को कम करने के लिए कैसे? मेरे साथ पहली बात यह थी कि n की कवरेज की गहराई के साथ एक सेट तैयार करना था, अर्थात सभी परीक्षण मामले, और फिर उत्सुकता से इसका चयन करें जो कि अभी तक कवर नहीं किए गए m तत्वों के संयोजन की सबसे बड़ी संख्या को हटा दें। तो मैं भीड़ के कवरेज के लिए एक लालची खोज की तरह कुछ के साथ आया था। यह तय करने के बाद कि यह बहुत दिलचस्प नहीं है, और शायद व्यावहारिक नहीं है, मैंने यह रास्ता नहीं लिया है।
शायद, आप में से कई लोग पहले से ही इस कार्य से परिचित हैं, लेकिन मुझे कभी भी इस तरह की समस्या से नहीं जूझना पड़ा, और यह देखते हुए कि समय सीमा एक सप्ताह दी गई थी, मुझे गंभीरता से झुकना पड़ा। लेकिन सीखने में कभी देर नहीं लगती। तीन दिनों और तीन रातों के लिए, मैंने एक एल्गोरिथ्म के साथ आने की कोशिश की, जो सबसे अच्छे तरीके से काम करेगा या कम से कम यांडेक्स जेनी से बेहतर होगा। यह मत सोचिए कि मैंने खोज इंजनों की ओर रुख नहीं किया था, मैं बस यह भी अनुमान नहीं लगा सकता था कि Google को कौन सी क्वेरी है। बहुत पीड़ा और विभिन्न खोजों के बाद, फिर भी मैंने किसी तरह चमत्कारिक ढंग से कहीं से एक विधि को जन्म दिया जो एक नए प्रश्न को जोड़ते समय संयोजनों के क्रमिक जोड़ पर आधारित था। जाहिर है, मेरे पास अभी भी एक प्रोग्रामर मानसिकता है, क्योंकि यह मेरे पास किसी भी आनुवंशिक एल्गोरिदम, स्टोचस्टिक विधियों या इस तरह के किसी भी चीज़ का उपयोग करने के लिए नहीं हुआ, लेकिन एक गैर-तुच्छ, लेकिन फिर भी लालची एल्गोरिथ्म दिखाई दिया।
जब कुछ दिन बाद मुझे पता चला कि मैं जिस विचार के साथ आया था और एक आधार के रूप में लिया गया था, और इसी तरह के कार्यों का क्रम पहले से मौजूद है, तो मुझे आश्चर्य हुआ कि पैरामीटर ऑर्डर एल्गोरिथ्म में इसी को कहा जाता है, दूसरे शब्दों में, एक नया पैरामीटर जोड़ने पर आधारित एल्गोरिथ्म । इसके अलावा, कुछ अच्छे लेख और यहां तक ​​कि एक पूरी पुस्तक है, जिसे "कवर सेट के निर्माण के तरीकों का अवलोकन" कहा जाता है, जो इस तरह की समस्याओं पर विचार करते हैं।

यहाँ सबसे प्रसिद्ध रणनीतियों को वर्गीकृत करने का तरीका बताया गया है:

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

पहला कदम।

शुरू करने के लिए, हम पहले मी प्रश्न लेते हैं और उनके बीच सभी संयोजनों को हल करते हैं। आउटपुट m कॉलम का एक मैट्रिक्स होगा और A (1) * A (2) * ... A (m) के बराबर पंक्तियों की संख्या होगी। चूंकि, किसी भी स्थिति में, इन एम कॉलम के बीच सभी संयोजनों को क्रमबद्ध किया जाना चाहिए, इसलिए हमें छोटी संख्या में पंक्तियां नहीं मिल सकती हैं। इस संबंध में, सर्वोत्तम परिणाम के लिए, आपको बस अवरोही क्रम में विकल्पों की संख्या के आधार पर प्रश्नों को क्रमबद्ध करना होगा। क्यों? यह भविष्य में स्पष्ट हो जाएगा।

चरण दो क्षैतिज विकास

आज्ञा देना क्रमांक + संख्या - m - 1. अर्थात्, मूल k = m है। अब हमारे पास पहले k कॉलम के लिए गहराई m का कवरेज है। निम्न कॉलम k + 1 को इस प्रकार जोड़ें:

1. एक सेट बी बनाएं - कॉलम k + 1 और कॉलम 1, ..., k के बीच सभी अप्रयुक्त संयोजनों का सेट। इस सेट के भीतर संयोजन को उन कॉलमों द्वारा वर्गीकृत किया जाना चाहिए, जिनसे वे मेल खाते हैं। हम पहली पंक्ति पर विचार करते हैं।
2. प्रश्न में पंक्ति में कॉलम k + 1 में कौन सा तत्व जोड़ा जाना चाहिए? जैसा कि मैंने पहले ही कहा था, मेरा एल्गोरिथ्म लालची है, और इसलिए हम एक जोड़ते हैं जो सेट बी से कई संयोजनों को यथासंभव हटा देगा। हम ऐसा करते हैं: हम पहले उत्तर को लाइन में प्रतिस्थापित करते हैं और यह पता लगाते हैं कि इस तरह की लाइन के साथ B के कितने संयोजनों को हटाया जा सकता है। यदि उनकी संख्या k है, तो विकल्प उपयुक्त है, यदि कम है - अगले पर जाएं। वह विकल्प जो बी से हटाए गए संयोजनों की सबसे बड़ी संख्या देगा और चुनें। मैं अपने दम पर जोड़ूंगा कि यदि कई विकल्प इष्टतम होने का दिखावा करते हैं, तो एक को वरीयता देना चाहिए जो उन स्तंभों के साथ संयोजन को पार कर जाएगा जिनके साथ संयोजन की संख्या अभी तक कवर नहीं की गई है, जो सबसे बड़ा है। फिर अगली लाइनों पर अधिक संयोजनों को पार करने की संभावना बढ़ जाएगी।
3. हम बी से कवर संयोजनों को हटाते हैं और दूसरे बिंदु पर जाते हैं, जहां हम अगली पंक्ति पर विचार करते हैं। यदि अधिक लाइनें नहीं हैं, तो बाहर निकलें।

अब, यदि सभी संयोजनों को कवर किया जाता है, तो हम फिर से दूसरे चरण में जाते हैं, एक नए क्षैतिज विकास के लिए, अर्थात हम एक नया प्रश्न / स्तंभ जोड़ते हैं। यदि प्रश्नों की संख्या समाप्त हो गई है, तो एल्गोरिथ्म समाप्त हो जाता है।

स्थिति ए = {2, 2, 2}, एम = 2 के लिए एल्गोरिथ्म का एक उदाहरण।

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

चरण तीन कार्यक्षेत्र वृद्धि

यदि आप अवरोही क्रम में विकल्पों की संख्या से स्तंभों को क्रमबद्ध करते हैं, तो क्षैतिज वृद्धि में लालच वास्तव में उत्कृष्ट परिणाम देता है। यदि आप क्रमशः अन्य विकल्पों के साथ कम संयोजनों के साथ कम विकल्पों के साथ एक कॉलम जोड़ते हैं, तो अधिक संभावना यह है कि क्षैतिज संयोजन में इन संयोजनों को कवर किया जाए और ऊर्ध्वाधर से बचें, या कम से कम इसे कम करें।
हम ऊर्ध्वाधर वृद्धि के साथ एक समान तरीके से काम करते हैं - हम एक पंक्ति जोड़ते हैं जो बी से सबसे अधिक संख्या में संयोजन निकालता है। यहां उनके लिए खोज करना पहले से ही अधिक कठिन है, क्योंकि एक तत्व को नहीं बदला गया है, लेकिन एक पूरी लाइन, और यह एल्गोरिथ्म का सबसे कठिन हिस्सा है। इसलिए, एक नियम के रूप में, इस भाग को जितना संभव हो उतने लाइनों से बचा जाता है और जोड़ा जाता है, लेकिन बहुपद में। स्थानीय स्तर पर सर्वोत्तम पंक्ति की खोज कितना न्यायसंगत है, यह मैं निश्चित रूप से नहीं कह सकता, लेकिन व्यवहार में परिणाम अच्छे हैं।
मैंने निम्नानुसार कार्य किया: पावर के घटते क्रम में क्रमबद्ध बी (1), बी (2), ..., बी (के) - बी के असमान उपसमूह जिसमें अनौपचारिक संयोजन संबंधित कॉलम में सूचीबद्ध हैं। स्पष्टता के लिए: यदि B = {_11, 1_1, 1_2}, तो b (1) = {1_1, 1_2}, b (2) = {_11}। यह आदेश शेष संयोजनों की सबसे बड़ी संख्या के साथ सेटों को प्राथमिकता देने के लिए किया जाता है। फिर मैंने पहला संयोजन b (1) से लिया, फिर कोई भी संयोजन जो b (2) में पिछले संयोजन का खंडन नहीं करता है, तो b (3), आदि में कोई भी उपयुक्त संयोजन। इस उदाहरण में, b (2) का _11, b (1) का 1_2 विरोधाभास करता है, लेकिन 1_1 का विरोधाभास नहीं करता है। एन्युमरेशन गहराई में खोज करने जैसा था, जब यह b (k) तक पहुंचा, B से लिए गए संयोजनों की संख्या को याद किया, b (k-1) में लौटा, एक और संयोजन लिया और फिर से b (k) के लिए। खोज का अंत क्षैतिज विकास के साथ था, या तो k संयोजनों की उपलब्धि, या संपूर्ण खोज। फिर एक समान खोज बी (2) के साथ शुरू हुई, फिर बी (3) के साथ, और इसी तरह अंत तक। इसके अलावा, यह स्पष्ट है कि यदि पहले से ही कम से कम आर संयोजनों को पार करना संभव था, तो बी (क्र) के साथ खोज शुरू करने का कोई मतलब नहीं है। मैंने परीक्षणों की सूची में शामिल संयोजनों की सबसे बड़ी संख्या के अनुरूप लाइन डाली, और नए के लिए - अगले एक की तलाश करें।
मैं इस खोज की अनुकूलता और गति का ढोंग नहीं करता, लेकिन यह केवल एक चीज थी जो मैं उस समय के साथ आया था।
एक अन्य महत्वपूर्ण संशोधन यह है कि यदि हमने b (1) ... b (k) से सभी संयोजनों को पंक्ति में नहीं जोड़ा है, अर्थात, ऐसा संयोजन, जो पिछले वाले के विपरीत नहीं था, इन सेटों में से एक में नहीं पाया गया था, तो रिक्त लाइनें आवश्यक रूप से बनाई गई हैं जगह। उदाहरण के लिए, अगर यह हमारे लिए मायने नहीं रखता है, कि क्या सम्मिलित करना है, तो 111 या 121 लाइन है, क्योंकि संयोजन _11 और _21 पहले से ही कवर किए गए हैं, तो हम कोई भी स्वीकार्य मूल्य सम्मिलित कर सकते हैं, लेकिन खाली जगह छोड़ना सबसे अच्छा है। क्यों? जब सभी संयोजनों को सही ढंग से कवर किया जाता है, तो हम दूसरे चरण पर लौटते हैं या, यदि k = n - 1, बाहर निकलें। इसलिए, अगर हमें अभी भी क्षैतिज रूप से बढ़ना है, तो हम इस रिक्त स्थान का लाभ उठा सकते हैं वहां एक मान डाल सकते हैं जो खाली स्थान वाले कॉलम के साथ किसी भी संयोजन को हटा देगा।

स्थिति ए = {3, 3, 3, 3}, एम = 2 के लिए एल्गोरिथ्म का एक उदाहरण।

पहला पुनरावृति पहले दो स्तंभों का गठन करने के लिए, तीसरा जोड़ा जाता है। फिर _23 और _31 के शेष संयोजनों को कवर करने के लिए दो लाइनें जोड़ी जाती हैं

दूसरा पुनरावृति। चौथा कॉलम जोड़ें। खाली स्थानों को यादृच्छिक संख्या से भरा जाता है।

निष्कर्ष

इस एल्गोरिथ्म को लागू करने के बाद, मैं बेहद खुश था, क्योंकि यह जेनी की तुलना में बेहतर और तेज काम कर रहा था। IPO का एकमात्र, बल्कि बड़ा, ऋण है कि अग्रिम में प्राप्त लाइनों की सटीक संख्या निर्धारित करना सैद्धांतिक रूप से अत्यंत कठिन है। यही है, यह एक दी गई गहराई से काम करता है, जिसकी गणना अधिकतम परीक्षणों के आधार पर की जानी चाहिए। अपने लेख में, मैं परीक्षण सेटों के आकार का अनुमानित अनुमान देता हूं, वर्ग में प्रश्न के लिए उत्तर विकल्पों की सबसे बड़ी संख्या के बराबर। हालांकि, यह केवल कुछ मामलों में और केवल m = 2 के लिए सही है, इसके अलावा, यह प्रश्नों की संख्या को ध्यान में नहीं रखता है, और वास्तविक आकार का बिखराव हमारे लिए इस तरह के अल्प अनुमान को सीमित करने के लिए बहुत बड़ा है। मामले में एम = 1, परीक्षणों की संख्या उत्तर विकल्पों की सबसे बड़ी संख्या के साथ मेल खाती है, उदाहरण के लिए, ए (के), और एम = एन - ए (1) * ... * ए (एन) के लिए। इसलिए, यह प्रश्न मेरे लिए खुला है।