عدد پنهان فروشندهٔ دوره‌گرد در تنگنا

استفاده از هوش مصنوعی اعلام شده است. نویسندگان در بخشی با عنوان «افشای استفاده از هوش مصنوعی» اعلام می‌کنند که در آماده‌سازی مقاله از ابزار هوش مصنوعی GPT-5.6 Sol Pro استفاده کرده‌اند، همهٔ نتایج را بازبینی و تأیید کرده‌اند و مسئولیت کامل محتوای آن را می‌پذیرند. کد آن‌ها در صورت درخواست در دسترس است.

مسئلهٔ فروشندهٔ دوره‌گرد به دنبال کوتاه‌ترین گشتی است که از هر نقطهٔ یک مجموعه یک بار دیدن کند و به نقطهٔ آغاز بازگردد. حال نقاط را تصادفی کنید: n نقطه را به‌طور یکنواخت در مربعی به ضلع 1 بیندازید و بپرسید کوتاه‌ترین گشت چقدر طول دارد.

در 1959، بیردوود، هالتون و همرزلی پاسخی چشمگیر را اثبات کردند. با بزرگ شدن n، طول بهترین گشت تقریباً به‌طور حتم برابر β√n می‌شود، که در آن β ثابتی جهانی است — برای هر پاشش تصادفی یکسان. آن‌ها همچنین نشان دادند که 0.625 ≤ β ≤ 0.9212.

بیش از شصت‌وپنج سال بعد، هیچ‌کس β را نمی‌داند. هیچ فرمولی وجود ندارد. آزمایش‌های رایانه‌ای بزرگ آن را حدود 0.7124 نشان می‌دهند، اما آزمایش اثبات نیست. تا کنون بهترین کران‌های اثبات‌شده 0.6277 ≤ β ≤ 0.90367 بودند. چنین ثابت‌هایی در لجستیک اهمیت دارند، جایی که برای برآورد طول مسیرهای تحویل بدون محاسبهٔ آن‌ها به کار می‌روند — و به همین دلیل نتیجهٔ تازه از مدرسهٔ کسب‌وکار مک‌کامبز دانشگاه تگزاس در آستین، به دست ژوئولون دونگ و جون‌یو کائو، آمده است.

بازهٔ تازه

مقاله اثبات می‌کند:

0.6421 ≤ β ≤ 0.8810

و با استفاده از نمونه‌گیری تصادفی نشان می‌دهد که با احتمال دست‌کم 1 − 2 × 10⁻⁴، 0.6536 ≤ β ≤ 0.8749. این احتمال به تصادفی بودن نمونه‌گیری رایانه‌ای مربوط است، نه به خود β که عددی ثابت است.

از پایین: یال‌های بلند را ببُر

برای اثبات اینکه هر گشتی باید بلند باشد، نویسندگان بررسی می‌کنند که چه رخ می‌دهد اگر همهٔ یال‌های یک گشت را که از طولی مانند 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 هنوز به‌خوبی درون آن قرار دارد. شبکه‌های ریزتر، برآوردهای دقیق‌تر از مساحت دیسک‌های هم‌پوشان و بلوک‌های بلندتر می‌توانند آن را تنگ‌تر کنند. به نوشتهٔ نویسندگان، بستن فاصلهٔ باقی‌مانده «ممکن است به فنون تازه نیاز داشته باشد.»