Look-ahead (backtracking)
بیک ٹریکنگ الگورتھم میں، آگے دیکھیں ایک ذیلی عمل کے لیے عام اصطلاح ہے جو اس کی اقدار میں سے کسی ایک کا اندازہ کرنے کے لیے برانچنگ متغیر کو منتخب کرنے کے اثرات کا اندازہ لگانے کی کوشش کرتی ہے۔ آگے دیکھنے کے دو اہم مقاصد اگلے کا اندازہ کرنے کے لیے متغیر کا انتخاب کرنا اور اسے تفویض کرنے کے لیے اقدار کی ترتیب کا انتخاب کرنا ہے۔ رکاوٹ کا اطمینان ایک عام رکاوٹ کے اطمینان کے مسئلے میں، ہر متغیر ایک ڈومین میں قدر لے سکتا ہے۔ اس لیے بیک ٹریکنگ الگورتھم بار بار ایک متغیر کا انتخاب کرتا ہے اور اس کی ہر ممکنہ قدر کی جانچ کرتا ہے۔ ہر قدر کے لیے الگورتھم کو بار بار چلایا جاتا ہے۔ آگے دیکھیں کا استعمال تشخیص کے لیے دیے گئے متغیر کو منتخب کرنے کے اثرات کی جانچ کرنے یا اسے دینے کے لیے اقدار کی ترتیب کا فیصلہ کرنے کے لیے کیا جاتا ہے۔ آگے کی تکنیکیں متغیر پر کسی مخصوص تفویض کے اثر کا اندازہ کرنے کی آسان تکنیک کو فارورڈ چیکنگ کہا جاتا ہے۔ موجودہ جزوی حل اور تشخیص کے لیے امیدوار کی تفویض کو دیکھتے ہوئے، یہ جانچتا ہے کہ آیا کوئی دوسرا متغیر مستقل قدر لے سکتا ہے۔ دوسرے لفظوں میں، یہ پہلے موجودہ جزوی حل کو سمجھے جانے والے متغیر کے لیے عارضی قدر کے ساتھ بڑھاتا ہے۔ اس کے بعد یہ ہر دوسرے متغیر پر غور کرتا ہے جو ابھی تک غیر تفویض شدہ ہے، اور جانچتا ہے کہ آیا اس کی کوئی تشخیص موجود ہے جو توسیعی جزوی حل کے مطابق ہے۔ زیادہ عام طور پر، فارورڈ چیکنگ ان اقدار کا تعین کرتی ہے جو توسیعی تفویض کے مطابق ہیں۔ ایک آگے دیکھنے کی تکنیک جو زیادہ وقت طلب ہو سکتی ہے لیکن بہتر نتائج پیدا کر سکتی ہے، آرک کی مستقل مزاجی پر مبنی ہے۔ یعنی، ایک نئے متغیر کی قدر کے ساتھ توسیع شدہ جزوی حل کو دیکھتے ہوئے، یہ تمام غیر تفویض شدہ متغیرات کے لیے آرک کی مستقل مزاجی کو نافذ کرتا ہے۔ دوسرے لفظوں میں، کسی بھی غیر تفویض شدہ متغیر کے لیے، وہ اقدار جنہیں مستقل طور پر کسی دوسرے متغیر تک نہیں بڑھایا جا سکتا انہیں ہٹا دیا جاتا ہے۔ فارورڈ چیکنگ اور آرک کی مستقل مزاجی کے درمیان فرق یہ ہے کہ سابقہ صرف ایک غیر تفویض شدہ متغیر کو مستقل مزاجی کے لیے چیک کرتا ہے، جبکہ دوسرا باہمی مستقل مزاجی کے لیے غیر تفویض شدہ متغیرات کے جوڑوں کو بھی چیک کرتا ہے۔ رکاوٹ کے اطمینان کے مسائل کو حل کرنے کے لیے لک فارڈ کا استعمال کرنے کا سب سے عام طریقہ آرک مستقل مزاجی (ایم اے سی) الگورتھم کو برقرار رکھنا ہے۔ آرک کی مستقل مزاجی سے متعلق دو دیگر طریقے مکمل اور جزوی نظر آگے ہیں۔ وہ آرک کی مستقل مزاجی کو نافذ کرتے ہیں، لیکن متغیرات کے ہر جوڑے کے لیے نہیں۔ خاص طور پر، مکمل نظر غیر تفویض شدہ متغیرات کے ہر جوڑے پر غور کرتی ہے، اور ان کے درمیان آرک کی مستقل مزاجی کو نافذ کرتی ہے۔ یہ عالمی آرک کی مستقل مزاجی کو نافذ کرنے سے مختلف ہے، جس کے لیے ممکنہ طور پر متغیرات کی ایک جوڑی کو ایک سے زیادہ بار دوبارہ غور کرنے کی ضرورت پڑ سکتی ہے۔ اس کے بجائے، ایک بار جب آگے کی مکمل نظر متغیرات کی ایک جوڑی کے درمیان آرک کی مستقل مزاجی کو نافذ کرتی ہے، تو اس جوڑی کو مزید نہیں سمجھا جاتا ہے۔ آگے کی جزوی نظر ایک جیسی ہے، لیکن متغیرات کی دی گئی ترتیب پر غور کیا جاتا ہے، اور آرک کی مستقل مزاجی ہر جوڑے کے لیے صرف ایک بار نافذ کی جاتی ہے۔ آرک کی مستقل مزاجی کی بنیاد پر آگے دیکھیں راستے کی مستقل مزاجی اور عمومی آئی-مستقل مزاجی یا رشتہ دار آرک کی مستقل مزاجی کے ساتھ کام کرنے کے لیے بھی بڑھایا جا سکتا ہے۔ آگے دیکھنے کا استعمال آگے دیکھنے کے نتائج کا استعمال اگلے متغیر کا اندازہ کرنے اور اس متغیر کو اقدار کی ترتیب دینے کے لیے کیا جاتا ہے۔ خاص طور پر، کسی بھی غیر تفویض شدہ متغیر اور قدر کے لیے، آگے دیکھیں اس متغیر کو اس قدر پر ترتیب دینے کے اثرات کا اندازہ لگاتا ہے۔ اگلے متغیر کا انتخاب اور اسے دینے کے لیے اگلی قیمت کا انتخاب تکمیلی ہے، اس میں قیمت کو عام طور پر اس طرح منتخب کیا جاتا ہے کہ حل (اگر کوئی ہو) جلد از جلد مل جائے، جبکہ اگلے متغیر کو عام طور پر اس طرح منتخب کیا جاتا ہے کہ عدم اطمینان (اگر موجودہ جزوی حل غیر تسلی بخش ہو) جلد از جلد ثابت ہو جائے۔ جائزہ لینے کے لیے اگلے متغیر کا انتخاب خاص طور پر اہم ہے، کیونکہ یہ چلانے کے وقت میں متغیر فرق پیدا کر سکتا ہے۔ جتنی جلدی ممکن ہو عدم اطمینان کو ثابت کرنے کے لیے، تفویض کیے جانے کے بعد چند متبادل چھوڑنے والے متغیر ترجیحی ہیں۔ اس خیال کو صرف متغیر/قدر کے جوڑوں کی اطمینان بخش یا عدم اطمینان کی جانچ کر کے نافذ کیا جا سکتا ہے۔ خاص طور پر، اگلا متغیر جو منتخب کیا جاتا ہے وہ ہے جس میں کم سے کم اقدار ہوتی ہیں جو موجودہ جزوی حل کے مطابق ہوتی ہیں۔ بدلے میں، مستقل مزاجی کا اندازہ صرف جزوی مستقل مزاجی کی جانچ کر کے، یا اوپر بیان کردہ کسی بھی زیر غور نظر آنے والی تکنیک کا استعمال کر کے کیا جا سکتا ہے۔ متغیر کو عارضی طور پر تفویض کرنے کے لیے اقدار کو ترتیب دینے کے لیے درج ذیل تین طریقے ہیں: کم سے کم تنازعات: ترجیحی اقدار وہ ہیں جو غیر تفویض شدہ متغیرات کے ڈومین سے کم سے کم کل اقدار کو ہٹا دیتی ہیں جیسا کہ آگے دیکھ کر اندازہ کیا جاتا ہے۔ زیادہ سے زیادہ ڈومین سائز: ترجیحی اقدار وہ ہیں جو غیر تفویض شدہ متغیرات کے لیے پیدا ہونے والے سب سے چھوٹے ڈومین میں اقدار کی تعداد کو زیادہ سے زیادہ کرتی ہیں، جیسا کہ آگے دیکھ کر اندازہ لگایا جاتا ہے۔ حل کا تخمینہ لگائیں: ترجیحی اقدار وہ ہیں جو حل کی زیادہ سے زیادہ تعداد تیار کرتی ہیں، جیسا کہ آگے دیکھ کر اندازہ لگایا جاتا ہے کہ غیر تفویض شدہ متغیرات کے ڈومین میں باقی تمام اقدار ایک دوسرے کے ساتھ مطابقت رکھتی ہیں۔ دوسرے الفاظ میں، قیمت کی ترجیح آگے دیکھنے کے نتیجے میں تمام ڈومینز کے سائز کو ضرب دے کر حاصل کی جاتی ہے۔ تجربات نے ثابت کیا کہ یہ تکنیکیں بڑے مسائل، خاص طور پر چھوٹے تنازعات کے لیے مفید ہیں۔ بے ترتیب کاری کو بعض اوقات متغیر یا قدر کے انتخاب کے لیے بھی استعمال کیا جاتا ہے۔ مثال کے طور پر، اگر کسی پیمائش کے مطابق دو متغیرات کو یکساں طور پر ترجیح دی جاتی ہے، تو انتخاب تصادفی طور پر کیا جا سکتا ہے۔ حوالہ جات محدود پروگرامنگ سرچ الگورتھم