3-ऑप्ट - Revision history

Manidh at 08:23, 7 July 2023

2023-07-07T08:23:07Z

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

Indicwiki: 7 revisions imported from :alpha:3-ऑप्ट

2023-07-06T12:37:15Z

7 revisions imported from alpha:3-ऑप्ट

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

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-06T10:31:08Z

added Category:Vigyan Ready using HotCat

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

alpha>Sadafsiddiqui at 07:19, 5 July 2023

2023-07-05T07:19:11Z

← Older revision		Revision as of 12:49, 5 July 2023
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">
	def reverse_segment_if_better(tour, i, j, k):		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 reversing tour[i:j] would make the tour shorter, then do it."""~~		if d0 > d1:
	~~# Given tour [...A-B...C-D...E-F...]~~		tour[i:j] = reversed(tour[i:j])
	~~A, B, C, D, E, F = tour[i-1], tour[i], tour[j-1], tour[j], tour[k-1], tour[k % len(tour)]~~		return -d0 + d1
	~~d0 = distance(A, B) + distance(C, D) + distance(E, F)~~		elif d0 > d2:
	~~d1 = distance(A, C) + distance(B, D) + distance(E, F)~~		tour[j:k] = reversed(tour[j:k])
	~~d2 = distance(A, B) + distance(C, E) + distance(D, F)~~		return -d0 + d2
	~~d3 = distance(A, D) + distance(E, B) + distance(C, F)~~		elif d0 > d4:
	~~d4 = distance(F, B) + distance(C, D) + distance(E, A)~~		tour[i:k] = reversed(tour[i:k])
			return -d0 + d4
	if d0 > d1:		elif d0 > d3:
	tour[i:j] = reversed(tour[i:j])		tmp = tour[j:k] + tour[i:j]
	return -d0 + d1		tour[i:k] = tmp
	elif d0 > d2:		return -d0 + d3
	tour[j:k] = reversed(tour[j:k])		return 0
	return -d0 + d2		</syntaxhighlight>सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-<syntaxhighlight lang="python">
	elif d0 > d4:		def three_opt(tour):
	tour[i:k] = reversed(tour[i:k])		"""Iterative improvement based on 3 exchange."""
	return -d0 + d4		while True:
	elif d0 > d3:		delta = 0
	tmp = tour[j:k] + tour[i:j]		for (a, b, c) in all_segments(len(tour)):
	tour[i:k] = tmp		delta += reverse_segment_if_better(tour, a, b, c)
	return -d0 + d3		if delta >= 0:
	return 0		break
	सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-		return tour
	def three_opt(tour):

	~~"""Iterative improvement based on 3 exchange."""~~		def all_segments(n: int):
	~~while True:~~		"""Generate all segments combinations"""
	~~delta = 0~~		return ((i, j, k)
	~~for (a, b, c) in all_segments(len(tour)):~~		for i in range(n)
	~~delta += reverse_segment_if_better(tour, a, b, c)~~		for j in range(i + 2, n)
	~~if delta >= 0:~~		for k in range(j + 2, n + (i > 0)))
	~~break~~		</syntaxhighlight>दिए गए टूर के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर टूर को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।
	~~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)))
	दिए गए टूर के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर टूर को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।

	==यह भी देखें==		==यह भी देखें==

alpha>Sadafsiddiqui at 17:52, 4 July 2023

2023-07-04T17:52:24Z

@@ Line 4: / Line 4: @@
 यह वह क्रियाविधि है जिसके द्वारा 3-ऑप्ट विनिमय किसी दिए गए मार्ग में कुशलतापूर्वक प्रयोग करता है-
-        यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
+        def reverse_segment_if_better(tour, i, j, k):
 सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-
-एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
+      def three_opt(tour):
 दिए गए टूर के लिए, आप सभी खंड संयोजन उत्पन्न करते हैं और प्रत्येक संयोजन के लिए, आप खंडों को उलट कर टूर को बेहतर बनाने का प्रयास करते हैं। जब आपको बेहतर परिणाम मिल जाए, तो आप प्रक्रिया को पुनः आरंभ करें, अन्यथा समाप्त करें।

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

2023-07-04T17:47:33Z

यह भी देखें

← Older revision		Revision as of 23:17, 4 July 2023
Line 44:		Line 44:
	श्रेणी में k के लिए (j + 2, n + (i > 0)))		श्रेणी में k के लिए (j + 2, n + (i > 0)))

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

	==यह भी देखें==		==यह भी देखें==

alpha>Sadafsiddiqui at 17:44, 4 July 2023

2023-07-04T17:44:14Z

← Older revision		Revision as of 23:14, 4 July 2023
Line 1:		Line 1:
	अनुकूलन में, 3-ऑप्ट [[यात्रा विक्रेता समस्या]] और संबंधित [[नेटवर्क अनुकूलन]] समस्याओं को हल करने के लिए एक सरल स्थानीय प्राप्त एल्गोरिदम है। सरल [[2-ऑप्ट]] एल्गोरिदम की तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता है।		अनुकूलन में, '''3-ऑप्ट''' [[यात्रा विक्रेता समस्या]] और संबंधित [[नेटवर्क अनुकूलन]] समस्याओं को हल करने के लिए एक सरल स्थानीय प्राप्त एल्गोरिदम है। सरल [[2-ऑप्ट]] एल्गोरिदम की तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता है।

	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-ऑप्ट में समय की जटिलता अधिक होती है।

alpha>Sadafsiddiqui at 17:39, 4 July 2023

2023-07-04T17:39:21Z

← Older revision		Revision as of 23:09, 4 July 2023
Line 1:		Line 1:
	~~{{Expert needed \|1=Mathematics\| reason="This page is very poor in terms of contents. No pseudo~~-~~code~~, ~~scarce references. This algorithm deserves a lot better description and treatment."\|date=September 2016}}~~		अनुकूलन में, 3-ऑप्ट [[यात्रा विक्रेता समस्या]] और संबंधित [[नेटवर्क अनुकूलन]] समस्याओं को हल करने के लिए एक सरल स्थानीय प्राप्त एल्गोरिदम है। सरल [[2-ऑप्ट]] एल्गोरिदम की तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता है।

	~~अनुकूलन~~ में, 3-~~ऑप्ट [[यात्रा विक्रेता समस्या]] और संबंधित~~ [[नेटवर्क ~~अनुकूलन~~]] ~~समस्याओं~~ को हल करने के लिए ~~एक सरल स्थानीय खोज एल्गोरिदम~~ है। ~~सरल [[~~2-ऑप्ट~~]] एल्गोरिदम~~ की ~~तुलना में, यह धीमा है लेकिन उच्च गुणवत्ता वाले समाधान उत्पन्न कर सकता~~ है।		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-ऑप्ट ~~स्वैप~~ किसी दिए गए मार्ग में ~~हेरफेर~~ करता है~~:<सिंटैक्सहाइलाइट lang= Python3 >~~
	~~डीईएफ़ रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, आई, जे, के):~~
	यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।		यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
	# दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]		# दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]
Line 31:		Line 28:
	वापसी 0		वापसी 0

	~~</सिंटैक्सहाइलाइट>~~सिद्धांत बहुत सरल ~~है।~~ आप मूल दूरी ~~की गणना करें~~ <math>d_0</math> और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और ~~वापस लौटें~~ <math>\delta</math> (सापेक्ष लागत).		सिद्धांत बहुत सरल है आप मूल दूरी <math>d_0</math> की गणना करते हैं और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और <math>\delta</math> (सापेक्ष लागत) वापस करें। उपरोक्त क्रियाविधि का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट विनिमय है-

	उपरोक्त ~~तंत्र~~ का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट ~~स्वैप~~ है~~:<सिंटैक्सहाइलाइट lang= Python3 >~~
	~~डीईएफ़ थ्री_ऑप्ट(टूर):~~
	3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।		3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
	जबकि सत्य:		जबकि सत्य:
Line 44:		Line 38:
	वापसी यात्रा		वापसी यात्रा

	~~def all_segments(n: int):~~
	सभी खंड संयोजन उत्पन्न करें		सभी खंड संयोजन उत्पन्न करें
	वापसी ((i, j, k)		वापसी ((i, j, k)
Line 51:		Line 44:
	श्रेणी में k के लिए (j + 2, n + (i > 0)))		श्रेणी में k के लिए (j + 2, n + (i > 0)))

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

	==यह भी देखें==		==यह भी देखें==

alpha>Indicwiki: Created page with "{{Expert needed |1=Mathematics| reason="This page is very poor in terms of contents. No pseudo-code, scarce references. This algorithm deserves a lot better description and tr..."

2023-06-25T11:50:02Z

Created page with "{{Expert needed |1=Mathematics| reason="This page is very poor in terms of contents. No pseudo-code, scarce references. This algorithm deserves a lot better description and tr..."

New page

{{Expert needed |1=Mathematics| reason="This page is very poor in terms of contents. No pseudo-code, scarce references. This algorithm deserves a lot better description and treatment."|date=September 2016}}

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

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-ऑप्ट स्वैप किसी दिए गए मार्ग में हेरफेर करता है:<सिंटैक्सहाइलाइट lang= Python3 >
डीईएफ़ रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, आई, जे, के):
यदि टूर[i:j] को उलटने से दौरा छोटा हो जाएगा, तो ऐसा करें।
# दिया गया दौरा [...ए-बी...सी-डी...ई-एफ...]
ए, बी, सी, डी, ई, एफ = टूर[आई-1], टूर[आई], टूर[जे-1], टूर[जे], टूर[के-1], टूर[के % लेन(टूर) )]
d0 = दूरी(ए, बी) + दूरी(सी, डी) + दूरी(ई, एफ)
d1 = दूरी(ए, सी) + दूरी(बी, डी) + दूरी(ई, एफ)
d2 = दूरी(ए, बी) + दूरी(सी, ई) + दूरी(डी, एफ)
d3 = दूरी(ए, डी) + दूरी(ई, बी) + दूरी(सी, एफ)
d4 = दूरी(F, B) + दूरी(C, D) + दूरी(E, A)

यदि d0 > d1:
टूर[i:j] = उलटा(टूर[i:j])
वापसी -d0 + d1
एलिफ़ d0 > d2:
टूर[जे:के] = उलटा(टूर[जे:के])
वापसी -d0 + d2
एलिफ़ d0 > d4:
टूर[i:k] = उलटा(टूर[i:k])
वापसी -d0 + d4
एलिफ़ d0 > d3:
टीएमपी = टूर[जे:के] + टूर[आई:जे]
टूर[आई:के] = टीएमपी
वापसी -d0 + d3
वापसी 0

</सिंटैक्सहाइलाइट>सिद्धांत बहुत सरल है। आप मूल दूरी की गणना करें <math>d_0</math> और आप प्रत्येक संशोधन की लागत की गणना करते हैं। यदि आपको बेहतर लागत मिलती है, तो संशोधन लागू करें और वापस लौटें <math>\delta</math> (सापेक्ष लागत).

उपरोक्त तंत्र का उपयोग करते हुए यह संपूर्ण 3-ऑप्ट स्वैप है:<सिंटैक्सहाइलाइट lang= Python3 >
डीईएफ़ थ्री_ऑप्ट(टूर):
3 एक्सचेंज के आधार पर पुनरावृत्तीय सुधार।
जबकि सत्य:
डेल्टा = 0
all_segments(len(tour)) में (ए, बी, सी) के लिए:
डेल्टा += रिवर्स_सेगमेंट_आईएफ_बेहतर(टूर, ए, बी, सी)
यदि डेल्टा >= 0:
तोड़ना
वापसी यात्रा

def all_segments(n: int):
सभी खंड संयोजन उत्पन्न करें
वापसी ((i, j, k)
रेंज में i के लिए(n)
श्रेणी में j के लिए (i + 2, n)
श्रेणी में k के लिए (j + 2, n + (i > 0)))

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

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

==संदर्भ==
{{Reflist}}
* {{cite journal|first= F. |last=BOCK | year = 1958 | title = An algorithm for solving traveling-salesman and related network optimization problems |journal=Operations Research |volume= 6 |issue=6}}
* {{cite journal | last=Lin | first=Shen | title=Computer Solutions of the Traveling Salesman Problem | journal=Bell System Technical Journal | publisher=Institute of Electrical and Electronics Engineers (IEEE) | volume=44 | issue=10 | year=1965 | issn=0005-8580 | doi=10.1002/j.1538-7305.1965.tb04146.x | pages=2245–2269}}
* {{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=}}
[[Category: अनुमानी एल्गोरिदम]] [[Category: ट्रैवलिंग सेल्समैन की समस्या]]

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