⚛️ quantum physics

Tensor-Network Formulation of the Traveling Salesman Problem and Variants

تقدم هذه الورقة صياغة لشبكة الموتر لمسألة البائع المتجول ومتغيراتها تستخدم طبقات موزونة بوزن بولتزمان ومرشحات عدّ لتحديد الجولات المثلى عبر قاعدة هامشية متسلسلة، لتعمل كخوارزمية استدلالية للتطبيقات الصناعية صغيرة النطاق بدلاً من كونها بديلاً متفوقاً للمحللات الكلاسيكية المتخصصة.

المؤلفون الأصليون: Alejandro Mata Ali, Iñigo Perez Delgado, Aitor Moreno Fdez. de Leceta

نُشر 2026-05-18

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Alejandro Mata Ali, Iñigo Perez Delgado, Aitor Moreno Fdez. de Leceta

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

الصورة الكبيرة: حل لغز "البائع المتجول" باستخدام نوع جديد من الآلات الحاسبة

تخيل أنك بائع متجول. لديك خريطة بها 10 أو 20 أو حتى 100 مدينة. يتعين عليك زيارة كل مدينة بالضبط مرة واحدة والعودة إلى منزلك، لكنك تريد القيام بذلك بأقصر مسافة ممكنة لتوفير الوقود والوقت. هذه هي "مسألة البائع المتجول" (TSP) الشهيرة.

المشكلة هي أنه مع إضافة المزيد من المدن، يتفجر عدد المسارات الممكنة. الأمر يشبه محاولة العثور على المفتاح المثالي في كومة من المفاتيح التي تنمو بسرعة تجعل فحص كل مفتاح منها يستغرق وقتاً أطول من عمر الكون. لهذا السبب تعاني أجهزة الكمبيوتر مع هذه المسألة.

يقدم هذا البحث طريقة جديدة لمعالجة هذه المشكلة باستخدام شبكات التنسور (Tensor Networks). فكر في "شبكة التنسور" ليس كبرنامج كمبيوتر، بل كـ نظام ترشيح (فلترة) ضخم متعدد الطبقات.

التشبيه: مصفاة "غبار الذهب"

تخيل أن لديك كيساً ضخماً من الرمل الممزوج بغبار الذهب.

الرمل: يمثل جميع المسارات السيئة والطويلة وغير الفعالة.
الذهب: يمثل المسار المثالي والأقصر.
الهدف: تريد فصل الذهب عن الرمل دون الحاجة للنظر في كل حبة رمل بشكل فردي.

لقد بنى المؤلفون آلة (شبكة التنسور) للقيام بذلك:

الخليط الأولي (التراكب - Superposition): أولاً، تنشئ الآلة "تراكباً". تخيل أنها تنشئ سحرياً نسخة من كل المسارات الممكنة في نفس الوقت. الأمر يشبه امتلاك مليون نسخة مختلفة منك، كل نسخة تسلك مساراً مختلفاً.
التوزين (الحرارة): بعد ذلك، تطبق الآلة "درجة حرارة" (تسمى $\tau$ $τ$ ). فكر في هذا كأنه مصباح حراري.
- المسارات الطويلة وغير الفعالة (الرمل) تصبح ساخنة وتتحول إلى ضوء، ثم تتلاشى.
- المسارات القصيرة والفعالة (الذهب) تظل باردة وثقيلة.
- تستخدم الآلة الرياضيات (عوامل بولتزمان) لجعل المسارات السيئة تختفي بشكل أسرع من المسارات الجيدة.
الفلاتر (القواعد): هذا هو الجزء الأهم. لا يمكنك اختيار أي مسار عشوائي؛ فلا يمكنك زيارة نفس المدينة مرتين. بنى المؤلفون فلاتر عدّ (Counting Filters) خاصة.
- تخيل وجود حارس أمن عند كل مدينة. إذا حاول مسافر زيارة مدينة سبق له زيارتها، يقوم الحارس بإغلاق الباب في وجه ذلك المسار المحدد.
- هذه الفلاتر "متفرقة" (sparse)، مما يعني أنها فعالة جداً في حجب المسارات الخاطئة دون الحاجة إلى فحص كل الاحتمالات يدوياً.
النتيجة (الهامش - Marginal): بعد مرور كل شيء عبر الحرارة والفلاتر، تقوم الآلة بضغط كل شيء. تسأل الآلة: "إذا نظرت إلى المدينة الأولى، فما هي المدينة الأكثر احتمالاً لأن تكون جزءاً من المسار الفائز؟" تختار تلك المدينة، وتثبتها، ثم تكرر العملية للمدينة الثانية، وهكذا حتى يتم بناء المسار بالكامل.

ما فعلوه بالفعل (التجارب)

لم يدّعِ المؤلفون أن طريقتهم هي "عصا سحرية" تحل كل المشكلات فوراً، بل كانوا صادقين جداً بشأن حدودها.

الاختبارات الصغيرة: اختبروا طريقتهم على خرائط صغيرة (من 5 إلى 12 مدينة).
المعايرة (Calibration): وجدوا أن إعداد "درجة الحرارة" ( $\tau$ ) أمر بالغ الأهمية. إذا كانت منخفضة جداً، فلن تتلاشى المسارات السيئة بما يكفي. وإذا كانت عالية جداً، فسيصاب الكمبيوتر بالارتباك بسبب الأخطاء الرياضية الصغيرة. كان عليهم ضبط هذا الإعداد بعناية لكل حجم خريطة.
النتائج:
- عندما ضبطوا الإعدادات بشكل مثالي، وجدت طريقتهم المسار المثالي في حوالي 95% من المرات في هذه الخرائط الصغيرة.
- عندما قارنوها بالطرق الحاسوبية القياسية (مثل طريقة "الجشع - Greedy" أو "التلدين المحاكي - Simulated Annealing")، كانت طريقتهم أفضل غالباً في إيجاد المسار المثالي.
- ومع ذلك، اعترفوا بأنه بالنسبة للخرائط الكبيرة جداً، تظل الرياضيات ثقيلة للغاية (التعقيد الأسي)، تماماً مثل الطرق القديمة. إنها ليست معجزة "وقت حدودي" (polynomial time)؛ بل هي مجرد طريقة أخرى منظمة جداً للقيام بالعمليات الحسابية.

اختبار من الواقع: مشكلة إعادة تعيين الوظائف

لمعرفة ما إذا كان هذا يعمل خارج نطاق النظرية، طبقوا الطريقة على مشكلة صناعية حقيقية لـ ONCE (منظمة إسبانية للمكفوفين).

المشكلة: كان لديهم عمال معينون لوظائف وبعض الوظائف الشاغرة. وكان عليهم معرفة ما إذا كان نقل عامل إلى وظيفة جديدة سيجعل الفريق بأكمله أكثر إنتاجية.
التحول: هذه ليست مشكلة "تنقل" بالضبط، لكنها مشابهة: عليك تخصيص وظائف فريدة لأشخاص فريدين دون تكرار التعيين.
النتيجة: قارنوا طريقة "شبكة التنسور" الخاصة بهم بأداتين قويتين أخريين (الملدن الكمي والملدن الرقمي).
- كانت النتائج متطابقة من حيث إجمالي مكاسب الإنتاجية.
- الاختلافات الوحيدة كانت في حالات "كسر التعادل" حيث تكون الخيارات متساوية رياضياً؛ حيث تختار الآلات المختلفة بينها بشكل عشوائي.
- الاستنتاج: أثبت هذا أن طريقتهم تعمل في العالم الحقيقي ويمكن دمجها في البرمجيات الصناعية، حتى لو لم تتفوق على الأدوات المتخصصة في هذه المهمة المحددة.

الخلاية (الخلاصة)

يقدم هذا البحث مجموعة أدوات رياضية جديدة لحل ألغاز التوجيه والتعيين.

الإيجابيات: توفر طريقة واضحة ومنظمة للتعامل مع القواعد المعقدة (مثل "لا تزر نفس المدينة مرتين") ويمكنها إيجاد الحلول المثالية للمشكلات الصغيرة. إنها تشبه وجود مساعد منظم جداً يتبع القواعد ولا يمل أبداً من التحقق من القيود.
السلبيات: لا تجعل المشكلات الضخمة سهلة بشكل سحري. فالرياضيات تظل تزداد صعوبة بشكل أسي مع نمو المشكلة. كما أنها تتطلب معايرة دقيقة لتعمل بشكل جيد.
الخلاصة: إنها طريقة جديدة قوية للتفكير في هذه المشكلات وأداة صلبة لمهام صناعية محددة وصغيرة النطاق، لكنها ليست بديلاً لجميع الحلول فائقة السرعة الموجودة حالياً.

باختصار، لقد صنعوا مصفاة متطورة يمكنها تصفية المسارات السيئة وإيجاد المسار الأفضل، ولكن لا يزال يتعين عليك ضبط الإعدادات الصحيحة للحصول على الذهب.

ملخص تقني: صياغة مسألة البائع المتجول ومتغيراتها باستخدام شبكة الموتر (Tensor-Network)

تعريف المسألة
تتناول الورقة مسألة البائع المتجول (TSP) والعديد من تعميماتها، بما في ذلك مسألة البائع المتجول المعتمدة على الزمن (TDTSP)، ومسألة إعادة تعيين المهام (JRP)، والمتغيرات التي تتضمن قيود عدم التكرار، وقواعد الأسبقية، وقيود المجموعات، وأهداف الاختناق (bottleneck objectives). تُعرف مسألة البائع المتجول بأنها إيجاد أقصر مسار يزور $N$ من العقد مرة واحدة بالضبط ثم يعود إلى نقطة البداية، وهي مسألة معروفة بصعوبتها الحسابية (NP-hard). وبينما توجد خوارزميات دقيقة مثل خوارزمية هيلد-كاركب ( $O(N^2 2^N)$ وطرق التفرع والتقيد (branch-and-bound)، إلا أنها تواجه تعقيداً أسياً يحد من قدرتها على التوسع في الحالات الصناعية. وفي المقابل، تقدم الخوارزميات التقريبية (مثل الخوارزميات الجينية، والبحث المحلي) حلولاً تقريبية دون ضمانات للأمثلية. ويشير المؤلفون إلى أن الخوارزميات الكمومية الناشئة (مثل QAOA وVQE) محدودة حالياً بسبب الضجيج في الأجهزة (عصر NISQ)، مما يستدعي استكشاف تقنيات كلاسيكية تحاكي خصائص الأنظمة الكمومية.

المنهجية
تتمثل المساهمة الجوهرية في صياغة شبكة موتر (TN) تمثل الجولات المرشحة كحالات في فضاء الضرب التوتري. تعمل الطريقة من خلال ثلاث آليات رئيسية:

بناء شبكة الموتر:
- التهيئة ('+'): إنشاء تراكب منتظم لجميع تعيينات العقد الممكنة لكل خطوة زمنية.
- التحسين ('S'): تطبيق مؤثر تطور الزمن التخيلي $U = e^{-\tau C(\vec{y})}$ ، حيث $\tau$ هو عامل التخميد و $C(\vec{y})$ هو تكلفة الجولة. هذا يعمل على كبت التكوينات ذات التكلفة العالية أسياً، بشكل مشابه لإيجاد الحالة الأرضية في الأنظمة الكمومية.
- تصفية القيود ('F'): إدخال طبقات مؤثر ضرب الموتر (MPO) لفرض القيود. بالنسبة لمسألة TSP القياسية، تعمل هذه الطبقات كمصافٍ للعدّ تضمن ظهور كل عقدة مرة واحدة بالضبط. تستخدم المصافي مؤشرات ربط ثنائية لتتبع ما إذا كانت عقدة معينة قد تمت زيارتها أم لا، مما ينفذ فعلياً قيد رمز ليفي-تشيفيتا $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$ .
- الاستخراج ('+'): تقوم طبقة الأثر (trace) بجمع السعات لإنتاج الأوزان الهامشية.
الاستخراج الهامشي المتسلسل:
يتم استخراج الحل بشكل تكراري. بالنسبة لبادئة ثابتة للجولة، تحسب الخوارزمية الوزن الهامشي $Z_p(a; \tau)$ لكل عقدة مرشحة $a$ عند الموضع التالي. في حد $\tau \to \infty$ والحسابات الدقيقة، يُضمن أن العقدة التي تعظم هذا الوزن هي جزء من جولة مثلى (الخاصية 3.2). تختار الخوارزمية العقدة المعظمة، وتحدث البادئة، وتكرر العملية حتى تكتمل الجولة.
التعميمات:
يتم تكييف الإطار لمتغيرات مختلفة من TSP عن طريق تعديل طبقات الفلتر والتطور:
- DNSNN (عدد مختلف من الخطوات/العقد): تسمح المصافي بظهور العقد ما بين $N^0$ و $N^f$ من المرات.
- NMTSP (غير ماركوفية): تستخدم MPOs من رتب أعلى للتعامل مع التكاليف المعتمدة على $K$ من الخطوات السابقة.
- BTSP (الاختناق): تستبدل تطور التكلفة بطبقة تتبع أقصى تكلفة للحافة التي تمت مواجهتها.
- PTSP (مقيدة بالمجموعات): تفرض المصافي زيارة عقدة واحدة بالضبط من كل فئة.
- TSPP (الأسبقية): تعمل المشاريع المحلية على كبح العقد إذا لم تظهر أسلافها المطلوبة بعد.
- JRP (إعادة تعيين المهام): تُنمذج كمسألة تعيين خطية حيث يمكن تكرار حالة "عدم الحركة"، وتكون بعض الشواغر فريدة.
التقريب والتعقيد:
التقليص الدقيق لشبكة الموتر الكاملة هو عملية أسية، وتتدرج بمعدل $O(\hat{N}^4 2^{\hat{N}})$ لتقليص الطبقات الكثيفة. لمعالجة الحالات الأكبر، يقترح المؤلفون:
- استئصال الطبقات (Layer Ablation): تطبيق مجموعة فرعية فقط من طبقات القيود لتقليل التعقيد، والتعامل مع النتيجة كخوارزمية تقريبية.
- التقليص الموضعي المتناثر (Sparse-Local Contraction): استغلال الطبيعة الحتمية والمتناثرة لموترات الفلتر الموضعية لتقليل المعاملات متعددة الحدود (على سبيل المثال، من $O(\hat{N}^4 2^{\hat{N}})$ إلى $O(\hat{N}^3 2^{\hat{N}})$ ) دون تغيير التدرج الأسي.
- خوارزمية تقريبية بـ $\tau$ منتهية (Finite- $\tau$ Heuristic): استخدام دقة منتهية و $\tau$ منتهية لتقريب حد درجة الحرارة صفر، مع الإقرار بأن التباين العددي وحالات التحلل (degeneracies) تؤثر على جودة الحل.

المساهمات الرئيسية

الصيغة الهامشية الصريحة: اشتقاق معادلة هامشية لشبكة الموتر التي تحدد جولة صالحة مثلى عبر قاعدة هامشية متسلسلة في حد الحسابات الدقيقة ودرجة الحرارة صفر.
ترميز القيود: تعريف طبقات MPO لقيود العدّ (عدم التكرار) القابلة للتطبيق على مختلف المسائل التوليفية.
إطار التعميم: بناء معياري يكيف صياغة TN لمتغيرات TSP (مثل TDTSP وJRP وBTSP وغيرها) عن طريق تغيير طبقات موتر محددة.
التنفيذ التقريبي (Heuristic): تنفيذ يعتمد على دقة منتهية و $\tau$ منتهية يعمل كخوارزمية تقريبية مُعايرة، مع تحليل لسلوكها فيما يتعلق بالتباين العددي والتحلل.

النتائج
تركز الدراسة التجريبية على حالات اصطناعية صغيرة ( $N \in \{5, \dots, 12\}$ ) للتحقق من صحة الطريقة وسلوكها العددي بدلاً من ادعاء التفوق الحسابي على الحلول المتخصصة.

المعايرة: معلمة الزمن التخيلي $\tau$ تعتمد على الحجم. أدى مسح المعايرة ( $\tau \in \{1, \dots, 40\}$ ) إلى تحسين معدل الحل الأمثل بشكل كبير من 55.56% (عند $\tau=1$ ) إلى 95.56% في مجموعة التقييم.
مقارنة الحلول: في الحالات الصغيرة، حقق حل TN المُعاير معدل أمثلية بنسبة 95.24%، متفوقاً على NetworkX greedy (26.67%) وsimulated annealing (59.05%)، لكنه لم يصل إلى مرجع هيلد-كارب الدقيق (100%).
استئصال الطبقات: أدى إزالة طبقات القيود إلى تدهور جودة الحل، مما يؤكد ضرورة وجود مجموعة الفلتر الكاملة لتحقيق دقة عالية.
الحالة الصناعية (JRP): في إثبات مفهوم لمسألة إعادة تعيين مهام ONCE، أنتج منهج TN حلولاً بتكاليف تراكمية مطابقة لـ Azure Digital Annealer، مع الاختلاف فقط في الحالات المتعددة للحلول المثلى (degenerate cases).

الأهمية والادعاءات
يصرح المؤلفون بوضوح بالتواضع بشأن القوة الحسابية للطريقة. هم لا يدعون امتلاك ميزة حسابية عامة على الحلول الكلاسيكية المتخصصة (مثل هيلد-كارب، أو التفرع والتقيد، أو خوارزميات التعيين المحددة) بالنسبة لمسألة TSP العامة.

التمثيل الرسمي: يُقدم العمل كـ "تمثيل زمني أسي دقيق في الحسابات المثالية" و"منصة للتقريبات والامتدادات المنضبطة".
الطبيعة التقريبية: يتم وصف تنفيذ $\tau$ المنتهي بأنه "خوارزمية تقريبية معايرة ذات دقة منتهية" يعتمد سلوكها على التباين العددي والتحلل.
الفائدة: تكمن القيمة الأساسية في إطار عمل شبكة الموتر المعياري، والذي يسمح بالدمج المنهجي لمختلف القيود (الأسبقية، المجموعات، التكاليف غير الماركوفية) وتطبيق تقنيات التقريب (إزالة الطبقات، التقليص المتناثر) ضمن صياغة موحدة.
القيود: تحتفظ الطريقة بالتدريج الأسي في أسوأ الحالات. كما تم تحديد مشكلات الاستقرار العددي (مثل نقص التباين وفقدان التباين في الحالات المتعددة للحل الأمثل) والحاجة إلى معايرة تعتمد على الحجم كقيود مهمة.

باختثناء، توفر الورقة صياغة دقيقة لشبكة الموتر لمسألة البائع المتجول ومتغيراتها، مما يثبت قدرتها على استعادة الحلول المثلى في الحالات الصغيرة ودمج القيود الصناعية، مع الإقرار بأنها لا تتجاوز التعقيد الأسي الأساسي للمسألة.