کمپیوٹنگ تے مصنوعی ذہانتپری پرنٹنظریہپڑھن لئی ۳ منٹ

کمپیوٹر سائنس وچ 1962 دی اک رکاوٹ ڈگ پئی

ہیملٹونی چکر (Hamiltonian cycle) کسے جال وچ اک گول سفر اے جیہڑا ہر بندو تے بالکل اک واری جاندا اے تے شروع والی تھاں مڑ آندا اے۔ اک سمت والے (directed) جال وچ، ہر جوڑ اک تیر اے جیہدے مگر صرف اک پاسے چلیا جا سکدا اے، اک پاسی گلی وانگ۔ ایس مسئلے دی وزن والی شکل غیر متناسب گھمن والے سوداگر دا مسئلہ (asymmetric travelling salesman problem) اے۔

ایہہ فیصلہ کرنا کہ اجیہا چکر ہے یا نہیں، نصابی کتاباں دا اک اوکھا مسئلہ اے۔ 1962 وچ، رچرڈ بیلمین تے، وکھرے طور تے، مائیکل ہیلڈ تے رچرڈ کارپ نے ڈائنامک پروگرامنگ الگورتھم دتے جیہڑے n بندواں والے جال لئی ایہنوں لگ بھگ 2ⁿ ویلے وچ حل کردے نیں (اوہناں عاملاں توں سوا جیہڑے صرف کثیر رکنی طور تے ودھدے نیں)۔ سٹھ ورھیاں توں ودھ، کوئی وی عام سمت والے جالاں اُتے بنیادی طور تے ایہدے توں چنگا نہ کر سکیا۔

بنا سمت والا چچیرا پہلاں ای ڈگ چکیا سی

دو پاسی جوڑاں والے جالاں لئی، آندریاس بیورکلنڈ نے 2014 وچ 1.657ⁿ وچ چلن والے اک بے ترتیب الگورتھم نال رکاوٹ توڑی، اک اجیہا کم جیہنے مقالے موجب اوہنوں 2016 دا EATCS–IPEC نیروڈ انعام دوایا۔ عام بنا سمت والے جالاں لئی ایہہ اجے وی سب توں تیز جاݨیا پچھاݨیا طریقہ اے۔ سمت والیاں لئی، ترقی صرف خاص حالتاں وچ آئی — دو حصیاں والے (bipartite) جال، ہر بندو تے تھوڑے جوڑاں والے جال — یا اک اݨ ثابت مفروضے، سٹراسن دے اسیمپٹوٹک رینک قیاس، ہیٹھ۔

نویں حد

ٹوکیو یونیورسٹی دے توموہیرو کوآنا (Tomohiro Koana) تے ٹوکیو دی کمپنی CyberAgent دے سوہ کومابے (Soh Kumabe) ہن اک بے ترتیب الگورتھم دیندے نیں جیہڑا سمت والے مسئلے دا فیصلہ ایس ویلے وچ کردا اے:

O((375/196)ⁿ) = O(1.9133ⁿ)**۔

عام سمت والے جالاں لئی، 1962 توں ایہہ قوت نمائی فنکشن دے بیس وچ پہلا سدھار اے۔

طاق تے جفت وچ گنتی

اوکھ باریک اے۔ چکراں نوں ماڈیولو 2 گننا — صرف ایہہ جاننا کہ اوہناں دی گنتی طاق اے یا جفت — 2ⁿ توں تھلے پہلاں ای ممکن سی۔ پر جفت، غیر صفر چکراں دی گنتی بالکل صفر ورگی لگدی اے۔ کلاسیکی حل ایہہ اے کہ جوڑاں نوں بے ترتیب وزن دتے جان تاں جے کسے کل وزن تے اک حل اکلا رہ جاوے (وکھرا کرن والا لیما، isolation lemma)؛ پر طاق جفت گنن دا تیز طریقہ وزناں نال کم نہیں کر سکدا سی۔

لکھاریاں دا نسخہ، سادے لفظاں وچ:

  1. چکر دے اک تیر دا اندازہ لاؤ، تے ایہدی تھاں اوس تیر دے اک سرے توں دوجے تک ہر بندو توں لنگھدا راہ لبھو۔
  2. ہر تیر نوں 1/50 امکان نال بے ترتیبی نال مٹاؤ۔
  3. ہر بندو تے آن والے تیراں دیاں تن ٹولیاں بناؤ، تے ہر بچے تیر نوں ٹولیاں دے اک بے ترتیب، غیر خالی سیٹ وچ نقل کرو۔
  4. جے چکر موجود اے، تے گھٹو گھٹ (49/50)ⁿ⁻¹ امکان نال ہر بندو لئی اک ٹولی اینج چنی جا سکدی اے کہ ٹھیک راہواں دی گنتی طاق ہووے۔
  5. ہر ٹولی نوں — ہر تیر نوں نہیں — بے ترتیب وزن دیو۔ ہن وکھرا کرن والی چال کم کردی اے، تے لگ بھگ (50/49)ⁿ دہراؤ کافی نیں۔
  6. ہر دہراؤ، بیورکلنڈ، کاسکی تے کوتس دے میٹرکس ڈیٹرمینینٹاں دے جوڑ تے آروند تے گوروسوامی دی وی ورتی اک بے ترتیب «لکیری کرن» ورت کے، ہر کل وزن تے طاق جفت گنتیاں (15/8)ⁿ ویلے وچ کڈھدا اے۔

دوہاں نوں ضرب دیو: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ۔

مشین دا بنایا ثبوت

مقالہ تخلیقی اے آئی بارے اک اعلان نال مکدا اے: مرکزی تھیورم دا ثبوت ChatGPT 6 Astra نے بنایا تے مسودہ تیار کرن وچ مدد کیتی۔ لکھاریاں نے وچکارلیاں تجویزاں دے بیان دتے، جیہڑے ماڈل دے اصل حل دی اک ترکیبی (combinatorial) پڑھت دیندے نیں، فیر ہر شے دی تصدیق تے سدھائی کیتی تے پوری ذمہ داری لیندے نیں۔

نتیجہ نظری اے — کوئی پروگرام نہیں چلایا گیا — تے الگورتھم بے ترتیب اے، دوہاں پاسیاں غلطی دے اک نکے امکان نال۔ اک پاسی گلیاں لئی 1.9133 تے دو پاسیاں لئی 1.657 دے وچکار، اک چوڑا خلا اجے کھلا اے۔