سفری سیلز مین کا چھپا ہوا عدد، گھیرے میں

مصنوعی ذہانت کے استعمال کا اعلان۔ “مصنوعی ذہانت کے استعمال کے انکشاف” میں مصنفین بتاتے ہیں کہ انہوں نے مقالہ تیار کرنے میں مصنوعی ذہانت کا اوزار GPT-5.6 Sol Pro استعمال کیا، کہ انہوں نے تمام نتائج کا جائزہ لیا اور ان کی تصدیق کی، اور کہ وہ اس کے مواد کی پوری ذمہ داری لیتے ہیں۔ ان کا کوڈ درخواست پر دستیاب ہے۔

سفری سیلز مین کا مسئلہ (travelling salesman problem) وہ مختصر ترین چکر پوچھتا ہے جو کسی مجموعے کے ہر نقطے سے ایک بار گزرے اور ابتدا پر واپس آ جائے۔ اب نقطوں کو بے ترتیب بنا دیں: 1 ضلع والے ایک مربع میں n نقطے یکساں طور پر پھینکیں اور پوچھیں کہ مختصر ترین چکر کتنا لمبا ہے۔

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 اب بھی اس کے بہت اندر ہے۔ زیادہ باریک جال، ایک دوسرے پر چڑھے دائروں کے رقبوں کے زیادہ درست تخمینے اور لمبے بلاک اسے مزید تنگ کر سکتے ہیں۔ مصنفین لکھتے ہیں کہ باقی فاصلہ ختم کرنے کے لیے “نئی تکنیکوں کی ضرورت پڑ سکتی ہے۔”