3-ऑप्ट

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

3-ऑप्ट विश्लेषण में 3 उप-टूर बनाने के लिए नेटवर्क (या टूर) में 3 संयोजनों (या किनारों) को हटाना सम्मिलित है। फिर अनुकूलतम को प्राप्त करने के लिए नेटवर्क को फिर से जोड़ने के 7 अलग-अलग तरीकों का विश्लेषण किया जाता है। यह प्रक्रिया तब तक 3 संयोजनों के अलग सेट के लिए दोहराई जाती है, जब तक कि नेटवर्क में सभी संभावित संयोजनों का प्रयास नहीं किया जाता है। 3-ऑप्ट के एकल निष्पादन में समय जटिलता $O(n^{3})$ होती है। पुनरावृत्त 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

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

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

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

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

यह भी देखें

• 2-ऑप्ट
• स्थानीय खोज (अनुकूलन)
• लिन-कर्निघन अनुमानी

संदर्भ

• 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.