2-ऑप्ट

2-ऑप्ट

ऑप्टिमाइज़ेशन (गणित) में, 2-ऑप्ट ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए एक सरल स्थानीय खोज एल्गोरिदम है।

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

स्यूडोकोड

देखने में, एक स्वैप इस प्रकार दिखता है:

 - ए बी - - ए - बी -
     × ==>
 - सी डी - - सी - डी -

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

प्रक्रिया 2optस्वैप(मार्ग, v1, v2) {
    1. रूट[0] से रूट[v1] लें और उन्हें new_route के क्रम में जोड़ें
    2. रूट[v1+1] से रूट[v2] लें और उन्हें उल्टे क्रम में new_route में जोड़ें
    3. रूट[प्रारंभ] के लिए रूट[v2+1] लें और उन्हें new_route के क्रम में जोड़ें
    नया_मार्ग लौटें;
}

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

• उदाहरण मार्ग: ए → बी → ई → डी → सी → एफ → जी → एच → ए
• उदाहरण पैरामीटर: v1=1, v2=4 (प्रारंभिक सूचकांक 0 मानते हुए)
• new_route की सामग्री चरण दर चरण:
  1. (ए → बी)
  2. ए → बी → (सी → डी → ई)
  3. ए → बी → सी → डी → ई → (एफ → जी → एच → ए)

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

जब तक कोई सुधार न हो तब तक दोहराएँ {
    best_distance = गणना कुल दूरी (मौजूदा_मार्ग)
    फिर से शुरू करें:
    (i = 0; i <= स्वैप किए जाने योग्य नोड्स की संख्या - 1; i++) के लिए {
        (j = i + 1; j <= स्वैप किए जाने योग्य नोड्स की संख्या; j++) के लिए {
            नया_रूट = 2ऑप्टस्वैप(मौजूदा_रूट, आई, जे)
            new_distance = गणना कुल दूरी (new_route)
            यदि (नई_दूरी < सर्वोत्तम_दूरी) {
                मौजूदा_मार्ग = नया_मार्ग
                best_distance = new_distance
                फिर से प्रारंभ करें
            }
        }
    }
}

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

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

   ए → बी → सी → डी → ए

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

   सी → बी → ए → डी → ए

जो वैध नहीं है (ए, डिपो से नहीं निकलता है)।

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

नया मार्ग बनाना और नये मार्ग की दूरी की गणना करना आमतौर पर बहुत महंगा काम हो सकता है $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