2025-11-24T18:19:18.135266

The frequency $K_i$s for symmetrical traveling salesman problem

Wang
The frequency $K_i$s ($i\in[4,n]$) are studied for symmetrical traveling salesman problem ($TSP$) to identify the edges in optimal Hamiltonian cycle ($OHC$). A frequency $K_i$ is computed with a sort of ${{i}\choose{2}}$ optimal $i$-vertex paths with given endpoints (optimal $i$-vertex path) in a corresponding $K_i$ in $K_n$. In frequency $K_i$, the frequency of an edge is the number of the optimal $i$-vertex paths containing the edge in the corresponding $K_i$. Given an $OHC$ edge related to $K_i$, it has a frequency bigger than $\frac{1}{2}{{i}\choose{2}}$ in the corresponding frequency $K_i$, and that of an ordinary edge not in $OHC$ is smaller than $\frac{1}{2}{{i}\choose{2}}$. On average, an $OHC$ edge in $K_i$ has the expected frequency bigger than $\frac{i^2-4i+7}{2}$ whereas an ordinary edge has the expected frequency smaller than 2. Moreover, given a frequency $K_i$ containing an $OHC$ edge related to $K_n$, the frequency of the $OHC$ edge is bigger than $\frac{1}{2}{{i}\choose{2}}$ in the worst average case. It implies that the average frequency of an $OHC$ edge computed with frequency $K_i$s is bigger than $\frac{1}{2}{{i}\choose{2}}$. It also found that the probability that an $OHC$ edge is contained in optimal $i$-vertex paths keeps stable or increases according to $i\in [4, n]$. As the frequency $K_i$s are used to compute the frequency of an edge, each $OHC$ edge has its own peak frequency at $i=P_0$ where $P_0=\frac{n}{2} + 2$ for even $n$ or $\frac{n+1}{2} + 1$ for odd $n$. For ordinary edges out of $OHC$, the probability that they are contained in optimal $i$-vertex paths decreases according to $i$. Moreover, the average frequency of an ordinary edge will be smaller than $\frac{1}{2}{{i}\choose{2}}$ if $i \geq [0.3660n + 5.5849]$. Based on these findings, an algorithm is presented to find $OHC$ in $O(n^62^{0.3660n})$ time using dynamic programming.
academic

सममित ट्रैवलिंग सेल्समैन समस्या के लिए आवृत्ति KiK_is

मूल जानकारी

  • पेपर ID: 2504.19608
  • शीर्षक: सममित ट्रैवलिंग सेल्समैन समस्या के लिए आवृत्ति KiK_is
  • लेखक: Yong Wang (उत्तर चीन विद्युत विश्वविद्यालय)
  • वर्गीकरण: cs.DM math.CO math.OC
  • प्रकाशन समय: 2025 अक्टूबर 15 (arXiv v3)
  • पेपर लिंक: https://arxiv.org/abs/2504.19608v3

सारांश

यह पेपर सममित ट्रैवलिंग सेल्समैन समस्या (TSP) में आवृत्ति KiK_is (i∈[4,n]i\in[4,n]) का अध्ययन करता है ताकि इष्टतम हैमिल्टनियन सर्किट (OHC) में किनारों की पहचान की जा सके। आवृत्ति KiK_i को KnK_n में KiK_i के अंदर संबंधित (i2)\binom{i}{2} दिए गए अंतिम बिंदुओं के इष्टतम ii-शीर्ष पथों के माध्यम से गणना की जाती है। आवृत्ति KiK_i में, किनारे की आवृत्ति उस किनारे को शामिल करने वाले इष्टतम ii-शीर्ष पथों की संख्या है। अनुसंधान से पता चलता है: OHC किनारों की आवृत्ति संबंधित आवृत्ति KiK_i में 12(i2)\frac{1}{2}\binom{i}{2} से अधिक है, जबकि सामान्य किनारे इस मान से कम हैं; OHC किनारों की अपेक्षित आवृत्ति i2−4i+72\frac{i^2-4i+7}{2} से अधिक है, सामान्य किनारे 2 से कम हैं; जब i≥[0.3660n+5.5849]i \geq [0.3660n + 5.5849] हो, तो सामान्य किनारों की औसत आवृत्ति 12(i2)\frac{1}{2}\binom{i}{2} से कम है। इन निष्कर्षों के आधार पर, O(n620.3660n)O(n^62^{0.3660n}) समय जटिलता के साथ एक गतिशील प्रोग्रामिंग एल्गोरिदम प्रस्तावित किया गया है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की पृष्ठभूमि

ट्रैवलिंग सेल्समैन समस्या (TSP) संयोजक अनुकूलन के क्षेत्र में एक शास्त्रीय NP-पूर्ण समस्या है। nn शीर्षों के पूर्ण ग्राफ KnK_n को देखते हुए, लक्ष्य सभी शीर्षों को बिल्कुल एक बार देखने वाले सबसे छोटे हैमिल्टनियन सर्किट को खोजना है। सममित TSP के लिए, किनारों (u,v)(u,v) और (v,u)(v,u) की दूरी समान है।

मौजूदा विधियों की सीमाएं

  1. सटीक एल्गोरिदम की उच्च समय जटिलता: Bellman और Held-Karp की गतिशील प्रोग्रामिंग एल्गोरिदम को O(n22n)O(n^22^n) समय की आवश्यकता है
  2. अनुमानी विधियों में सैद्धांतिक गारंटी का अभाव: हालांकि LKH जैसी अनुमानी एल्गोरिदम व्यावहारिक रूप से अच्छा प्रदर्शन करती हैं, लेकिन सैद्धांतिक आधार की कमी है
  3. किनारों की संरचनात्मक विशेषताओं की पहचान करना कठिन: OHC किनारों में दूरी पर कोई उल्लेखनीय विशेषता नहीं है, जिससे सामान्य किनारों से अलग करना मुश्किल है

अनुसंधान प्रेरणा

मौजूदा अनुसंधान से पता चलता है कि आवृत्ति K4K_4s के आधार पर OHC किनारों की प्रभावी पहचान की जा सकती है, लेकिन अधिक सामान्य मामलों में आवृत्ति KiK_is (i>4i > 4) का व्यवस्थित अध्ययन नहीं है। यह पेपर निम्नलिखित का उद्देश्य रखता है:

  1. OHC किनारों और सामान्य किनारों के बीच आवृत्ति KiK_is पर सैद्धांतिक सीमाएं स्थापित करना
  2. किनारों की आवृत्ति और संभावना के परिवर्तन के नियमों का विश्लेषण करना
  3. आवृत्ति विशेषताओं के आधार पर उच्च दक्ष OHC पहचान एल्गोरिदम डिजाइन करना

मुख्य योगदान

  1. आवृत्ति निचली सीमा सिद्धांत स्थापित किया: साबित किया कि आवृत्ति KiK_i में OHC किनारों की आवृत्ति 12(i2)\frac{1}{2}\binom{i}{2} से अधिक है, सामान्य किनारे इस मान से कम हैं
  2. आवृत्ति परिवर्तन के नियमों का विश्लेषण किया: OHC किनारों की आवृत्ति ii के साथ बढ़ती है या स्थिर रहती है, सामान्य किनारों की आवृत्ति एकदिष्ट रूप से घटती है
  3. महत्वपूर्ण बिंदु निर्धारित किया: साबित किया कि जब i≥[0.3660n+5.5849]i \geq [0.3660n + 5.5849] हो, तो OHC किनारों और सामान्य किनारों को पूरी तरह से अलग किया जा सकता है
  4. उच्च दक्ष एल्गोरिदम प्रस्तावित किया: आवृत्ति विशेषताओं के आधार पर O(n620.3660n)O(n^62^{0.3660n}) समय एल्गोरिदम
  5. संभावना में कमी की शर्तें प्रदान कीं: सामान्य किनारों की पहचान के लिए संभावना में कमी का मानदंड pi+1(g)<[1−2i(i−1)]pi(g)p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g) दिया

विधि विस्तार

कार्य परिभाषा

इनपुट: nn शीर्षों का पूर्ण ग्राफ KnK_n और किनारों का दूरी फलन d(u,v)d(u,v)आउटपुट: इष्टतम हैमिल्टनियन सर्किट OHC बाधाएं: सममित TSP, अर्थात् d(u,v)=d(v,u)d(u,v) = d(v,u)

मुख्य अवधारणाएं

इष्टतम ii-शीर्ष पथ (OP^i)

KiK_i में ii शीर्षों और निश्चित अंतिम बिंदुओं को देखते हुए, इष्टतम ii-शीर्ष पथ सभी ii शीर्षों को बिल्कुल एक बार देखने वाला सबसे छोटा पथ है। प्रत्येक KiK_i में (i2)\binom{i}{2} विभिन्न अंतिम बिंदु जोड़ियों के लिए OP^i होते हैं।

आवृत्ति KiK_i

आवृत्ति KiK_i संबंधित KiK_i के समान शीर्ष और किनारे हैं, लेकिन किनारों के वजन को उस किनारे की (i2)\binom{i}{2} OP^i में दिखने की संख्या (आवृत्ति) से बदल दिया जाता है।

सैद्धांतिक ढांचा

प्रमेय 3.3 (OHC किनारे आवृत्ति निचली सीमा)

(i2)\binom{i}{2} OP^i वाले KiK_i (i≥4i \geq 4) के लिए, संबंधित आवृत्ति KiK_i में OHC किनारों की आवृत्ति 12(i2)\frac{1}{2}\binom{i}{2} से अधिक है।

प्रमाण रणनीति:

  • जब i=4i=4 हो, तो सभी संभावित आवृत्ति K4K_4 की गणना द्वारा सत्यापन
  • i>4i>4 के लिए, गणितीय आगमन का उपयोग करके, KiK_i से Ki+1K_{i+1} तक विस्तार करते समय OHC किनारे आवृत्ति की एकदिष्टता साबित करना

प्रमेय 3.4 (सामान्य किनारे आवृत्ति ऊपरी सीमा)

आवृत्ति KiK_i में सामान्य किनारों की आवृत्ति 12(i2)\frac{1}{2}\binom{i}{2} से कम है, सर्वोत्तम औसत स्थिति में अपेक्षित आवृत्ति i+22\frac{i+2}{2} से कम है।

प्रमेय 4.1 (KnK_n में OHC किनारे आवृत्ति सीमाएं)

KnK_n में OHC किनारों के लिए, उस किनारे को शामिल करने वाले किसी भी आवृत्ति KiK_i में, इसकी आवृत्ति सबसे खराब औसत स्थिति में 12(i2)\frac{1}{2}\binom{i}{2} से अधिक है।

एल्गोरिदम डिजाइन

आवृत्ति-आधारित पहचान एल्गोरिदम

  1. आवृत्ति KiK_i की गणना करें: चयनित ii मान के लिए, सभी KiK_i की आवृत्ति की गणना करें
  2. किनारों का वर्गीकरण: आवृत्ति सीमा 12(i2)\frac{1}{2}\binom{i}{2} के आधार पर किनारों को वर्गीकृत करें
  3. संभावना में कमी की पहचान: शर्त pi+1(g)<[1−2i(i−1)]pi(g)p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g) का उपयोग करके सामान्य किनारों की पहचान करें

समय जटिलता विश्लेषण

  • एकल KiK_i के OP^i की गणना के लिए O(i42i)O(i^42^i) समय की आवश्यकता है
  • i=[0.3660n+5.5849]i = [0.3660n + 5.5849] के लिए, कुल समय जटिलता O(n620.3660n)O(n^62^{0.3660n}) है

प्रायोगिक सेटअप

डेटासेट

  1. छोटे पैमाने के TSP उदाहरण: n∈[4,14]n \in [4,14] के निर्मित उदाहरण और Oliver30 के उप-ग्राफ
  2. वास्तविक TSP उदाहरण: TSPLIB में 48 उदाहरण, जिनमें शामिल हैं:
    • यूक्लिडियन TSP: att48, eil51, pr76 आदि
    • ATT TSP: att532 आदि
    • GEO TSP: कई भौगोलिक दूरी उदाहरण
    • मैट्रिक्स TSP: si535, si1032 आदि

मूल्यांकन मेट्रिक्स

  • आवृत्ति सटीकता: OHC किनारों और सामान्य किनारों का आवृत्ति वितरण
  • अलगाव प्रभाव: आवृत्ति सीमा का उपयोग करके सही ढंग से वर्गीकृत किनारों का अनुपात
  • एल्गोरिदम दक्षता: गणना समय और स्थान जटिलता

कार्यान्वयन विवरण

  • OP^i की गणना के लिए गतिशील प्रोग्रामिंग का उपयोग
  • बड़े पैमाने के उदाहरणों के लिए, औसत आवृत्ति की गणना के लिए 1000 KiK_i का यादृच्छिक नमूना
  • C++ कार्यान्वयन, 2.3GHz CPU, 4GB मेमोरी वाले लैपटॉप पर चलाया गया

प्रायोगिक परिणाम

आवृत्ति सीमा सत्यापन

छोटे पैमाने के उदाहरण परिणाम

n∈[4,14]n \in [4,14] के उदाहरणों के लिए:

  • OHC किनारे आवृत्ति: न्यूनतम आवृत्ति हमेशा 718(i2)\frac{7}{18}\binom{i}{2} से अधिक है, अधिकांश मामलों में 12(i2)\frac{1}{2}\binom{i}{2} से अधिक है
  • सामान्य किनारे आवृत्ति: अधिकतम आवृत्ति 12(i2)\frac{1}{2}\binom{i}{2} से कम है, औसत आवृत्ति 2 के करीब है
  • आवृत्ति अनुपात: OHC किनारों और सामान्य किनारों का औसत आवृत्ति अनुपात 4 (n=4n=4) से बढ़कर 37.3 (n=14n=14) हो जाता है

वास्तविक TSP उदाहरण परिणाम

TSPLIB उदाहरणों के लिए:

  • पहली न्यूनतम OHC किनारे आवृत्ति अधिकांश मामलों में flb=12(i2)f_{lb} = \frac{1}{2}\binom{i}{2} से अधिक है
  • दूसरी न्यूनतम OHC किनारे आवृत्ति लगभग हमेशा flbf_{lb} से अधिक है
  • OHC किनारों की औसत आवृत्ति favg>foavg=i2−4i+72f_{avg} > f_{oavg} = \frac{i^2-4i+7}{2}

किनारों का वर्गीकरण प्रभाव

आवृत्ति सीमा के आधार पर वर्गीकरण

पहली, 5वीं, 10वीं, 15वीं, 20वीं न्यूनतम OHC किनारे आवृत्ति को सीमा के रूप में उपयोग करना:

  • पहली न्यूनतम आवृत्ति: 20%-30% सामान्य किनारों को बनाए रखता है (छोटे उदाहरण), बड़े उदाहरणों में अनुपात कम है
  • 5वीं न्यूनतम आवृत्ति: सामान्य किनारों का अनुपात 15% से नीचे (छोटे उदाहरण), 10% से नीचे (मध्यम उदाहरण) तक गिरता है
  • सीमा बढ़ने के साथ, बनाए गए सामान्य किनारों की संख्या तेजी से घटती है

संभावना में कमी की शर्त का प्रभाव

शर्त pi(g)−pi+1(g)>2pi(g)i(i−1)p_i(g) - p_{i+1}(g) > \frac{2p_i(g)}{i(i-1)} का उपयोग करना:

  • i=4→5i=4 \to 5 पर लगभग 90% सामान्य किनारों की पहचान करता है
  • i=5→6i=5 \to 6 पर सभी सामान्य किनारों की पहचान करता है (n≤10n \leq 10)
  • आवृत्ति सीमा विधि की तुलना में अधिक कुशल, कम गणना मात्रा

आवृत्ति परिवर्तन के नियम

OHC किनारों का आवृत्ति परिवर्तन

  • एकदिष्टता: संभावना pi(e)p_i(e) ii के साथ बढ़ती है या स्थिर रहती है
  • शिखर: आवृत्ति P0=n2+2P_0 = \frac{n}{2}+2 (सम nn) या P0=n+12+1P_0 = \frac{n+1}{2}+1 (विषम nn) पर शिखर तक पहुंचती है
  • त्रुटि सीमा: संभावना में कमी के समय pi+1(e)≥[1−2i(i−1)]pi(e)p_{i+1}(e) \geq [1-\frac{2}{i(i-1)}]p_i(e) को संतुष्ट करता है

सामान्य किनारों का आवृत्ति परिवर्तन

  • एकदिष्ट कमी: संभावना pi(g)p_i(g) ii के साथ एकदिष्ट रूप से घटती है
  • तीव्र गिरावट: कमी का परिमाण आमतौर पर 2pi(g)i(i−1)\frac{2p_i(g)}{i(i-1)} से अधिक है
  • महत्वपूर्ण बिंदु: जब i≥[0.3660n+5.5849]i \geq [0.3660n + 5.5849] हो, तो औसत आवृत्ति 12(i2)\frac{1}{2}\binom{i}{2} से कम है

संबंधित कार्य

TSP सटीक एल्गोरिदम

  • गतिशील प्रोग्रामिंग: Bellman (1962) और Held-Karp (1962) का O(n22n)O(n^22^n) एल्गोरिदम
  • शाखा और सीमा: Carpaneto आदि द्वारा बड़े पैमाने पर असममित TSP एल्गोरिदम
  • कटिंग प्लेन विधि: Applegate आदि द्वारा 85,900 शहरों के उदाहरण का समाधान

TSP अनुमानी एल्गोरिदम

  • Lin-Kernighan एल्गोरिदम: शास्त्रीय स्थानीय खोज एल्गोरिदम
  • LKH एल्गोरिदम: α\alpha-measure के आधार पर सुधारा गया संस्करण
  • छद्म-हड्डी किनारे विधि: Jäger आदि द्वारा प्रस्तावित उच्च गुणवत्ता वाले भ्रमण पथ विधि

आवृत्ति विधि

  • आवृत्ति K4K_4: Wang और Remmel (2016) द्वारा पहली बार आवृत्ति चतुर्भुज विधि प्रस्तावित
  • द्विपद वितरण मॉडल: किनारे आवृत्ति के लिए संभाव्यता मॉडल स्थापित किया
  • आवश्यक और पर्याप्त शर्तें: Wang (2019) द्वारा आवृत्ति K4K_4 के आधार पर OHC किनारों के लिए आवश्यक और पर्याप्त शर्तें दीं

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. सैद्धांतिक सीमाएं: आवृत्ति KiK_i में OHC किनारों और सामान्य किनारों के लिए कठोर सीमाएं स्थापित की गईं
  2. परिवर्तन के नियम: किनारे आवृत्ति के ii के साथ विभिन्न परिवर्तन पैटर्न का खुलासा किया
  3. एल्गोरिदम दक्षता: पारंपरिक विधियों से बेहतर समय जटिलता वाली पहचान एल्गोरिदम प्रस्तावित की गई
  4. व्यावहारिकता: विभिन्न प्रकार के TSP उदाहरणों पर विधि की प्रभावशीलता सत्यापित की गई

सीमाएं

  1. गणना जटिलता: हालांकि घातांकीय पद में सुधार हुआ है, लेकिन अति-बड़े पैमाने के उदाहरणों के लिए अभी भी कठिन है
  2. विशेष मामले: समान वजन वाले किनारों की बड़ी संख्या वाले उदाहरणों के लिए, विधि की प्रभावशीलता कम हो सकती है
  3. नमूनाकरण त्रुटि: बड़े पैमाने के उदाहरणों में यादृच्छिक नमूनाकरण त्रुटि का परिचय दे सकता है
  4. भंडारण आवश्यकताएं: बड़ी संख्या में KiK_i और OP^i को संग्रहीत करने की आवश्यकता है, स्थान जटिलता अधिक है

भविष्य की दिशाएं

  1. एल्गोरिदम अनुकूलन: समय जटिलता को और कम करना, विशेष रूप से स्थिरांक पद
  2. समानांतरकरण: आवृत्ति गणना की स्वतंत्रता का उपयोग करके समानांतर अनुकूलन
  3. अनुमानी विधि: आवृत्ति विशेषताओं के आधार पर अनुमानी एल्गोरिदम विकसित करना
  4. विस्तारित अनुप्रयोग: विधि को असममित TSP और अन्य संयोजक अनुकूलन समस्याओं तक विस्तारित करना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक कठोरता: पूर्ण गणितीय प्रमाण और सैद्धांतिक विश्लेषण प्रदान करता है
  2. व्यापक प्रयोग: छोटे पैमाने से बड़े पैमाने तक, कई प्रकार के TSP उदाहरणों को शामिल करता है
  3. विधि नवाचार: पहली बार आवृत्ति KiK_is के गुणों और अनुप्रयोगों का व्यवस्थित अध्ययन
  4. व्यावहारिक मूल्य: कार्यान्वयन योग्य एल्गोरिदम और स्पष्ट समय जटिलता सीमाएं प्रदान करता है

कमियां

  1. लेखन की लंबाई: पेपर की लंबाई अत्यधिक है, कुछ सामग्री को संक्षिप्त किया जा सकता है
  2. जटिल प्रतीक: गणितीय प्रतीक अधिक हैं, पठनीयता में सुधार की आवश्यकता है
  3. प्रयोग का पैमाना: गणना क्षमता की सीमा के कारण, अधिकतम उदाहरण आकार अपेक्षाकृत छोटा है
  4. तुलना की कमी: अन्य सटीक एल्गोरिदम के साथ प्रत्यक्ष प्रदर्शन तुलना की कमी है

प्रभाव

  1. सैद्धांतिक योगदान: TSP की संरचनात्मक गुणों के अनुसंधान के लिए नया दृष्टिकोण प्रदान करता है
  2. एल्गोरिदम मूल्य: विशिष्ट आकार सीमा में प्रभावी सटीक एल्गोरिदम प्रदान करता है
  3. विधि प्रेरणा: आवृत्ति विश्लेषण विधि अन्य संयोजक अनुकूलन समस्याओं पर लागू हो सकती है
  4. कार्यान्वयन कठिनाई: विधि अपेक्षाकृत जटिल है, व्यावहारिक अनुप्रयोग के लिए तकनीकी दक्षता की आवश्यकता है

लागू परिस्थितियां

  1. मध्यम पैमाने का TSP: विशेष रूप से n≤100n \leq 100 के सटीक समाधान की आवश्यकता के लिए उपयुक्त
  2. सैद्धांतिक अनुसंधान: TSP संरचना विश्लेषण के लिए उपकरण प्रदान करता है
  3. पूर्व-प्रसंस्करण चरण: बड़े पैमाने के TSP के किनारे फ़िल्टरिंग पूर्व-प्रसंस्करण के रूप में काम कर सकता है
  4. शिक्षण अनुसंधान: संयोजक अनुकूलन शिक्षण के लिए केस स्टडी प्रदान करता है

संदर्भ

यह पेपर 25 महत्वपूर्ण संदर्भों का हवाला देता है, जिनमें शामिल हैं:

  • Bellman (1962), Held & Karp (1962): TSP गतिशील प्रोग्रामिंग एल्गोरिदम की नींव
  • Lin & Kernighan (1973): शास्त्रीय LK अनुमानी एल्गोरिदम
  • Helsgaun (2000, 2009): LKH एल्गोरिदम श्रृंखला
  • Wang & Remmel (2016): आवृत्ति K4K_4 विधि का मूल कार्य
  • Applegate et al. (2009): बड़े पैमाने के TSP समाधान रिकॉर्ड

समग्र मूल्यांकन: यह एक सैद्धांतिक रूप से गहन और प्रायोगिक रूप से विस्तृत संयोजक अनुकूलन पेपर है, जो TSP किनारों की संरचनात्मक विशेषताओं के अनुसंधान में महत्वपूर्ण योगदान देता है। हालांकि एल्गोरिदम दक्षता और लेखन सरलता के पहलुओं में सुधार की गुंजाइश है, लेकिन इसका सैद्धांतिक मूल्य और विधि नवाचार स्वीकृति के योग्य है।