3-ऑप्ट

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

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

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

def reverse_segment_if_better(tour, i, j, k):
    """If reversing tour[i:j] would make the tour shorter, then do it."""
    # Given tour [...A-B...C-D...E-F...]
    A, B, C, D, E, F = tour[i-1], tour[i], tour[j-1], tour[j], tour[k-1], tour[k % len(tour)]
    d0 = distance(A, B) + distance(C, D) + distance(E, F)
    d1 = distance(A, C) + distance(B, D) + distance(E, F)
    d2 = distance(A, B) + distance(C, E) + distance(D, F)
    d3 = distance(A, D) + distance(E, B) + distance(C, F)
    d4 = distance(F, B) + distance(C, D) + distance(E, A)

    if d0 > d1:
        tour[i:j] = reversed(tour[i:j])
        return -d0 + d1
    elif d0 > d2:
        tour[j:k] = reversed(tour[j:k])
        return -d0 + d2
    elif d0 > d4:
        tour[i:k] = reversed(tour[i:k])
        return -d0 + d4
    elif d0 > d3:
        tmp = tour[j:k] + tour[i:j]
        tour[i:k] = tmp
        return -d0 + d3
    return 0

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

def three_opt(tour):
    """Iterative improvement based on 3 exchange."""
    while True:
        delta = 0
        for (a, b, c) in all_segments(len(tour)):
            delta += reverse_segment_if_better(tour, a, b, c)
        if delta >= 0:
            break
    return tour

def all_segments(n: int):
    """Generate all segments combinations"""
    return ((i, j, k)
        for i in range(n)
        for j in range(i + 2, n)
        for k in range(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.