3-ऑप्ट
 | This article needs attention from an expert in Mathematics. The specific problem is: "This page is very poor in terms of contents. No pseudo-code, scarce references. This algorithm deserves a lot better description and treatment.". (September 2016) |
अनुकूलन में, 3-ऑप्ट यात्रा विक्रेता समस्या और संबंधित नेटवर्क अनुकूलन समस्याओं को हल करने के लिए एक सरल स्थानीय खोज एल्गोरिदम है। सरल 2-ऑप्ट एल्गोरिदम की तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता है।
3-ऑप्ट विश्लेषण में 3 उप-टूर बनाने के लिए ग्राफ़ (अलग गणित) (या टूर) में 3 कनेक्शन (या किनारों) को हटाना शामिल है। फिर इष्टतम को खोजने के लिए नेटवर्क को फिर से जोड़ने के 7 अलग-अलग तरीकों का विश्लेषण किया जाता है। यह प्रक्रिया तब तक 3 कनेक्शनों के एक अलग सेट के लिए दोहराई जाती है, जब तक कि नेटवर्क में सभी संभावित संयोजनों का प्रयास नहीं किया जाता है। 3-ऑप्ट के एकल निष्पादन में समय की जटिलता होती है .[1] पुनरावृत्त 3-ऑप्ट में समय की जटिलता अधिक होती है।
यह वह तंत्र है जिसके द्वारा 3-ऑप्ट स्वैप किसी दिए गए मार्ग में हेरफेर करता है:<सिंटैक्सहाइलाइट lang= Python3 > डीईएफ़ रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, आई, जे, के):
यदि टूर[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-ऑप्ट स्वैप है:<सिंटैक्सहाइलाइट lang= Python3 > डीईएफ़ थ्री_ऑप्ट(टूर):
3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
जबकि सत्य:
डेल्टा = 0
all_segments(len(tour)) में (ए, बी, सी) के लिए:
डेल्टा += रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, ए, बी, सी)
यदि डेल्टा >= 0:
तोड़ना
वापसी यात्रा
def all_segments(n: int):
सभी खंड संयोजन उत्पन्न करें
वापसी ((i, j, k)
रेंज में i के लिए(n)
श्रेणी में j के लिए (i + 2, n)
श्रेणी में k के लिए (j + 2, n + (i > 0)))
</सिंटैक्सहाइलाइट>दिए गए दौरे के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर दौरे को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।
यह भी देखें
- 2-ऑप्ट
- स्थानीय खोज (अनुकूलन)
- लिन-कर्निघन अनुमानी
संदर्भ
- ↑ 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.
