Domination analysis
تخمینہ الگورتھم کا تسلط تجزیہ اس کی کارکردگی کا اندازہ لگانے کا ایک طریقہ ہے، جسے گلوور اور پانن نے 1997 میں متعارف کرایا تھا۔ کلاسیکی تخمینہ تناسب تجزیہ کے برعکس، جو ایک حساب شدہ حل کے عددی معیار کا موازنہ ایک بہترین حل کے ساتھ کرتا ہے، تسلط تجزیہ میں تمام ممکنہ حل کے ترتیب شدہ ترتیب میں حساب شدہ حل کے درجہ کی جانچ کرنا شامل ہے۔ تجزیہ کے اس انداز میں، کہا جاتا ہے کہ ایک الگورتھم میں ڈومینس نمبر یا ڈومینس نمبر K ہوتا ہے، اگر اس مسئلے کے مختلف حل K کا ایک ذیلی مجموعہ موجود ہو جس میں الگورتھم کا آؤٹ پٹ بہترین ہو۔ تسلط کے تجزیے کا اظہار تسلط کے تناسب کا استعمال کرتے ہوئے بھی کیا جا سکتا ہے، جو حل کی جگہ کا وہ حصہ ہے جو دیئے گئے حل سے بہتر نہیں ہے۔ یہ تعداد ہمیشہ وقفے [0,1] کے اندر ہوتی ہے، جس میں بڑی تعداد بہتر حل کی نشاندہی کرتی ہے۔ تسلط کا تجزیہ عام طور پر ان مسائل پر لاگو ہوتا ہے جن کے ممکنہ حل کی کل تعداد معلوم ہوتی ہے اور جن کا درست حل مشکل ہوتا ہے۔ مثال کے طور پر، ٹریولنگ سیلز مین کے مسئلے میں، (n-1) ہیں! n شہروں کے ساتھ کسی مسئلے کے ممکنہ حل۔ اگر کسی الگورتھم کو دکھایا جا سکتا ہے کہ غلبہ نمبر (n-1)! کے قریب ہے، یا اس کے مساوی طور پر تسلط تناسب 1 کے قریب ہے، تو اسے کم غلبہ نمبر والے الگورتھم سے بہتر سمجھا جا سکتا ہے۔ اگر کسی مسئلے کے حل کی جگہ کے بے ترتیب نمونوں کو مؤثر طریقے سے تلاش کرنا ممکن ہے، جیسا کہ ٹریولنگ سیلز مین کے مسئلے میں ہے، تو بے ترتیب الگورتھم کے لیے ایسا حل تلاش کرنا سیدھا ہے جس میں زیادہ امکان کے ساتھ اعلی تسلط کا تناسب ہو: صرف نمونوں کا ایک مجموعہ بنائیں اور ان میں سے بہترین حل منتخب کریں۔ (مثال کے طور پر اورلن اور شرما دیکھیں۔) یہاں بیان کردہ غلبہ نمبر کو گراف کے تسلط نمبر کے ساتھ الجھن میں نہیں ڈالنا چاہیے، جو گراف کے سب سے چھوٹے غالب سیٹ میں عمودی کی تعداد سے مراد ہے۔ حال ہی میں، مضامین کی بڑھتی ہوئی تعداد سامنے آئی ہے جس میں ہیورسٹکس کی کارکردگی کا اندازہ لگانے کے لیے تسلط کے تجزیے کا اطلاق کیا گیا ہے۔ اس قسم کے تجزیے کو کلاسیکی تخمینہ تناسب تجزیہ روایت کے ساتھ مقابلہ کرنے کے طور پر دیکھا جا سکتا ہے۔ دونوں اقدامات کو تکمیلی کے طور پر بھی دیکھا جا سکتا ہے۔ معلوم نتائج اس حصے میں معلوم نتائج کا تکنیکی سروے شامل ہے۔ ورٹیکس کور غیر مطابقت پذیری۔ ε> 0 ہونے دیں۔ جب تک کہ P = NP نہ ہو، ورٹیکس کور کے لیے کوئی کثیر الجہتی الگورتھم ایسا نہیں ہے کہ اس کا تسلط نمبر 3 ((n-n ^ ε)/3) سے زیادہ ہو۔ نیپسیک غیر مطابقت پذیری۔ ε> 0 ہونے دیں۔ جب تک کہ P = NP نہ ہو، نیپسیک کے لیے کوئی کثیر الجہتی الگورتھم ایسا نہیں ہے کہ اس کا تسلط نمبر 2 سے زیادہ ہو۔ زیادہ سے زیادہ اطمینان بخش ٹی ایس پی حوالہ جات تخمینہ الگورتھم