2-ऑप्ट: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[File:2-opt wiki.svg|thumb|2-ऑप्ट]]अनुकूलन में, [[ट्रैवलिंग सेल्समैन की समस्या]] को हल करने के लिए 2-ऑप्ट एक सरल स्थानीय खोज एल्गोरिदम है। 2-ऑप्ट एल्गोरिदम पहली बार 1958 में क्रोज़ द्वारा प्रस्तावित किया गया था,<ref>G. A. Croes,  A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.</ref> हालांकि मूल चाल का सुझाव फ्लड द्वारा पहले ही दिया जा चुका था।<ref>M. M. Flood, The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.</ref> इसके पीछे मुख्य विचार यह है कि एक ऐसा रूट अपनाया जाए जो स्वयं को पार करे और उसे पुन: व्यवस्थित किया जाए ताकि वह स्वयं पार न हो। एक संपूर्ण 2-ऑप्ट स्थानीय खोज स्वैपिंग तंत्र के हर संभव वैध संयोजन की तुलना करेगी। यह तकनीक ट्रैवलिंग सेल्समैन की समस्या के साथ-साथ कई संबंधित समस्याओं पर भी लागू की जा सकती है। इनमें वाहन रूटिंग समस्या (वीआरपी) के साथ-साथ कैपेसिटेटेड वीआरपी भी शामिल है, जिसमें एल्गोरिदम में मामूली संशोधन की आवश्यकता होती है।
[[File:2-opt wiki.svg|thumb|2-ऑप्ट]]अनुकूलन में, [[ट्रैवलिंग सेल्समैन की समस्या]] को हल करने के लिए 2-ऑप्ट एक सरल स्थानीय खोज (लोकल सर्च) एल्गोरिदम है। 2-ऑप्ट एल्गोरिदम पहली बार 1958 में क्रोज़ द्वारा प्रस्तावित किया गया था,<ref>G. A. Croes,  A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.</ref> हालांकि मूल चाल का सुझाव फ्लड द्वारा पहले ही दिया जा चुका था।<ref>M. M. Flood, The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.</ref> इसके पीछे मुख्य विचार यह है कि एक ऐसा रूट अपनाया जाए जो स्वयं को पार करे और उसे पुन: व्यवस्थित किया जाए ताकि वह स्वयं पार न हो। संपूर्ण 2-ऑप्ट स्थानीय खोज स्वैपिंग तंत्र के हर संभव वैध संयोजन की तुलना करेगी। यह तकनीक ट्रैवलिंग सेल्समैन की समस्या के साथ-साथ कई संबंधित समस्याओं पर भी लागू की जा सकती है। इनमें वाहन रूटिंग समस्या (वीआरपी) के साथ-साथ कैपेसिटेटेड वीआरपी भी सम्मिलित है, जिसमें एल्गोरिदम में साधारण संशोधन की आवश्यकता होती है।
== स्यूडोकोड ==
== स्यूडोकोड ==
दृष्टिगत रूप से, एक स्वैप इस तरह दिखता है:
दृष्टिगत रूप से, एक स्वैप इस तरह दिखता है:
Line 43: Line 43:
  }
  }


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


उदाहरण के लिए, A स्थित डिपो के साथ:
उदाहरण के लिए, A स्थित डिपो के साथ:
Line 56: Line 56:
== कुशल कार्यान्वयन ==
== कुशल कार्यान्वयन ==


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


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


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


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


=== सी++ कोड ===
=== C++ कोड ===
<सिंटैक्सहाइलाइट लैंग= सी++ >
<syntaxhighlight lang="c++">
#<एल्गोरिदम>शामिल करें
#include <algorithm>
#शामिल <यादृच्छिक>
#include <random>
#शामिल <stdio.h>
#include <stdio.h>
#शामिल <वेक्टर>
#include <vector>


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


क्लास पॉइंट {
class Point {
   जनता:
   public:
पूर्णांक एक्स, वाई;
int x, y;


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


// दो बिंदुओं के बीच की दूरी का वर्ग
// Distance between two points squared
इनलाइन int dist2(const प्वाइंट और अन्य) const {
inline int dist2(const Point &other) const {
वापसी (एक्स - अन्य.एक्स) * (एक्स - अन्य.एक्स) + (वाई - अन्य.वाई) * (वाई - अन्य.वाई);
return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
}
}
};
};


// पूरे पथ की दूरी की गणना करें (बिंदुओं के बीच वर्ग दूरी)
// Calculate the distance of the whole path (Squared Distances between points)
int pathLengthSq(वेक्टर<प्वाइंट> &पथ) {
int pathLengthSq(vector<Point> &path) {
पूर्णांक लंबाई = 0;
int length = 0;
for (int i = 0; i < path.size(); i++) {
for (int i = 0; i < path.size(); i++) {
लंबाई += पथ[i].dist2(पथ[(i + 1) % पथ.आकार()]);
length += path[i].dist2(path[(i + 1) % path.size()]);
}
}
वापसी की लंबाई;
return length;
}
}


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


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


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


// 0 और 1000 के बीच यादृच्छिक बिंदुओं के साथ लंबाई n का एक पथ बनाएं
// Create a path of length n with random points between 0 and 1000
वेक्टर<प्वाइंट> createRandomPath(int n) {
vector<Point> createRandomPath(int n) {
वेक्टर<प्वाइंट> पथ;
vector<Point> path;
के लिए (int i = 0; i < n; i++) {
for (int i = 0; i < n; i++) {
path.push_back(प्वाइंट(रैंड() % 1000, रैंड() % 1000));
path.push_back(Point(rand() % 1000, rand() % 1000));
}
}
वापसी का पथ;
return path;
}
}


मुख्य प्रवेश बिंदु() {
int main() {
वेक्टर<बिंदु> पथ = createRandomPath(100);
vector<Point> path = createRandomPath(100);
प्रिंटपाथ(पथ1, पथ);
printPath("path1", path);


int curLength = pathLengthSq(पथ);
int curLength = pathLengthSq(path);
int n = path.size();
int n = path.size();
बूल पाया गया सुधार = सत्य;
bool foundImprovement = true;
जबकि (सुधार मिला) {
while (foundImprovement) {
पाया गया सुधार = गलत;
foundImprovement = false;
के लिए (int i = 0; i <= n - 2; i++) {
for (int i = 0; i <= n - 2; i++) {
के लिए (int j = i + 1; j <= n - 1; j++) {
for (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]);
int lengthDelta = -path[i].dist2(path[(i + 1) % n]) - path[j].dist2(path[(j + 1) % n]) + path[i].dist2(path[j]) + path[(i + 1) % n].dist2(path[(j + 1) % n]);


// यदि पथ की लंबाई कम हो गई है, तो 2-ऑप्ट स्वैप करें
// If the length of the path is reduced, do a 2-opt swap
अगर (लंबाईडेल्टा < 0) {
if (lengthDelta < 0) {
do2Opt(पथ, i, j);
do2Opt(path, i, j);
कर्ल लंबाई + = लंबाई डेल्टा;
curLength += lengthDelta;
पाया गया सुधार = सत्य;
foundImprovement = true;
}
}
}
}
}
}
}
}


प्रिंटपाथ(पथ2, पथ);
printPath("path2", path);
वापसी 0;
return 0;
}
}
 
</syntaxhighlight>
</सिंटैक्सहाइलाइट>


=== आउटपुट ===
=== आउटपुट ===
Line 189: Line 188:
];
];
</syntaxhighlight>
</syntaxhighlight>
=== दृश्य-चित्रण ===
[[File:2-opt Swap Path Visualization.gif|161x161px|alt=2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन|2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन|left]]




=== विज़ुअलाइज़ेशन ===
[[File:2-opt Swap Path Visualization.gif|600px|center|alt=2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन|2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन]]


==यह भी देखें==
==यह भी देखें==
*[[3-ऑप्ट]]
*[[3-ऑप्ट]]
*[[स्थानीय खोज (अनुकूलन)]]
*[[स्थानीय खोज (अनुकूलन)|लोकल सर्च (अनुकूलन)]]
*लिन-कर्निघन अनुमानी
*लिन-कर्निघन अनुमानी


Line 204: Line 207:
* {{cite book|author = G. A. CROES | year = 1958 | title = A method for solving traveling salesman problems | publisher = Operations Res. 6 (1958), pp., 791-812.}}
* {{cite book|author = G. A. CROES | year = 1958 | title = A method for solving traveling salesman problems | publisher = Operations Res. 6 (1958), pp., 791-812.}}
* {{cite book|author = M. M. FLOOD | year = 1956 | title = The traveling-salesman problem | publisher = Operations Res. 4 (1956), pp., 61-75.}}
* {{cite book|author = M. M. FLOOD | year = 1956 | title = The traveling-salesman problem | publisher = Operations Res. 4 (1956), pp., 61-75.}}
==बाहरी संबंध==
==बाहरी संबंध==
*[https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf The Traveling Salesman Problem: A Case Study in Local Optimization]
*[https://www.cs.ubc.ca/~hutter/previous-earg/EmpAlgReadingGroup/TSP-JohMcg97.pdf The Traveling Salesman Problem: A Case Study in Local Optimization]
*[http://www-e.uni-magdeburg.de/mertens/TSP/node3.html Improving Solutions: 2-opt Exchanges]
*[http://www-e.uni-magdeburg.de/mertens/TSP/node3.html Improving Solutions: 2-opt Exchanges]
[[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 12:14, 7 July 2023

2-ऑप्ट

अनुकूलन में, ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए 2-ऑप्ट एक सरल स्थानीय खोज (लोकल सर्च) एल्गोरिदम है। 2-ऑप्ट एल्गोरिदम पहली बार 1958 में क्रोज़ द्वारा प्रस्तावित किया गया था,[1] हालांकि मूल चाल का सुझाव फ्लड द्वारा पहले ही दिया जा चुका था।[2] इसके पीछे मुख्य विचार यह है कि एक ऐसा रूट अपनाया जाए जो स्वयं को पार करे और उसे पुन: व्यवस्थित किया जाए ताकि वह स्वयं पार न हो। संपूर्ण 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 डिपो नहीं छोड़ता है)।

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

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

lengthDelta = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])

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

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

C++ कोड

#include <algorithm>
#include <random>
#include <stdio.h>
#include <vector>

using namespace std;

class Point {
  public:
	int x, y;

	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
	Point() {
		this->x = 0;
		this->y = 0;
	}

	// Distance between two points squared
	inline int dist2(const Point &other) const {
		return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y);
	}
};

// Calculate the distance of the whole path (Squared Distances between points)
int pathLengthSq(vector<Point> &path) {
	int length = 0;
	for (int i = 0; i < path.size(); i++) {
		length += path[i].dist2(path[(i + 1) % path.size()]);
	}
	return length;
}

// Perform a 2-opt swap
void do2Opt(vector<Point> &path, int i, int j) {
	reverse(begin(path) + i + 1, begin(path) + j + 1);
}

// Print the path. 
void printPath(string pathName, vector<Point> &path) {
	printf("%s = [", pathName.c_str());
	for (int i = 0; i < path.size(); i++) {
		if (i % 10 == 0) {
			printf("\n    ");
		}

		if (i < path.size() - 1) {
			printf("[ %3d, %3d], ", path[i].x, path[i].y);
		}
		else {
			printf("[ %3d, %3d]", path[i].x, path[i].y);
		}
	}
	printf("\n];\n");
}

// Create a path of length n with random points between 0 and 1000
vector<Point> createRandomPath(int n) {
	vector<Point> path;
	for (int i = 0; i < n; i++) {
		path.push_back(Point(rand() % 1000, rand() % 1000));
	}
	return path;
}

int main() {
	vector<Point> path = createRandomPath(100);
	printPath("path1", path);

	int curLength = pathLengthSq(path);
	int n = path.size();
	bool foundImprovement = true;
	while (foundImprovement) {
		foundImprovement = false;
		for (int i = 0; i <= n - 2; i++) {
			for (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[j]) + path[(i + 1) % n].dist2(path[(j + 1) % n]);

				// If the length of the path is reduced, do a 2-opt swap
				if (lengthDelta < 0) {
					do2Opt(path, i, j);
					curLength += lengthDelta;
					foundImprovement = true;
				}
			}
		}
	}

	printPath("path2", path);
	return 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]
];

दृश्य-चित्रण

2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन




यह भी देखें

संदर्भ

  1. G. A. Croes, A method for solving traveling salesman problems. Operations Res. 6 (1958), pp., 791-812.
  2. M. M. Flood, The traveling-salesman problem. Operations Res. 4 (1956), pp., 61-75.
  • 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.

बाहरी संबंध