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 لمسألة بائع الرحالة المتماثلة

المعلومات الأساسية

  • معرّف الورقة: 2504.19608
  • العنوان: تكرار KiK_is لمسألة بائع الرحالة المتماثلة
  • المؤلف: Yong Wang (جامعة شمال الصين للطاقة الكهربائية)
  • التصنيف: cs.DM math.CO math.OC
  • تاريخ النشر: 15 أكتوبر 2025 (arXiv v3)
  • رابط الورقة: https://arxiv.org/abs/2504.19608v3

الملخص

تدرس هذه الورقة تكرار KiK_is (i∈[4,n]i\in[4,n]) في مسألة بائع الرحالة المتماثلة (TSP) لتحديد الأضلاع في الدورة الهاميلتونية المثلى (OHC). يتم حساب التكرار KiK_i من خلال أفضل مسارات ii-رأس مع نقاط نهاية محددة في KiK_i المقابلة في KnK_n. في تكرار 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-كاملة في مجال التحسين التوافقي. بالنظر إلى رسم بياني كامل KnK_n بـ nn رأس، الهدف هو إيجاد أقصر دورة هاميلتونية تزور جميع الرؤوس مرة واحدة بالضبط. بالنسبة لـ TSP المتماثلة، تكون المسافة بين الأضلاع (u,v)(u,v) و (v,u)(v,u) متساوية.

قيود الطرق الموجودة

  1. التعقيد الزمني العالي للخوارزميات الدقيقة: مثل خوارزمية البرمجة الديناميكية لـ Bellman و Held-Karp التي تتطلب وقت O(n22n)O(n^22^n)
  2. نقص الضمانات النظرية للطرق الاستكشافية: على الرغم من أن الخوارزميات الاستكشافية مثل LKH تؤدي بشكل جيد عملياً، إلا أنها تفتقر إلى أساس نظري
  3. صعوبة تحديد الخصائص الهيكلية للأضلاع: أضلاع OHC ليس لها خصائص بارزة من حيث المسافة، مما يجعل من الصعب تمييزها عن الأضلاع العادية

دافع البحث

تشير الأبحاث الموجودة إلى أنه يمكن تحديد أضلاع OHC بشكل فعال بناءً على تكرار K4K_4s، لكن هناك نقص في الدراسة المنهجية للحالات الأكثر عمومية لتكرار KiK_is (i>4i > 4). تهدف هذه الورقة إلى:

  1. إنشاء حدود نظرية لأضلاع OHC والأضلاع العادية في تكرار KiK_is
  2. تحليل قوانين التغيير في تكرار الأضلاع واحتمالاتها مع تغير ii
  3. تصميم خوارزمية فعالة لتحديد OHC بناءً على خصائص التكرار

المساهمات الأساسية

  1. إنشاء نظرية الحد الأدنى للتكرار: إثبات أن تكرار أضلاع OHC في تكرار KiK_i أكبر من 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)

شرح الطريقة

تعريف المهمة

الإدخال: رسم بياني كامل KnK_n بـ nn رأس ودالة المسافة للأضلاع d(u,v)d(u,v)الإخراج: دورة هاميلتونية مثلى OHC القيود: TSP متماثلة، أي d(u,v)=d(v,u)d(u,v) = d(v,u)

المفاهيم الأساسية

مسار ii-رأس مثلى (OP^i)

بالنظر إلى ii رأس في KiK_i ونقاط نهاية ثابتة، مسار 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)

بالنسبة لـ KiK_i (i≥4i \geq 4) التي تحتوي على (i2)\binom{i}{2} من OP^i، يكون تكرار أضلاع OHC في تكرار KiK_i المقابل أكبر من 12(i2)\frac{1}{2}\binom{i}{2}.

فكرة الإثبات:

  • عندما i=4i=4، يتم التحقق من خلال تعداد جميع تكرارات K4K_4 الممكنة
  • بالنسبة لـ i>4i>4، يتم استخدام الاستقراء لإثبات الرتابة في تكرار أضلاع OHC عند التوسع من KiK_i إلى Ki+1K_{i+1}

النظرية 3.4 (الحد الأعلى لتكرار الأضلاع العادية)

يكون تكرار الأضلاع العادية في تكرار KiK_i أقل من 12(i2)\frac{1}{2}\binom{i}{2}، والتكرار المتوقع في أفضل حالة متوسطة أقل من i+22\frac{i+2}{2}.

النظرية 4.1 (حدود التكرار لأضلاع OHC في KnK_n)

بالنسبة لأضلاع OHC في KnK_n، يكون تكرارها في أي تكرار 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) لتحديد الأضلاع العادية

تحليل التعقيد الزمني

  • حساب OP^i لـ KiK_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 الحقيقية: 48 مثيل من TSPLIB، تشمل:
    • TSP إقليدي: att48, eil51, pr76 وغيرها
    • TSP ATT: att532 وغيرها
    • TSP جغرافي: مثيلات متعددة بمسافات جغرافية
    • TSP مصفوفة: si535, si1032 وغيرها

مؤشرات التقييم

  • دقة التكرار: توزيع التكرار لأضلاع OHC والأضلاع العادية
  • تأثير الفصل: نسبة الأضلاع التي يتم تصنيفها بشكل صحيح باستخدام عتبة التكرار
  • كفاءة الخوارزمية: وقت الحساب والتعقيد المكاني

تفاصيل التنفيذ

  • استخدام البرمجة الديناميكية لحساب OP^i
  • بالنسبة للمثيلات الكبيرة، أخذ عينات عشوائية من 1000 KiK_i لحساب متوسط التكرار
  • تنفيذ C++، يعمل على جهاز كمبيوتر محمول بمعالج 2.3GHz وذاكرة 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}

تأثير تصنيف الأضلاع

التصنيف بناءً على عتبة التكرار

استخدام تكرار أضلاع OHC الأصغر الأول والخامس والعاشر والخامس عشر والعشرين كعتبات:

  • العتبة الأولى الأصغر: الاحتفاظ بـ 20%-30% من الأضلاع العادية (المثيلات الصغيرة)، نسبة أقل في المثيلات الكبيرة
  • العتبة الخامسة الأصغر: نسبة الأضلاع العادية المحتفظ بها تنخفض إلى أقل من 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)}:

  • تحديد حوالي 90% من الأضلاع العادية عند الانتقال من i=4i=4 إلى i=5i=5
  • تحديد جميع الأضلاع العادية عند الانتقال من i=5i=5 إلى i=6i=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 الدقيقة

  • البرمجة الديناميكية: خوارزمية O(n22n)O(n^22^n) لـ Bellman (1962) و Held-Karp (1962)
  • الفرع والحد: خوارزميات Carpaneto وآخرين لـ TSP غير المتماثلة الكبيرة
  • طريقة المستويات القاطعة: حل Applegate وآخرين لمثيل بـ 85,900 مدينة

خوارزميات TSP الاستكشافية

  • خوارزمية Lin-Kernighan: خوارزمية البحث المحلي الكلاسيكية
  • خوارزمية LKH: نسخة محسّنة بناءً على α\alpha-measure
  • طريقة الأضلاع الشبه عظمية: طريقة Jäger وآخرين للمسارات الجولة عالية الجودة

طرق التكرار

  • تكرار K4K_4: طريقة Wang و Remmel (2016) الأولى بناءً على رباعيات التكرار
  • نموذج التوزيع ذي الحدين: إنشاء نموذج احتمالي لتكرار الأضلاع
  • الشروط الضرورية والكافية: شروط Wang (2019) بناءً على تكرار K4K_4

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. الحدود النظرية: إنشاء حدود صارمة لأضلاع OHC والأضلاع العادية في تكرار KiK_i
  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. على الرغم من أن هناك مجالاً للتحسين من حيث كفاءة الخوارزمية وبساطة الكتابة، إلا أن قيمتها النظرية وابتكار طريقتها يستحقان الاعتراف.