ভ্রাম্যমাণ বিক্রেতার গোপন সংখ্যা, কোণঠাসা

এআই ব্যবহার ঘোষিত। একটি “এআই ব্যবহারের প্রকাশ”-এ লেখকেরা জানিয়েছেন যে গবেষণাপত্র প্রস্তুতে তারা এআই টুল GPT-5.6 Sol Pro ব্যবহার করেছেন, সব ফল পর্যালোচনা ও যাচাই করেছেন, এবং এর বিষয়বস্তুর পূর্ণ দায়িত্ব নিচ্ছেন। তাদের কোড অনুরোধে পাওয়া যায়।

ভ্রাম্যমাণ বিক্রেতা সমস্যা (ট্রাভেলিং সেলসম্যান প্রবলেম) এমন সবচেয়ে ছোট সফর খোঁজে, যা একটি সেটের প্রতিটি বিন্দুতে একবার যায় এবং শুরুর জায়গায় ফিরে আসে। এবার বিন্দুগুলোকে এলোমেলো করুন: বাহু ১ এমন একটি বর্গক্ষেত্রে সুষমভাবে n টি বিন্দু ছুড়ে দিন এবং জিজ্ঞেস করুন সবচেয়ে ছোট সফর কত লম্বা।

১৯৫৯ সালে বিয়ার্ডউড, হ্যালটন ও হ্যামারসলি একটি চমকপ্রদ উত্তর প্রমাণ করেন। n বাড়লে সেরা সফরের দৈর্ঘ্য প্রায় নিশ্চিতভাবে β√n-এর সমান হয়ে যায়, যেখানে β একটি সার্বজনীন ধ্রুবক — প্রতিটি এলোমেলো বিন্যাসের জন্য একই। তারা এটিও দেখান যে 0.625 ≤ β ≤ 0.9212।

পঁয়ষট্টি বছরেরও বেশি পরে, β কেউ জানে না। এর কোনো সূত্র নেই। বড় কম্পিউটার পরীক্ষা একে প্রায় ০.৭১২৪-এ রাখে, কিন্তু পরীক্ষা প্রমাণ নয়। এতদিন সেরা প্রমাণিত সীমা ছিল 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 দেয় — হুবহু ১৯৫৯ সালের সীমা। নতুন উপাদানটি হলো ৩, ৪ ও ৫টি বিন্দুর ছোট গুচ্ছ থেকে আসা সংশোধনের একটি ধারা, যার প্রতিটি বিন্দুগুলোর সম্ভাব্য অবস্থানের ওপর একটি সমাকলন। এই সমাকলনগুলো নিখুঁতভাবে হিসাব করা যায় না, তাই লেখকেরা তাদের ক্ষেত্রকে ক্ষুদ্র ঘনকে কেটে প্রতিটি ঘনকের নিম্নসীমা বের করেন, প্রতিটি অমূলদ সংখ্যাকে প্রতিকূল দিকে আসন্নীকরণ করে, যাতে ফলাফলটি একটি প্রকৃত সীমা হয়:

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

ওপর থেকে: পাঁচটির ব্লকে আঁকাবাঁকা পথ

ঊর্ধ্বসীমার জন্য কেবল একটি ভালো সফর দরকার। প্রচলিত পদ্ধতি বর্গক্ষেত্রটিকে আনুভূমিক ফালিতে কাটে এবং সেগুলো আঁকাবাঁকা পথে পেরোয়, বাঁ থেকে ডানে, তারপর ডান থেকে বাঁয়ে। নতুন মোড়: প্রতিটি ফালির ভেতরে বিন্দুগুলো নেওয়া হয় পাঁচটি করে ব্লকে, আর প্রতিটি ব্লকে যাওয়া হয় তার ২৪টি সম্ভাব্য ক্রমের সেরাটিতে।

একটি ব্লকের প্রত্যাশিত দৈর্ঘ্য একটি এগারো-মাত্রিক সমাকলন — বিন্দুগুলোর মধ্যে পাঁচটি আনুভূমিক ফাঁক ও ছয়টি উচ্চতা। লেখকেরা একটি সূক্ষ্ম গ্রিডে সংখ্যাগতভাবে এর সীমা বের করেন, আবারও মূলদ সংখ্যাকে নিরাপদ দিকে আসন্নীকরণ করে, এবং পান β < 0.8810।

যে ব্যবধান রয়ে গেল

পরিসরটি প্রায় ০.২৮ প্রস্থ থেকে সংকুচিত হয়ে প্রায় ০.২৪ হয়েছে, কিন্তু পরীক্ষালব্ধ মান ০.৭১২৪ এখনো এর বেশ ভেতরে। আরও সূক্ষ্ম গ্রিড, পরস্পরকে ছাপিয়ে যাওয়া চাকতির ক্ষেত্রফলের আরও নিখুঁত অনুমান এবং দীর্ঘতর ব্লক একে আরও আঁটসাঁট করতে পারে। লেখকেরা লিখেছেন, বাকি দূরত্ব ঘোচাতে “নতুন কৌশলের প্রয়োজন হতে পারে।”