3-ऑप्ट: Difference between revisions

From Vigyanwiki
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 3: Line 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 उप-टूर बनाने के लिए [[ग्राफ़ (अलग गणित)|नेटवर्क]] (या टूर) में 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-ऑप्ट विनिमय किसी दिए गए मार्ग में कुशलतापूर्वक प्रयोग करता है-<syntaxhighlight lang="python">
      यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
def reverse_segment_if_better(tour, i, j, k):
     # दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]
    """If reversing tour[i:j] would make the tour shorter, then do it."""
     ए, बी, सी, डी, ई, एफ = टूर[आई-1], टूर[आई], टूर[जे-1], टूर[जे], टूर[के-1], टूर[के % लेन(टूर) )]
     # Given tour [...A-B...C-D...E-F...]
     d0 = दूरी(ए, बी) + दूरी(सी, डी) + दूरी(ई, एफ)
     A, B, C, D, E, F = tour[i-1], tour[i], tour[j-1], tour[j], tour[k-1], tour[k % len(tour)]
     d1 = दूरी(ए, सी) + दूरी(बी, डी) + दूरी(ई, एफ)
     d0 = distance(A, B) + distance(C, D) + distance(E, F)
     d2 = दूरी(ए, बी) + दूरी(सी, ई) + दूरी(डी, एफ)
     d1 = distance(A, C) + distance(B, D) + distance(E, F)
     d3 = दूरी(ए, डी) + दूरी(ई, बी) + दूरी(सी, एफ)
     d2 = distance(A, B) + distance(C, E) + distance(D, F)
     d4 = दूरी(F, B) + दूरी(C, D) + दूरी(E, A)
     d3 = distance(A, D) + distance(E, B) + distance(C, F)
     d4 = distance(F, B) + distance(C, D) + distance(E, A)


     यदि d0 > d1:
     if d0 > d1:
         टूर[i:j] = उलटा(टूर[i:j])
         tour[i:j] = reversed(tour[i:j])
         वापसी -d0 + d1
         return -d0 + d1
     एलिफ़ d0 > d2:
     elif d0 > d2:
         टूर[जे:के] = उलटा(टूर[जे:के])
         tour[j:k] = reversed(tour[j:k])
         वापसी -d0 + d2
         return -d0 + d2
     एलिफ़ d0 > d4:
     elif d0 > d4:
         टूर[i:k] = उलटा(टूर[i:k])
         tour[i:k] = reversed(tour[i:k])
         वापसी -d0 + d4
         return -d0 + d4
     एलिफ़ d0 > d3:
     elif d0 > d3:
         टीएमपी = टूर[जे:के] + टूर[आई:जे]
         tmp = tour[j:k] + tour[i:j]
         टूर[आई:के] = टीएमपी
         tour[i:k] = tmp
         वापसी -d0 + d3
         return -d0 + d3
     वापसी 0
     return 0
</syntaxhighlight>सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-<syntaxhighlight lang="python">
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


सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-
def all_segments(n: int):
      3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
     """Generate all segments combinations"""
    जबकि सत्य:
     return ((i, j, k)
        डेल्टा = 0
         for i in range(n)
        all_segments(len(tour)) में (ए, बी, सी) के लिए:
         for j in range(i + 2, n)
            डेल्टा += रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, ए, बी, सी)
         for k in range(j + 2, n + (i > 0)))
        यदि डेल्टा >= 0:
</syntaxhighlight>दिए गए टूर के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर टूर को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।
            तोड़ना
     वापसी यात्रा
 
      सभी खंड संयोजन उत्पन्न करें
     वापसी ((i, j, k)
         रेंज में i के लिए(n)
         श्रेणी में j के लिए (i + 2, n)
         श्रेणी में k के लिए (j + 2, n + (i > 0)))
 
दिए गए टूर के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर टूर को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।


==यह भी देखें==
==यह भी देखें==
Line 57: Line 58:
* {{cite journal | last=Lin | first=S. | last2=Kernighan | first2=B. W. | title=An Effective Heuristic Algorithm for the Traveling-Salesman Problem | journal=Operations Research | publisher=Institute for Operations Research and the Management Sciences (INFORMS) | volume=21 | issue=2 | year=1973 | issn=0030-364X | doi=10.1287/opre.21.2.498 | pages=498–516}}
* {{cite journal | last=Lin | first=S. | last2=Kernighan | first2=B. W. | title=An Effective Heuristic Algorithm for the Traveling-Salesman Problem | journal=Operations Research | publisher=Institute for Operations Research and the Management Sciences (INFORMS) | volume=21 | issue=2 | year=1973 | issn=0030-364X | doi=10.1287/opre.21.2.498 | pages=498–516}}
* {{cite book | last=Sipser | first=Michael | title=Introduction to the theory of computation | publisher=Thomson Course Technology | publication-place=Boston | date=2006 | isbn=0-534-95097-3 | oclc=58544333 | page=}}
* {{cite book | last=Sipser | first=Michael | title=Introduction to the theory of computation | publisher=Thomson Course Technology | publication-place=Boston | date=2006 | isbn=0-534-95097-3 | oclc=58544333 | page=}}
[[Category: अनुमानी एल्गोरिदम]] [[Category: ट्रैवलिंग सेल्समैन की समस्या]]


[[Category: Machine Translated Page]]
[[Category:Created On 25/06/2023]]
[[Category:Created On 25/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:अनुमानी एल्गोरिदम]]
[[Category:ट्रैवलिंग सेल्समैन की समस्या]]

Latest revision as of 13:53, 7 July 2023

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

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

सिद्धांत बहुत सरल है आप मूल दूरी की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 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)))

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

यह भी देखें

संदर्भ

  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=209421’