3-ऑप्ट: Difference between revisions

From Vigyanwiki
(Created page with "{{Expert needed |1=Mathematics| reason="This page is very poor in terms of contents. No pseudo-code, scarce references. This algorithm deserves a lot better description and tr...")
 
No edit summary
Line 1: Line 1:
{{Expert needed |1=Mathematics| reason="This page is very poor in terms of contents. No pseudo-code, scarce references. This algorithm deserves a lot better description and treatment."|date=September 2016}}
अनुकूलन में, 3-ऑप्ट [[यात्रा विक्रेता समस्या]] और संबंधित [[नेटवर्क अनुकूलन]] समस्याओं को हल करने के लिए एक सरल स्थानीय प्राप्त एल्गोरिदम है। सरल [[2-ऑप्ट]] एल्गोरिदम की तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता है।


अनुकूलन में, 3-ऑप्ट [[यात्रा विक्रेता समस्या]] और संबंधित [[नेटवर्क अनुकूलन]] समस्याओं को हल करने के लिए एक सरल स्थानीय खोज एल्गोरिदम है। सरल [[2-ऑप्ट]] एल्गोरिदम की तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता है।
3-ऑप्ट विश्लेषण में 3 उप-टूर बनाने के लिए [[ग्राफ़ (अलग गणित)|नेटवर्क]] (या टूर) में 3 संयोजनों (या किनारों) को हटाना सम्मिलित है। फिर अनुकूलतम को प्राप्त करने के लिए नेटवर्क को फिर से जोड़ने के 7 अलग-अलग तरीकों का विश्लेषण किया जाता है। यह प्रक्रिया तब तक 3 संयोजनों के अलग सेट के लिए दोहराई जाती है, जब तक कि नेटवर्क में सभी संभावित संयोजनों का प्रयास नहीं किया जाता है। 3-ऑप्ट के एकल निष्पादन में समय जटिलता <math>O(n^3)</math> होती है।<ref>{{Cite conference|title=Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem|last1=Blazinskas|first1=Andrius|last2=Misevicius|first2=Alfonsas|s2cid=15324387|date=2011|conference=17th International Conference on Information and Software Technologies |location=Kaunas, Lithuania |conference-url=https://isd.ktu.lt/it2011/ |url=https://isd.ktu.lt/it2011/material/Proceedings/1_AI_5.pdf}}</ref> पुनरावृत्त 3-ऑप्ट में समय की जटिलता अधिक होती है।


3-ऑप्ट विश्लेषण में 3 उप-टूर बनाने के लिए [[ग्राफ़ (अलग गणित)]] (या टूर) में 3 कनेक्शन (या किनारों) को हटाना शामिल है। फिर इष्टतम को खोजने के लिए नेटवर्क को फिर से जोड़ने के 7 अलग-अलग तरीकों का विश्लेषण किया जाता है। यह प्रक्रिया तब तक 3 कनेक्शनों के एक अलग सेट के लिए दोहराई जाती है, जब तक कि नेटवर्क में सभी संभावित संयोजनों का प्रयास नहीं किया जाता है। 3-ऑप्ट के एकल निष्पादन में समय की जटिलता होती है <math>O(n^3)</math>.<ref>{{Cite conference|title=Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem|last1=Blazinskas|first1=Andrius|last2=Misevicius|first2=Alfonsas|s2cid=15324387|date=2011|conference=17th International Conference on Information and Software Technologies |location=Kaunas, Lithuania |conference-url=https://isd.ktu.lt/it2011/ |url=https://isd.ktu.lt/it2011/material/Proceedings/1_AI_5.pdf}}</ref> पुनरावृत्त 3-ऑप्ट में समय की जटिलता अधिक होती है।
यह वह क्रियाविधि है जिसके द्वारा 3-ऑप्ट विनिमय किसी दिए गए मार्ग में कुशलतापूर्वक प्रयोग करता है-
 
यह वह तंत्र है जिसके द्वारा 3-ऑप्ट स्वैप किसी दिए गए मार्ग में हेरफेर करता है:<सिंटैक्सहाइलाइट lang= Python3 >
डीईएफ़ रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, आई, जे, के):
       यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
       यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
     # दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]
     # दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]
Line 31: Line 28:
     वापसी 0
     वापसी 0


</सिंटैक्सहाइलाइट>सिद्धांत बहुत सरल है। आप मूल दूरी की गणना करें <math>d_0</math> और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और वापस लौटें <math>\delta</math> (सापेक्ष लागत).
सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-
 
उपरोक्त तंत्र का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट स्वैप है:<सिंटैक्सहाइलाइट lang= Python3 >
डीईएफ़ थ्री_ऑप्ट(टूर):
       3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
       3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
     जबकि सत्य:
     जबकि सत्य:
Line 44: Line 38:
     वापसी यात्रा
     वापसी यात्रा


def all_segments(n: int):
       सभी खंड संयोजन उत्पन्न करें
       सभी खंड संयोजन उत्पन्न करें
     वापसी ((i, j, k)
     वापसी ((i, j, k)
Line 51: Line 44:
         श्रेणी में k के लिए (j + 2, n + (i > 0)))
         श्रेणी में k के लिए (j + 2, n + (i > 0)))


</सिंटैक्सहाइलाइट>दिए गए दौरे के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर दौरे को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।
दिए गए दौरे के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर दौरे को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।


==यह भी देखें==
==यह भी देखें==

Revision as of 23:09, 4 July 2023

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

3-ऑप्ट विश्लेषण में 3 उप-टूर बनाने के लिए नेटवर्क (या टूर) में 3 संयोजनों (या किनारों) को हटाना सम्मिलित है। फिर अनुकूलतम को प्राप्त करने के लिए नेटवर्क को फिर से जोड़ने के 7 अलग-अलग तरीकों का विश्लेषण किया जाता है। यह प्रक्रिया तब तक 3 संयोजनों के अलग सेट के लिए दोहराई जाती है, जब तक कि नेटवर्क में सभी संभावित संयोजनों का प्रयास नहीं किया जाता है। 3-ऑप्ट के एकल निष्पादन में समय जटिलता होती है।[1] पुनरावृत्त 3-ऑप्ट में समय की जटिलता अधिक होती है।

यह वह क्रियाविधि है जिसके द्वारा 3-ऑप्ट विनिमय किसी दिए गए मार्ग में कुशलतापूर्वक प्रयोग करता है- 

      यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
   # दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]
   ए, बी, सी, डी, ई, एफ = टूर[आई-1], टूर[आई], टूर[जे-1], टूर[जे], टूर[के-1], टूर[के % लेन(टूर) )]
   d0 = दूरी(ए, बी) + दूरी(सी, डी) + दूरी(ई, एफ)
   d1 = दूरी(ए, सी) + दूरी(बी, डी) + दूरी(ई, एफ)
   d2 = दूरी(ए, बी) + दूरी(सी, ई) + दूरी(डी, एफ)
   d3 = दूरी(ए, डी) + दूरी(ई, बी) + दूरी(सी, एफ)
   d4 = दूरी(F, B) + दूरी(C, D) + दूरी(E, A)

   यदि d0 > d1:
       टूर[i:j] = उलटा(टूर[i:j])
       वापसी -d0 + d1
   एलिफ़ d0 > d2:
       टूर[जे:के] = उलटा(टूर[जे:के])
       वापसी -d0 + d2
   एलिफ़ d0 > d4:
       टूर[i:k] = उलटा(टूर[i:k])
       वापसी -d0 + d4
   एलिफ़ d0 > d3:
       टीएमपी = टूर[जे:के] + टूर[आई:जे]
       टूर[आई:के] = टीएमपी
       वापसी -d0 + d3
   वापसी 0

सिद्धांत बहुत सरल है आप मूल दूरी की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है- 

      3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
   जबकि सत्य:
       डेल्टा = 0
       all_segments(len(tour)) में (ए, बी, सी) के लिए:
           डेल्टा += रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, ए, बी, सी)
       यदि डेल्टा >= 0:
           तोड़ना
   वापसी यात्रा

      सभी खंड संयोजन उत्पन्न करें
   वापसी ((i, j, k)
       रेंज में i के लिए(n)
       श्रेणी में j के लिए (i + 2, n)
       श्रेणी में k के लिए (j + 2, n + (i > 0)))

दिए गए दौरे के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर दौरे को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।

यह भी देखें

संदर्भ

  1. ↑ Blazinskas, Andrius; Misevicius, Alfonsas (2011). Combining 2-OPT, 3-OPT and 4-OPT with K-SWAP-KICK perturbations for the traveling salesman problem (PDF). 17th International Conference on Information and Software Technologies. Kaunas, Lithuania. S2CID 15324387.
  • BOCK, F. (1958). "An algorithm for solving traveling-salesman and related network optimization problems". Operations Research. 6 (6).
  • Lin, Shen (1965). "Computer Solutions of the Traveling Salesman Problem". Bell System Technical Journal. Institute of Electrical and Electronics Engineers (IEEE). 44 (10): 2245–2269. doi:10.1002/j.1538-7305.1965.tb04146.x. ISSN 0005-8580.
  • Lin, S.; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research. Institute for Operations Research and the Management Sciences (INFORMS). 21 (2): 498–516. doi:10.1287/opre.21.2.498. ISSN 0030-364X.
  • Sipser, Michael (2006). Introduction to the theory of computation. Boston: Thomson Course Technology. ISBN 0-534-95097-3. OCLC 58544333.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=3-ऑप्ट&oldid=209147’