2-ऑप्ट - Revision history

Manidh at 06:44, 7 July 2023

2023-07-07T06:44:59Z

← Older revision		Revision as of 12:14, 7 July 2023
Line 210:		Line 210:
	*[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:Vigyan Ready]]		[[Category:Machine Translated Page]]
			[[Category:Pages with script errors]]
			[[Category:Templates Vigyan Ready]]
			[[Category:अनुमानी एल्गोरिदम]]
			[[Category:ट्रैवलिंग सेल्समैन की समस्या]]

Indicwiki: 6 revisions imported from :alpha:2-ऑप्ट

2023-07-06T12:37:29Z

6 revisions imported from alpha:2-ऑप्ट

← Older revision	Revision as of 18:07, 6 July 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-06T10:51:40Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 16:21, 6 July 2023
Line 216:		Line 216:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 25/06/2023]]		[[Category:Created On 25/06/2023]]
			[[Category:Vigyan Ready]]

alpha>Sugatha: /* यह भी देखें */

2023-07-05T06:47:51Z

यह भी देखें

← Older revision		Revision as of 12:17, 5 July 2023
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 64:		Line 64:
	साथ ही वहां वर्ग दूरी का उपयोग करने से वर्गमूल फ़ंक्शन कॉल को छोड़कर गणना को कम करने में सहायता मिलती है। चूँकि हम केवल दो दूरियों की तुलना करने की परवाह करते हैं, सटीक दूरी की नहीं, इससे चीज़ों की गति बढ़ाने में मदद मिलेगी। यह बहुत ज़्यादा नहीं है, लेकिन यह लाखों शीर्षों वाले बड़े डेटासेट के साथ सहायता करता है।		साथ ही वहां वर्ग दूरी का उपयोग करने से वर्गमूल फ़ंक्शन कॉल को छोड़कर गणना को कम करने में सहायता मिलती है। चूँकि हम केवल दो दूरियों की तुलना करने की परवाह करते हैं, सटीक दूरी की नहीं, इससे चीज़ों की गति बढ़ाने में मदद मिलेगी। यह बहुत ज़्यादा नहीं है, लेकिन यह लाखों शीर्षों वाले बड़े डेटासेट के साथ सहायता करता है।

	=== सी++ कोड ===		=== C++ कोड ===
	<syntaxhighlight lang="c++">		<syntaxhighlight lang="c++">
	#include <algorithm>		#include <algorithm>
Line 189:		Line 189:
	</syntaxhighlight>		</syntaxhighlight>
	=== दृश्य-चित्रण ===		=== दृश्य-चित्रण ===
	[[File:2-opt Swap Path Visualization.gif\|~~300x300px~~\|alt=2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन\|2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन\|left]]		[[File:2-opt Swap Path Visualization.gif\|161x161px\|alt=2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन\|2-ऑप्ट स्वैप पथ विज़ुअलाइज़ेशन\|left]]

alpha>Sweta at 05:43, 5 July 2023

2023-07-05T05:43:44Z

← Older revision		Revision as of 11:13, 5 July 2023
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 अलग-अलग किनारों को जोड़ना सम्मिलित है, इसलिए हम केवल उन किनारों की दूरियां घटा और जोड़ सकते हैं।

	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 = - dist(route[v1], route[v1+1]) - dist(route[v2], route[v2+1]) + dist(route[v1+1], route[v2+1]) + dist(route[v1], route[v2])

alpha>Sweta at 05:40, 5 July 2023

2023-07-05T05:40:54Z

Show changes

alpha>Sweta at 10:21, 4 July 2023

2023-07-04T10:21:24Z

Show changes

alpha>Indicwiki: Created page with "2-ऑप्टऑप्टिमाइज़ेशन (गणित) में, 2-ऑप्ट ट्रैवलिंग सेल्सम..."

2023-06-25T11:50:48Z

Created page with "thumb|2-ऑप्टऑप्टिमाइज़ेशन (गणित) में, 2-ऑप्ट ट्रैवलिंग सेल्सम..."

New page

[[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-ऑप्ट स्थानीय खोज स्वैपिंग तंत्र के हर संभावित वैध संयोजन की तुलना करेगी। इस तकनीक को ट्रैवलिंग सेल्समैन की समस्या के साथ-साथ कई संबंधित समस्याओं पर भी लागू किया जा सकता है। इनमें वाहन रूटिंग समस्या (वीआरपी) के साथ-साथ कैपेसिटेटेड वीआरपी भी शामिल है, जिसके लिए एल्गोरिदम में मामूली संशोधन की आवश्यकता होती है।

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

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

स्यूडोकोड में, वह तंत्र जिसके द्वारा 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 की सामग्री चरण दर चरण:
*# (ए → बी)
*# ए → बी → (सी → डी → ई)
*# ए → बी → सी → डी → ई → (एफ → जी → एच → ए)

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

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

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

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

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

नोड[0] और नोड[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])

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

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

=== सी++ कोड ===
<सिंटैक्सहाइलाइट लैंग= सी++ >
#<एल्गोरिदम>शामिल करें
#शामिल <यादृच्छिक>
#शामिल <stdio.h>
#शामिल <वेक्टर>

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

क्लास पॉइंट {
जनता:
पूर्णांक एक्स, वाई;

बिंदु(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;
}

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

=== आउटपुट ===
<syntaxhighlight lang="output">
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]
];
</syntaxhighlight>

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

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

==संदर्भ==
{{Reflist}}

* {{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.}}

==बाहरी संबंध==
*[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]
[[Category: अनुमानी एल्गोरिदम]] [[Category: ट्रैवलिंग सेल्समैन की समस्या]]

[[Category: Machine Translated Page]]
[[Category:Created On 25/06/2023]]