Search problem
کمپیوٹیشنل پیچیدگی کے نظریہ، کمپیوٹیبلٹی تھیوری، اور فیصلہ کے نظریہ کی ریاضی میں، تلاش کا مسئلہ ایک قسم کا کمپیوٹیشنل مسئلہ ہے جس کی نمائندگی بائنری رشتہ کرتا ہے۔ بدیہی طور پر، مسئلہ آبجیکٹ "x" میں ساخت "y" کو تلاش کرنے پر مشتمل ہے۔ ایک الگورتھم کو اس مسئلے کو حل کرنے کے لیے کہا جاتا ہے اگر کم از کم ایک متعلقہ ڈھانچہ موجود ہو، اور پھر اس ڈھانچے کی ایک موجودگی کو آؤٹ پٹ بنایا جاتا ہے ؛ بصورت دیگر، الگورتھم ایک مناسب آؤٹ پٹ ("نہیں ملا" یا اس طرح کا کوئی پیغام) کے ساتھ رک جاتا ہے۔ ہر تلاش کے مسئلے میں ایک متعلقہ فیصلہ کا مسئلہ بھی ہوتا ہے، یعنی اس تعریف کو کسی بھی مناسب انکوڈنگ کا استعمال کرتے ہوئے n-ary رلیشنز کے لیے عام کیا جا سکتا ہے جو متعدد سٹرنگز کو ایک سٹرنگ میں کمپریس کرنے کی اجازت دیتا ہے (مثال کے طور پر انہیں ڈیلیمیٹر کے ساتھ لگاتار درج کرکے)۔ مزید رسمی طور پر، ایک رشتہ R کو تلاش کے مسئلے کے طور پر دیکھا جا سکتا ہے، اور ایک ٹورنگ مشین جو R کا حساب لگاتی ہے اسے بھی حل کرنے کے لیے کہا جاتا ہے۔ مزید رسمی طور پر، اگر R ایک بائنری رشتہ ہے جیسے کہ فیلڈ (R) σ + اور T ایک ٹورنگ مشین ہے، تو T R کا حساب لگاتا ہے اگر: اگر x ایسا ہے کہ کچھ y ایسا ہے کہ R (x, y) تو T آؤٹ پٹ z کے ساتھ x کو اس طرح قبول کرتا ہے کہ R (x, z) (ایک سے زیادہ y ہو سکتا ہے، اور T کو صرف ان میں سے ایک تلاش کرنے کی ضرورت ہے) اگر x ایسا ہے کہ کوئی y نہیں ہے کہ R (x, y) ہو تو T x کو مسترد کر دیتا ہے (نوٹ کریں کہ جزوی فنکشن کا گراف بائنری تعلق ہے، اور اگر T جزوی فنکشن کا حساب لگاتا ہے تو زیادہ سے زیادہ ایک ممکنہ آؤٹ پٹ ہوتا ہے۔) اس طرح کے مسائل گراف تھیوری اور مشترکہ اصلاح میں بہت کثرت سے پائے جاتے ہیں، مثال کے طور پر، جہاں مخصوص ملاپ، اختیاری گروہ، مخصوص مستحکم سیٹ وغیرہ جیسے ڈھانچوں کی تلاش کی جاتی ہے۔ دلچسپی کے موضوعات ہیں۔ تعریف ایک تلاش کے مسئلے کی خصوصیت اکثر اس طرح ہوتی ہے: حالتوں کا ایک مجموعہ ایک ابتدائی حالت ایک ہدف کی حالت یا ہدف کی جانچ: ایک بولین فنکشن جو ہمیں بتاتا ہے کہ آیا دی گئی حالت ایک ہدف کی حالت ہے۔ ایک جانشین فنکشن: کسی ریاست سے نئی حالتوں کے ایک سیٹ کی نقشہ سازی۔ مقصد اس وقت حل تلاش کریں جب کسی مسئلے کو حل کرنے کے لیے الگورتھم نہ دیا جائے، بلکہ صرف اس بات کی وضاحت کریں کہ حل کیسا لگتا ہے۔ سرچ میتھڈ جنیرک سرچ الگورتھم: گراف، اسٹارٹ نوڈس، اور گول نوڈس کو دیکھتے ہوئے، اسٹارٹ نوڈس سے راستے بڑھاتے ہوئے تلاش کریں۔ اسٹارٹ نوڈ سے راستوں کی سرحد کو برقرار رکھیں جن کی کھوج کی گئی ہے۔ جیسے جیسے تلاش آگے بڑھتی ہے، سرحد غیر دریافت شدہ نوڈس میں پھیل جاتی ہے جب تک کہ گول نوڈ کا سامنا نہ ہو۔ جس طرح سے سرحد کو بڑھایا جاتا ہے وہ تلاش کی حکمت عملی کی وضاحت کرتا ہے۔ ان پٹ: ایک گراف، اسٹارٹ نوڈس کا ایک سیٹ، بولین پروسیجر گول (n) جو جانچتا ہے کہ آیا n ایک گول نوڈ ہے۔ فرنٹیئر: = {s: s ایک اسٹارٹ نوڈ ہے} ؛ جب کہ فرنٹیئر خالی نہیں ہے: راستہ منتخب کریں اور ہٹا دیں <n0،.، nk> فرنٹیئر سے ؛ اگر گول (nk) واپس آتا ہے <n0،.، nk> ؛ nk کے ہر پڑوسی کے لیے <n0،.، nk، n> فرنٹیئر میں شامل کریں ؛ اختتام جبکہ یہ بھی دیکھیں لامحدود سرچ آپریٹر فیصلہ سازی کا مسئلہ آپٹیمائزیشن کا مسئلہ گنتی کا مسئلہ (پیچیدگی) فنکشن کا مسئلہ تلاش کے کھیل حوالہ جات کمپیوٹیشنل مسائل