الرقم الخفي للبائع المتجول، محاصَرًا

استخدام الذكاء الاصطناعي مصرَّح به. في “إفصاح عن استخدام الذكاء الاصطناعي”، يذكر المؤلفان أنهما استخدما أداة الذكاء الاصطناعي GPT-5.6 Sol Pro في إعداد الورقة، وأنهما راجعا جميع النتائج وتحققا منها، ويتحملان المسؤولية الكاملة عن محتواها. والشيفرة البرمجية متاحة عند الطلب.

تطلب مسألة البائع المتجول أقصر جولة تزور كل نقطة من مجموعة مرة واحدة وتعود إلى نقطة البداية. والآن لنجعل النقاط عشوائية: ارمِ n نقطة بتوزيع منتظم في مربع طول ضلعه 1، واسأل عن طول أقصر جولة.

في عام 1959، برهن بيردوود وهالتون وهامرسلي على إجابة لافتة. فكلما كبر n، يصبح طول أفضل جولة مساويًا بشكل شبه مؤكد لـβ√n، حيث β ثابت كوني — هو نفسه لكل نثر عشوائي. كما بيّنوا أن 0.625 ≤ β ≤ 0.9212.

وبعد أكثر من خمسة وستين عامًا، لا أحد يعرف β. فلا توجد له صيغة. وتضعه التجارب الحاسوبية الكبيرة عند نحو 0.7124، لكن التجربة ليست برهانًا. وحتى الآن، كانت أفضل الحدود المبرهنة 0.6277 ≤ β ≤ 0.90367. ولهذه الثوابت أهمية في الخدمات اللوجستية، حيث تُستخدم لتقدير طول مسارات التوصيل دون حسابها — ولهذا جاءت النتيجة الجديدة من كلية ماكومبز لإدارة الأعمال في جامعة تكساس في أوستن، على يد تشوولون دونغ وجونيو تساو.

النطاق الجديد

تبرهن الورقة على:

0.6421 ≤ β ≤ 0.8810

وباستخدام أخذ العينات العشوائي، تُبيّن أن 0.6536 ≤ β ≤ 0.8749 باحتمال لا يقل عن 1 − 2 × 10⁻⁴. ويتعلق هذا الاحتمال بعشوائية أخذ العينات الحاسوبي، لا بـβ نفسه، الذي هو عدد ثابت.

من الأسفل: اقطع الأضلاع الطويلة

لإثبات أن كل جولة لا بد أن تكون طويلة، ينظر المؤلفان فيما يحدث إذا حُذفت كل أضلاع الجولة التي يزيد طولها على طول معيّن r. تنكسر الجولة إلى قطع من المسارات، وتبقى كل قطعة داخل عنقود من النقاط التي يبعد بعضها عن بعض أقل من r. وكلما احتاج العنقود إلى مسارات أكثر لتغطيته، وجب أن تكون في الجولة أضلاع طويلة أكثر. وبجمع ذلك على كل قيم r الممكنة نحصل على طول الجولة:

ℓ(H) = ∫₀^∞ N_H(r) dr،

حيث يعدّ N_H(r) الأضلاع الأطول من r.

تعطي النقاط المعزولة ونهايات المسارات الحدّ القديم 5/8 = 0.625 — وهو بالضبط حدّ 1959. أما المكوّن الجديد فهو سلسلة من التصحيحات الناتجة عن عناقيد صغيرة من 3 و4 و5 نقاط، كل منها تكامل على المواضع الممكنة للنقاط. ولا يمكن حساب هذه التكاملات بدقة، لذا يقسّم المؤلفان مجالاتها إلى مكعبات دقيقة ويحدّان كل مكعب من الأسفل، مع تقريب كل عدد غير نسبي في الاتجاه غير المواتي كي تكون النتيجة حدًّا حقيقيًا:

β ≥ 0.625 + 0.01113528859 + 0.005040573276 + 0.001015487669 > 0.6421.

من الأعلى: تعرّج في كتل من خمس

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

والطول المتوقع للكتلة تكامل في أحد عشر بُعدًا — خمس فجوات أفقية بين النقاط وستة ارتفاعات. ويحدّه المؤلفان عدديًا على شبكة دقيقة، مرة أخرى بأعداد نسبية مقرَّبة في الاتجاه الآمن، فيحصلان على β < 0.8810.

الفجوة المتبقية

ضاق النطاق من عرض يقارب 0.28 إلى نحو 0.24، لكن القيمة التجريبية 0.7124 لا تزال تقع في داخله بعيدًا عن طرفيه. ويمكن لشبكات أدق، وتقديرات أحدّ لمساحات الأقراص المتداخلة، وكتل أطول أن تضيّقه أكثر. ويكتب المؤلفان أن سدّ المسافة المتبقية “قد يتطلب تقنيات جديدة”.