Closest string
نظریاتی کمپیوٹر سائنس میں، قریب ترین سٹرنگ ایک این پی ہارڈ کمپیوٹیشنل مسئلہ ہے، جو ان پٹ سٹرنگ کے سیٹ کے ہندسی مرکز کو تلاش کرنے کی کوشش کرتا ہے۔ لفظ "مرکز" کو سمجھنے کے لیے، دو تاروں کے درمیان فاصلے کی وضاحت کرنا ضروری ہے۔ عام طور پر، اس مسئلے کا مطالعہ ہیمنگ کے فاصلے کو ذہن میں رکھتے ہوئے کیا جاتا ہے۔ رسمی تعریف مزید رسمی طور پر، n لمبائی-m سٹرنگ s1، s2،.، sn کو دیکھتے ہوئے، قریب ترین سٹرنگ کا مسئلہ ایک نئی لمبائی-m سٹرنگ s کی تلاش کرتا ہے جیسے کہ تمام i کے لیے d (s، si) ≤ k، جہاں d ہیمنگ فاصلے کی نشاندہی کرتا ہے، اور جہاں k جتنا ممکن ہو اتنا چھوٹا ہے۔ قریب ترین سٹرنگ کے مسئلے کا فیصلہ مسئلہ ورژن، جو کہ NP مکمل ہے، اس کے بجائے k کو ایک اور ان پٹ کے طور پر لیتا ہے اور سوال کرتا ہے کہ آیا تمام ان پٹ سٹرنگز کے ہیمنگ فاصلے k کے اندر کوئی سٹرنگ ہے یا نہیں۔ قریب ترین تار کے مسئلے کو عام 1-مرکز کے مسئلے کے ایک خاص معاملے کے طور پر دیکھا جا سکتا ہے جس میں عناصر کے درمیان فاصلے کو ہیمنگ فاصلے کا استعمال کرتے ہوئے ماپا جاتا ہے۔ بائیو انفارمیٹکس میں، قریب ترین سٹرنگ کا مسئلہ ڈی این اے میں سگنلز تلاش کرنے کے مسئلے کا ایک گہرائی سے مطالعہ شدہ پہلو ہے۔ آسانیاں اور ڈیٹا میں کمی قریب ترین سٹرنگ کی مثالوں میں ایسی معلومات ہو سکتی ہیں جو مسئلے کے لیے ضروری نہیں ہیں۔ کچھ معنوں میں، قریب ترین سٹرنگ کے معمول کے ان پٹ میں معلومات ہوتی ہیں، جو مسئلہ کی سختی میں معاون نہیں ہوتی ہیں۔ مثال کے طور پر، اگر کچھ تاروں میں حرف a موجود ہے، لیکن کسی میں بھی حرف z نہیں ہے، تو سب کو zs کے ساتھ تبدیل کرنے سے بنیادی طور پر مساوی مثال ملے گی، یعنی: ترمیم شدہ مثال کے حل سے، اصل حل کو بحال کیا جا سکتا ہے، اور اس کے برعکس۔ ان پٹ کو معمول پر لانا جب تمام ان پٹ سٹرنگز جو ایک ہی لمبائی کا اشتراک کرتے ہیں ایک دوسرے کے اوپر لکھے جاتے ہیں، تو وہ ایک میٹرکس بناتے ہیں۔ کچھ صفوں کی اقسام کے حل پر بنیادی طور پر ایک جیسے مضمرات ہوتے ہیں۔ مثال کے طور پر، ایک کالم کو اندراجات (a، a، b) کے ساتھ دوسرے کالم (x، x، y) سے تبدیل کرنا ایک مختلف حل کی تار کا باعث بن سکتا ہے، لیکن حل پذیری کو متاثر نہیں کر سکتا، کیونکہ دونوں کالم ایک ہی ساخت کا اظہار کرتے ہیں، یعنی۔ پہلی دو اندراجات برابر ہیں، لیکن تیسرے سے مختلف ہیں۔ ایک ان پٹ مثال کو ہر کالم میں، اس کردار کو جو اکثر a کے ساتھ آتا ہے، دوسرے کردار کو جو اکثر b کے ساتھ آتا ہے، اور اسی طرح تبدیل کرکے معمول بنایا جا سکتا ہے۔ عام مثال کے حل کو دیکھتے ہوئے، اصل مثال کو ہر کالم میں حل کے حروف کو اس کے اصل ورژن میں دوبارہ نقشہ بنا کر پایا جا سکتا ہے۔ کالموں کی ترتیب مسئلہ کی سختی میں معاون نہیں ہے۔ اس کا مطلب یہ ہے کہ اگر ہم تمام ان پٹ سٹرنگز کو ایک مخصوص ترتیب π کے مطابق ترتیب دیتے ہیں اور اس ترمیم شدہ مثال کے لیے ایک حل سٹرنگ s حاصل کرتے ہیں، تو π−1 (s) اصل مثال کا حل ہوگا۔ مثال تین ان پٹ تاروں uvwx، xuwv، اور xvwu کے ساتھ ایک مثال دی گئی ہے۔ اسے میٹرکس کے طور پر اس طرح لکھا جا سکتا ہے: پہلے کالم میں اقدار (u، x، x) ہیں۔ چونکہ x وہ حرف ہے جو اکثر ظاہر ہوتا ہے، اس لیے ہم اسے a سے بدل دیتے ہیں، اور ہم نئے پہلے کالم (b، a، a) کو حاصل کرتے ہوئے، b سے، جو دوسرا اکثر حرف ہے، u کو بدل دیتے ہیں۔ دوسرے کالم میں اقدار (v، u، v) ہیں۔ جہاں تک پہلے کالم کا تعلق ہے، v کو a سے اور u کو b سے تبدیل کیا جاتا ہے، جس سے نیا دوسرا کالم (a، b، a) حاصل ہوتا ہے۔ تمام کالموں کے ساتھ ایسا کرنے سے نارملائزڈ مثال ملتی ہے۔ نارملائزیشن سے حاصل کردہ ڈیٹا میں کمی ان پٹ کو نارمل کرنے سے حروف تہجی کا سائز کم ہو کر زیادہ سے زیادہ ان پٹ سٹرنگ کی تعداد تک پہنچ جاتا ہے۔ یہ الگورتھم کے لیے مفید ہو سکتا ہے جن کے چلنے کا وقت حروف تہجی کے سائز پر منحصر ہوتا ہے۔ لگ بھگ لی اور دیگر۔ ایک کثیر الجہتی وقت کا تخمینہ اسکیم تیار کیا جو بڑے پوشیدہ مستقلات کی وجہ سے عملی طور پر ناقابل استعمال ہے۔ فکسڈ پیرامیٹر ٹریکٹیبلٹی قریبی سٹرنگ کو حل کیا جا سکتا ہے، جہاں k ان پٹ سٹرنگز کی تعداد ہے، L تمام سٹرنگز کی لمبائی ہے اور d حل سٹرنگ سے کسی بھی ان پٹ سٹرنگ تک مطلوبہ زیادہ سے زیادہ فاصلہ ہے۔ قریبی سٹرنگ زیادہ عام قریب ترین سبسٹرنگ مسئلے کا ایک خاص معاملہ ہے، جو سختی سے زیادہ مشکل ہے۔ اگرچہ قریب ترین سٹرنگ کئی طریقوں سے فکسڈ پیرامیٹر ٹریک ایبل ثابت ہوتی ہے، لیکن ان پیرامیٹرز کے حوالے سے قریب ترین سبسٹرنگ W [1]-سخت ہے۔ حوالہ جات NP-سخت مسائل رسمی زبانیں