ایم آئی ٹی میں ایک پیچیدہ مسئلہ کے ساتھ گڈ ول شکار کا منظر

الگورتھم اور ہیورسٹکس کے مابین فرق

آئیے کچھ دلچسپ مسائل اور ان کے لطیف پہلوؤں کے ذریعہ الگورتھم کی عمارت کے بنیادی ڈھانچے کو دیکھیں

محرک

کئی سالوں سے مجھے یہ احساس ہوا ہے کہ انفارمیٹکس "کمپیوٹر" یا "پروگرامنگ" کے بارے میں نہیں ہے۔ ہم اس جال میں پھنس چکے ہیں کیونکہ ہم بہت سے عام الفاظ "کمپیوٹر" اور "پروگرامنگ" کے عادی ہیں۔ کمپیوٹر سائنس - مشکلات کا مطالعہ۔ اس مسئلے کو دیکھتے ہوئے ، کمپیوٹر سائنس دان کا ہدف یہ ہے کہ کسی بھی ممکنہ پریشانیوں سے نمٹنے کے لئے الگورتھم ، ایک قدم بہ قدم فہرست تیار کریں۔ الگورتھم محدود عمل ہیں ، اور اگر ان کی پیروی کی جائے تو ہم اس مسئلے کو حل کریں گے۔ دنیا کی ہر چیز کی طرح چند مستثنیات کے ساتھ الگورتھم واقعی حل ہیں۔ اس کو حاصل کرنے کے لئے کمپیوٹر اور پروگرامنگ صرف ٹولز ہیں۔

ایک بار جب مجھے یقین ہو گیا کہ "کمپیوٹر سائنس الگورتھم کی تعلیم ہے ،" میں جلدی سے اس کو ریاضی سے جوڑ سکتا ہوں۔ در حقیقت ، وہ جڑواں بھائیوں سے زیادہ ہیں۔ وہ خوبصورتی جو آپ اب آہستہ سے ایک نظم و ضبط سے دوسرے شعبے میں منتقل کرسکتے ہیں۔ مختصرا if ، اگر میں یہ کہوں کہ ریاضی کمپیوٹر سائنس پر مبنی ہے اور یہ کہ الگورتھم ریاضی کی نمائندگی کرنے کا ایک اور طریقہ ہے تو میں غلطی نہیں کروں گا۔ یہ دماغ کی موسیقی ہے۔

یہ مسئلہ حل کرنے والا ، فکری طور پر عبور حاصل کرنے اور خوبصورت بنانا ہے - یہی میرے لئے الگورتھم سیکھنا شروع کرنا ہے۔ مجھے یقین ہے کہ آپ بھی کریں گے۔ میں اس حص sectionے کو دو حوالوں کے ساتھ اختتام کرتا ہوں جو تحقیق اور بلا شبہ فیڈ سوچ کے لئے ایک اچھی بنیاد فراہم کرتے ہیں۔

الگورتھم پر بھروسہ کرنا چاہئے۔ - ڈونلڈ نٹ (ریاضی دان اور کمپیوٹر سائنسدان)
جان وان نیومن
اگر لوگ یہ نہیں مانتے کہ ریاضی آسان ہے تو ، اس کی وجہ وہ نہیں جانتے کہ زندگی کتنی پیچیدہ ہے۔ - جان وان نیومان (ریاضی ، طبیعیات ، شماریات ، معاشیات اور اطلاعات)

تعارف

آئیے اس مسئلے سے شروعات کریں۔ الگورتھمک مسئلہ کی ترتیب کے طور پر جانا جاتا ہے مندرجہ ذیل کی وضاحت کی گئی ہے.

کسی مسئلے اور مسئلے کی مثال کے مابین فرق بہت ضروری ہے۔ اس معاملے میں ، مثال کے طور پر {سورو ، بھاونا ، جین ، مائک ، رام ، رچا names یا {7، 12، 11، 101، 45 like جیسے نمبروں کی فہرست جیسے ناموں کا مجموعہ ہوسکتا ہے۔ تاہم ، "ترتیب دیں" الگورتھم ایک عام مسئلہ ہے ، لہذا آپ کو ایک مشترکہ حل کی ضرورت ہے جو کسی بھی طرح کی رسائی کو قبول کرتا ہے اور آپ کو مطلوبہ نتائج دیتا ہے۔ انضباطی مسئلے کو حل کرنے کے لئے مختلف الگورتھم موجود ہیں ، جن میں سے ایک "ترمیم" کہلاتا ہے۔

متحرک بہاؤ ترتیب دیں

ایڈ لسٹنگ ایک چھانٹ کا طریقہ ہے جو ایک شے سے شروع ہوتا ہے (صرف ایک فہرست بنانا) اور پھر باقی اشیاء کو آرڈر لسٹ میں شامل کرنا۔ نمائندگی کو بائیں طرف چیک کریں۔

پیتھون کا ارادہ ترتیب پر عمل درآمد مندرجہ ذیل ہے:

داخلی ترتیب کو ترتیب دیں داخلی عمل

ہم ہمیشہ الگورتھم کی تلاش کرتے ہیں جو درست ، موثر اور نفاذ میں آسان ہیں۔ اس تعارف میں ہم صرف الگورتھم کی درستگی پر توجہ دیں گے۔

مناسب الگورتھم اکثر اوقات درستگی کے ثبوت کے ساتھ فراہم کیے جاتے ہیں ، اس کا مطلب یہ ہے کہ کسی مسئلے کی ہر مثال ، جیسا کہ ہم اوپر والی مثال میں دیکھ چکے ہیں ، مطلوبہ نتیجہ نکالنا چاہئے۔ لیکن ، آگے بڑھنے سے پہلے ، ہم یہ ظاہر کریں کہ یہ کبھی بھی درست کیوں نہیں ہے ، اور عام طور پر کیوں نہیں ، کیوں یہ "واضح" ہے۔

کیا میرا الگورتھم واضح ہے یا درست؟

اس مسئلے پر غور کریں جو اکثر مینوفیکچرنگ ، ٹرانسپورٹ اور جانچ پروگراموں میں ہوتا ہے۔ فرض کیجئے کہ آپ کے پاس ٹھوس فروخت کرنے کی صلاحیت رکھنے والا روبوٹ ہے۔ اب آپ الیکٹرانک کارڈ کو سولڈر کرنا چاہتے ہیں ، جس میں چپ اور دوسرے حصے ہوتے ہیں جن کو بورڈ کے ساتھ منسلک کرنے کی ضرورت ہوتی ہے۔ تو واضح سوال یہ ہے کہ روبوٹ کس طرح بورڈ کے گرد گھوم سکتا ہے اور اپنا کام انجام دے سکتا ہے۔ یہ مؤثر طریقے سے کیا جانا چاہئے کیوں کہ بہت سارے بورڈ ایسے ہیں جن کی ایک مقررہ مدت میں تیاری کی ضرورت ہے ، اور ہر بورڈ میں ایسی بہت سی سولڈرنگ سائٹس ہیں۔

مسئلے کی سرکاری وضاحت اس طرح دکھائی دیتی ہے اور ہمیں روبوٹ بازو کو پروگرام کرنے کی ضرورت ہے۔

مسئلہ: روبوٹ کی قسم کو بہتر بنانا

تعارف: ہوائی جہاز پر S 'n' پوائنٹ مجموعہ

نتیجہ: سیٹ سی میں ہر ایک نقطہ پر جانے کے لئے سب سے مختصر سائیکل کی قسم کیا ہے؟

سپلائی -1: قریب میں پڑوس ہیوریئسٹ ہے

شاید سب سے اہم خیال قریب ترین پڑوسی ہوریسٹک ہے۔ کچھ بے ترتیب p0 پوائنٹ سے ہم قریب ترین پڑوسی P1 کی طرف چلتے ہیں۔ P1 سے شروع کرتے ہوئے ، ہم اس کے قریب ترین غیر شناخت شدہ پڑوسی کے پاس جاتے ہیں (لہذا p0 امیدوار کے طور پر نہیں گنتی جاتا ہے)۔ ہم ایک نقطہ تک تمام نکات دہراتے ہیں اور پھر ٹور مکمل کرنے کے لئے اپنے ابتدائی نقطہ p0 پر واپس آجاتے ہیں۔

لہذا ، یہاں مرکزی خیال یہ ہے کہ سفر کے وقت کو کم کرنے کے لئے طویل فاصلے دیکھنے سے پہلے قریبی جگہوں کا دورہ کرنا ہے۔ یہ اوپر والے اعداد و شمار 1 میں بہت اچھی طرح سے کام کرتا ہے اور یہ بہت چھوٹا بھی نہیں ہے ، لیکن ہر ایک جوڑے کو پوائنٹس (pi، pj) پر دو بار دیکھنا اچھ .ا ہوگا ، پرجاتیوں میں pj شامل کرنے پر pi اور دوسرے کو شامل کریں گے۔ بدقسمتی سے ، یہ الگورتھم سبھی نہیں ہے۔

یقینی طور پر ، الگورتھم نے اس قسم کو تلاش کیا ، لیکن اس کا مطلب بھی مختصر ترین قسم کا نہیں ہے۔ صورتحال پر ایک نگاہ ڈالیں جب تمام خیالات ایک لکیر کے ساتھ پڑے ہوئے ہیں ، تو شکل 2 دیکھیں۔ اگر ہم 0 سے شروع کرتے ہیں تو ، ہم بائیں سے دائیں کودنا جاری رکھیں گے ... بہترین ٹور بائیں نقطہ سے شروع ہوسکتا ہے ، اور جب ہم دائیں طرف جاتے ہیں تو ، ہر ایک نقطہ پر جائیں اور آخر میں پہلے مقام پر واپس آجائیں۔

تعریف 2: قریب ترین پڑوسی ہیوریسٹک ہے

ہوسکتا ہے کہ ہمیں ایک مختلف نقطہ نظر کی ضرورت ہو۔ قریب ترین مقام تک پہنچنے کے لئے یہ ہمیشہ بہت محدود ہوتا ہے۔ اس طرح ، یہ بتانا ممکن نہیں ہے کہ آیا الگورتھم صحیح ہیں یا غلط۔

سوال یہ پیدا ہوتا ہے کہ اس مسئلے کو حل کرنے کے ل the صحیح الگورتھم کیا ہونا چاہئے؟ ٹھیک ہے ، ایک جواب واضح ہوسکتا ہے ، تمام پوائنٹس کے ممکنہ ترتیب کی فہرست بنائیں ، اور پھر اس ترتیب کا انتخاب کریں جس کی پوری لمبائی کم سے کم ہوجائے۔ اس طرح ، ہماری ضمانت ہے کہ کم سے کم سفر مکمل کریں۔

اب ہم اس موقع کا دوبارہ جائزہ لیں گے۔ فرض کریں کہ آپ کے کل 20 پوائنٹس ہیں۔ لہذا ہمارے پاس 20 پوائنٹس کے ساتھ ہر ممکن راستے کا حساب کتاب کرنا ہے! (20 واقعاتی) ، یہ 10 سائز کا 18 مختلف آرڈر ہے۔ اب یہ کمپیوٹر کے لئے ایک بہت بڑی تعداد ہے ، اور اگر n = 1000 ، اس کا مطلب یہ ہے کہ کمپیوٹر کو تمام اختیارات کا اندازہ کرنے اور اس کا تعین کرنے سے پہلے کہ ہمیں کون سا راستہ مختصر ہے اس سے پہلے ہمیں کسی اور بڑے دھماکے کا انتظار کرنا پڑے۔ .

اس مسئلے کو اکثر ٹریولنگ وینڈر (ٹی ایس پی) مسئلہ کہا جاتا ہے ، اور ہم اس مسئلے کو حل کرنے کے لئے ایک موثر الگورتھم تلاش کرنے کی کوشش کر رہے ہیں ، لیکن ابھی اس بحث سے اصل ڈرا کیا ہے الگورتھم اور اصولوں کے درمیان بنیادی فرق ہے۔ ہورسٹک الگورتھم ہمیشہ صحیح نتیجہ برآمد کرتے ہیں ، لیکن ہورسٹک بہت بہتر کام کرسکتا ہے لیکن کبھی بھی مکمل حل کی ضمانت نہیں دیتا ہے۔

الگورتھم کی درستگی کے بارے میں مزید

آئیے الگوریتم کی توثیق کے مقام پر اپنے ذہن کو وسعت دینے کے لئے ایک اور دشواری کو دیکھیں۔ منصوبہ بندی میں یہ مسئلہ ہے۔ ہم کہتے ہیں کہ آپ اداکار / اداکارہ کے بعد سب سے زیادہ طلب گار ہیں اور سائن اپ کرنے کے لئے آپ کو فلموں کی فہرست مل گئی ہے۔ پروجیکٹس منصوبے کے آغاز اور اختتامی تاریخ کے ساتھ آتی ہیں۔ آپ اب دو پروجیکٹس کو قبول نہیں کرسکتے ہیں جو ایک ساتھ ایک دوسرے کے ساتھ ہم آہنگ ہوں۔

اپنے جیسے فنکار کا مقصد ان منصوبوں سے زیادہ سے زیادہ رقم کمانا ہے۔ ہر پروجیکٹ کو ایک ہی ادائیگی ہوتی ہے ، اس کا مطلب ہے کہ آپ ان منصوبوں کی سب سے بڑی رقم تلاش کر رہے ہیں جن کا وقت موافق نہیں ہے۔ منصوبہ بندی کے اس مسئلے کی مثال پر غور کریں۔

آؤٹ پٹ - 3: منصوبہ بندی کا مسئلہ

اب ، مثال کے طور پر ، سرکاری طور پر اس مسئلے کی شناخت کریں -

مسئلہ: فلم کی منصوبہ بندی میں دشواری

تعارف: لائن پر ن وقفوں کا سیٹ کریں۔

نتیجہ: غیر اوورلیپنگ وقفوں کا سب سے بڑا مجموعہ کیا ہے جو I سے منتخب کیا جاسکتا ہے؟

مجھے یقین ہے کہ اس الگورتھم کو ڈیزائن کرنے کے لئے کافی آئیڈیاز ملیں گے۔ پہلا کام یہ ہے کہ آپ کام شروع کرسکتے ہیں جب پہلی ملازمت دستیاب ہو ، مطلب یہ ہے کہ اگر آپ بیکار نہیں رہنا چاہتے ہیں تو آپ کو جلد سے جلد شروع کی تاریخ سے ہی شروع کرنا ہوگا۔

ابتدائی تاریخ کا انتخاب کرنے کا الگورتھم

اب یہ اچھا خیال کیوں نہیں ہے۔ پہلی ملازمت کے بارے میں سوچو ، اس میں کافی وقت لگے گا اور کاروباری امکانات کو کم ڈیڈ لائن کے ساتھ ختم کردیں گے۔ اس منظر نامے کو ذیل میں بیان کیا گیا ہے۔

ابتدائی الگورتھم کے ساتھ شروع کرنے کے لئے ایک برا خیال

اس طرح ، آپ کے لئے یہ قدرتی ہوگا کہ آپ مختصر ترین نوکری کا انتخاب کرنا شروع کریں اور ہر موڑ پر کم سے کم نوکری تلاش کریں۔ اس تعداد کو زیادہ سے زیادہ کرنے سے محصول میں اضافہ ہوسکتا ہے۔ آئیے باضابطہ طور پر اس ہورسٹک کی وضاحت کریں۔

مختصر ملازمت کے انتخاب

اب یہ نقطہ نظر اچھا لگتا ہے ، لیکن چھوٹی ملازمتیں ملنے سے ہم نصف تنخواہ تک محدود رہ سکتے ہیں۔ اس معاملے میں ذیل کی شبیہہ پر غور کریں۔

مختصر کام کا انتخاب کرکے ادائیگی کو محدود کریں

تو آئیے ایک الگورتھم ڈھونڈیں جو صحیح اور موثر ہے۔

فلم کی منصوبہ بندی میں دشواریوں کے ل Proper مناسب اور موثر الگورتھم

لہذا ، ہمارے معاملے میں ، ڈپریشن -3 پر نظر ڈالیں تاکہ یہ معلوم ہوسکے کہ پروجیکٹوں کو کس طرح ترتیب دیا جاتا ہے۔ نیچے دی گئی تصویر میں دکھایا گیا ہے کہ کیسے ایک فنکار فلموں کو قبول کرتا ہے۔

فلم کی منصوبہ بندی کے مسئلے کو حل کرنا

سفر

  1. ہمیشہ الگورتھم کے ساتھ ہیوریسٹس میں ہمیشہ نمایاں فرق ہوتا ہے جو ہمیشہ درست رہتا ہے اور عام طور پر اچھ workے کام کرتے ہیں لیکن اس کی کوئی ضمانت نہیں ہے۔
  2. الگورتھم کی درستگی ایک ایسی خصوصیت ہے جس کا احتیاط کے ساتھ مظاہرہ کرنے کی ضرورت ہے۔

مصنف کا نوٹ

یہ "الگورتھم اور ڈیٹا سٹرکچر" سیریز کا پہلا مضمون ہے۔ اگلے آرٹیکل میں ، ہم ایک ریاضی کا حلقہ بنائیں گے جو الگورتھم کی درستگی کو ظاہر کرتا ہے۔ خبر پر عمل کریں ، باخبر رہیں۔ ہمارے ساتھ رہیں…

خوش سیکھنے :)

حوالہ جات

  1. الگورتھم ڈویلپمنٹ گائیڈ۔ اسٹیفن سکیانا ، سنی اسٹونی بروک ، محکمہ برائے اطلاعات ، امریکہ۔
  2. الگورتھم تک رسائی ۔کورن ، لیزرسن ، ریوسٹ اور اسٹین
  3. ازگر کا استعمال کرتے ہوئے الگورتھم اور ڈیٹا ڈھانچے۔ بریڈ ملر اور ڈیوڈ رینم ، لوتھر کالج