2-ऑप्ट

2-ऑप्ट

अनुकूलन में, ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए 2-ऑप्ट एक सरल स्थानीय खोज एल्गोरिदम है। 2-ऑप्ट एल्गोरिदम पहली बार 1958 में क्रोज़ द्वारा प्रस्तावित किया गया था, हालांकि मूल चाल का सुझाव फ्लड द्वारा पहले ही दिया जा चुका था। इसके पीछे मुख्य विचार यह है कि एक ऐसा रूट अपनाया जाए जो स्वयं को पार करे और उसे पुन: व्यवस्थित किया जाए ताकि वह स्वयं पार न हो। एक संपूर्ण 2-ऑप्ट स्थानीय खोज स्वैपिंग तंत्र के हर संभव वैध संयोजन की तुलना करेगी। यह तकनीक ट्रैवलिंग सेल्समैन की समस्या के साथ-साथ कई संबंधित समस्याओं पर भी लागू की जा सकती है। इनमें वाहन रूटिंग समस्या (वीआरपी) के साथ-साथ कैपेसिटेटेड वीआरपी भी शामिल है, जिसमें एल्गोरिदम में मामूली संशोधन की आवश्यकता होती है।

स्यूडोकोड

दृष्टिगत रूप से, एक स्वैप इस तरह दिखता है:

 - A   B -             - A - B -
     ×         ==>
 - C   D -             - C - D -

स्यूडोकोड में, वह तंत्र जिसके द्वारा 2-ऑप्ट स्वैप किसी दिए गए रूट में हेरफेर करता है, इस प्रकार है। यहां v1 और v2 किनारों के पहले शीर्ष हैं जिन्हें आप रूट से गुजरते समय स्वैप करना चाहते हैं:

procedure 2optSwap(route, v1, v2) {
    1. take route[0] to route[v1] and add them in order to new_route
    2. take route[v1+1] to route[v2] and add them in reverse order to new_route
    3. take route[v2+1] to route[start] and add them in order to new_route
    return new_route;
}

यहां यादृच्छिक माध्यम से इनपुट के साथ उपरोक्त का एक उदाहरण दिया गया है:

• उदाहरण रूट: A → B → E → D → C → F → G → H → A
• उदाहरण पैरामीटर: v1=1, v2=4 (प्रारंभिक सूचकांक 0 मानते हुए)
• नया_रूट की विषय वस्तु:

1. (A → B)
2. A → B → (C → D → E)
3. A → B → C → D → E → (F → G → H → A)

यह उपरोक्त तंत्र का उपयोग करते हुए पूर्ण 2-ऑप्ट स्वैप है:

repeat until no improvement is made {
    best_distance = calculateTotalDistance(existing_route)
    start_again:
    for (i = 0; i <= number of nodes eligible to be swapped - 1; i++) {
        for (j = i + 1; j <= number of nodes eligible to be swapped; j++) {
            new_route = 2optSwap(existing_route, i, j)
            new_distance = calculateTotalDistance(new_route)
            if (new_distance < best_distance) {
                existing_route = new_route
                best_distance = new_distance
                goto start_again
            }
        }
    }
}

ध्यान दें: यदि आप किसी विशेष नोड या डिपो पर शुरू/समाप्ति करते हैं, तो आपको इसे स्वैपिंग के लिए योग्य उम्मीदवार के रूप में खोज से हटाना होगा, क्योंकि क्रम को उत्क्रमी से एक अमान्य पथ हो जाएगा।

उदाहरण के लिए, A स्थित डिपो के साथ:

   A → B → C → D → A

नोड[0] और नोड[2] का उपयोग करके स्वैप करने से परिणाम मिलेगा

   C → B → A → D → A

जो वैध नहीं है (A डिपो नहीं छोड़ता है)।

कुशल कार्यान्वयन

नया रूट बनाना और नये रूट की दूरी की गणना करना आमतौर पर बहुत महंगा काम हो सकता है $O(n)$ कहाँ n रूट में शीर्षों की संख्या है। इसे सममित स्थिति में (जहां दो नोड्स के बीच की दूरी प्रत्येक विपरीत दिशा में समान होती है) एक प्रदर्शन करके छोड़ा जा सकता है $O(1)$ कार्यवाही। चूँकि 2-ऑप्ट ऑपरेशन में 2 किनारों को हटाना और 2 अलग-अलग किनारों को जोड़ना शामिल है, हम केवल उन किनारों की दूरी को घटा और जोड़ सकते हैं।

लंबाईडेल्टा = - जिला(रूट[v1], रूट[v1+1]) - जिला(रूट[v2], रूट[v2+1]) + जिला(रूट[v1+1], रूट[v2+1]) + जिला(रूट[v1], रूट[v2])

अगर lengthDelta नकारात्मक है इसका मतलब यह होगा कि स्वैप के बाद नई दूरी छोटी होगी। एक बार ये तो पता चल ही जाता है lengthDelta नकारात्मक है, तो हम 2-ऑप्ट स्वैप करते हैं। इससे हम बहुत सारी संगणना से बच जाते हैं।

इसके अलावा वहां वर्ग दूरी का उपयोग करने से वर्गमूल फ़ंक्शन कॉल को छोड़ कर गणना को कम करने में मदद मिलती है। चूँकि हम केवल दो दूरियों की तुलना करने की परवाह करते हैं, सटीक दूरी की नहीं, इससे चीजों को गति देने में मदद मिलेगी। यह ज़्यादा नहीं है, लेकिन यह लाखों शीर्षों वाले बड़े डेटासेट में मदद करता है

सी++ कोड

<सिंटैक्सहाइलाइट लैंग= सी++ >

1. <एल्गोरिदम>शामिल करें
2. शामिल <यादृच्छिक>
3. शामिल <stdio.h>
4. शामिल <वेक्टर>

नेमस्पेस एसटीडी का उपयोग करना;

क्लास पॉइंट {

 जनता:

पूर्णांक एक्स, वाई;

बिंदु(int x, int y) { यह->x = x; यह->y = y; } बिंदु() { यह->x = 0; यह->y = 0; }

// दो बिंदुओं के बीच की दूरी का वर्ग इनलाइन int dist2(const प्वाइंट और अन्य) const { वापसी (एक्स - अन्य.एक्स) * (एक्स - अन्य.एक्स) + (वाई - अन्य.वाई) * (वाई - अन्य.वाई); } };

// पूरे पथ की दूरी की गणना करें (बिंदुओं के बीच वर्ग दूरी) int pathLengthSq(वेक्टर<प्वाइंट> &पथ) { पूर्णांक लंबाई = 0; for (int i = 0; i < path.size(); i++) { लंबाई += पथ[i].dist2(पथ[(i + 1) % पथ.आकार()]); } वापसी की लंबाई; }

// 2-ऑप्ट स्वैप करें शून्य do2Opt(वेक्टर<प्वाइंट> &पथ, int i, int j) { रिवर्स (शुरू (पथ) + i + 1, आरंभ (पथ) + j + 1); }

// पथ प्रिंट करें। शून्य प्रिंटपाथ(स्ट्रिंग पथनाम, वेक्टर<प्वाइंट> और पथ) { प्रिंटफ( %s = [ , pathName.c_str()); for (int i = 0; i < path.size(); i++) { यदि (i % 10 == 0) { प्रिंटफ( \n ); }

यदि (i <path.size() - 1) { प्रिंटफ( [ %3d, %3d], , पथ[i].x, पथ[i].y); } अन्य { प्रिंटफ ([ %3d, %3d] , पथ[i].x, पथ[i].y); } } प्रिंटफ( \n];\n ); }

// 0 और 1000 के बीच यादृच्छिक बिंदुओं के साथ लंबाई n का एक पथ बनाएं वेक्टर<प्वाइंट> createRandomPath(int n) { वेक्टर<प्वाइंट> पथ; के लिए (int i = 0; i < n; i++) { path.push_back(प्वाइंट(रैंड() % 1000, रैंड() % 1000)); } वापसी का पथ; }

मुख्य प्रवेश बिंदु() { वेक्टर<बिंदु> पथ = createRandomPath(100); प्रिंटपाथ(पथ1, पथ);

int curLength = pathLengthSq(पथ); int n = path.size(); बूल पाया गया सुधार = सत्य; जबकि (सुधार मिला) { पाया गया सुधार = गलत; के लिए (int i = 0; i <= n - 2; i++) { के लिए (int j = i + 1; j <= n - 1; j++) { int lengthDelta = -path[i].dist2(path[(i + 1) % n]) - path[j].dist2(path[(j + 1) % n]) + path[i].dist2(path [जे]) + पथ[(i + 1) % n].dist2(पथ[(j + 1) % n]);

// यदि पथ की लंबाई कम हो गई है, तो 2-ऑप्ट स्वैप करें अगर (लंबाईडेल्टा < 0) { do2Opt(पथ, i, j); कर्ल लंबाई + = लंबाई डेल्टा; पाया गया सुधार = सत्य; } } } }

प्रिंटपाथ(पथ2, पथ); वापसी 0; }

</सिंटैक्सहाइलाइट>

आउटपुट

path1 = [
    [ 743, 933], [ 529, 262], [ 508, 700], [ 256, 752], [ 119, 256], [ 351, 711], [ 705, 843], [ 393, 108], [ 366, 330], [ 932, 169],
    [ 847, 917], [ 868, 972], [ 223, 980], [ 592, 549], [ 169, 164], [ 427, 551], [ 624, 190], [ 920, 635], [ 310, 944], [ 484, 862],
    [ 301, 363], [ 236, 710], [ 431, 876], [ 397, 929], [ 491, 675], [ 344, 190], [ 425, 134], [  30, 629], [ 126, 727], [ 334, 743],
    [ 760, 104], [ 620, 749], [ 932, 256], [ 613, 572], [ 509, 490], [ 405, 119], [  49, 695], [ 719, 327], [ 824, 497], [ 649, 596],
    [ 184, 356], [ 245,  93], [ 306,   7], [ 754, 509], [ 665, 352], [ 738, 783], [ 690, 801], [ 337, 330], [ 656, 195], [  11, 963],
    [  42, 427], [ 968, 106], [   1, 212], [ 480, 510], [ 571, 658], [ 814, 331], [ 564, 847], [ 625, 197], [ 931, 438], [ 487,  18],
    [ 187, 151], [ 179, 913], [ 750, 995], [ 913, 750], [ 134, 562], [ 547, 273], [ 830, 521], [ 557, 140], [ 726, 678], [ 597, 503],
    [ 893, 408], [ 238, 988], [  93,  85], [ 720, 188], [ 746, 211], [ 710, 387], [ 887, 209], [ 103, 668], [ 900, 473], [ 105, 674],
    [ 952, 183], [ 787, 370], [ 410, 302], [ 110, 905], [ 996, 400], [ 585, 142], [  47, 860], [ 731, 924], [ 386, 158], [ 400, 219],
    [  55, 415], [ 874, 682], [   6,  61], [ 268, 602], [ 470, 365], [ 723, 518], [ 106,  89], [ 130, 319], [ 732, 655], [ 974, 993]
];
path2 = [
    [ 743, 933], [ 750, 995], [ 847, 917], [ 868, 972], [ 974, 993], [ 913, 750], [ 920, 635], [ 874, 682], [ 726, 678], [ 732, 655],
    [ 830, 521], [ 900, 473], [ 893, 408], [ 931, 438], [ 996, 400], [ 932, 256], [ 952, 183], [ 968, 106], [ 932, 169], [ 887, 209],
    [ 760, 104], [ 746, 211], [ 720, 188], [ 656, 195], [ 625, 197], [ 624, 190], [ 585, 142], [ 557, 140], [ 487,  18], [ 306,   7],
    [ 245,  93], [ 187, 151], [ 169, 164], [ 106,  89], [  93,  85], [   6,  61], [   1, 212], [ 119, 256], [ 130, 319], [ 184, 356],
    [ 301, 363], [ 337, 330], [ 366, 330], [ 410, 302], [ 344, 190], [ 393, 108], [ 405, 119], [ 425, 134], [ 386, 158], [ 400, 219],
    [ 529, 262], [ 547, 273], [ 470, 365], [ 509, 490], [ 597, 503], [ 710, 387], [ 665, 352], [ 719, 327], [ 814, 331], [ 787, 370],
    [ 824, 497], [ 754, 509], [ 723, 518], [ 649, 596], [ 571, 658], [ 613, 572], [ 592, 549], [ 480, 510], [ 427, 551], [ 268, 602],
    [ 134, 562], [  55, 415], [  42, 427], [  30, 629], [  49, 695], [ 103, 668], [ 105, 674], [ 126, 727], [  47, 860], [  11, 963],
    [ 110, 905], [ 179, 913], [ 223, 980], [ 238, 988], [ 310, 944], [ 256, 752], [ 236, 710], [ 334, 743], [ 351, 711], [ 491, 675],
    [ 508, 700], [ 431, 876], [ 397, 929], [ 484, 862], [ 564, 847], [ 620, 749], [ 690, 801], [ 738, 783], [ 705, 843], [ 731, 924]
];

विज़ुअलाइज़ेशन

यह भी देखें

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

संदर्भ

• G. A. CROES (1958). A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
• M. M. FLOOD (1956). The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.

बाहरी संबंध

• The Traveling Salesman Problem: A Case Study in Local Optimization
• Improving Solutions: 2-opt Exchanges