negar92
12-03-2012, 12:59 AM
الگوریتمهای تقریبی
از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
در علوم کامپیوتر الگوریتم های تقریبی، الگوریتمهایی برای پیداکردن راه حل های تقریبی برای مسائل بهینه سازی هستند.این الگوریتم ها اغلب برای حل تقریبی مسائل ان پی-سخت (NP-hard) بکار می‌روند زیرا بسیاری از مسائل بهینه سازی ان پی-سخت هستند ( در واقع بررسی کردن درستی جواب اینگونه مسائل با حل کلی آنها معادل است ) طبق تئوری پیچیدگی محاسباتی (Computational complexity theory) تا زمانیکه http://pnu-club.com/imported/2012/12/1.png، الگوریتمهای کارامد با زمان چند جمله ای برای چنین مسائلی پیدا نخواهد شد مگر اینکه P=NP که چنین فرضی هم خیلی بعید است .
برخلاف روش‌های مکاشفه ای (Heuristics) که راه حلهایی بهینه، اغلب بدون اثبات و بدون کران برای جواب خود هستند؛ الگوریتمهای تقریبی راه حلهایی شبه بهینه همراه با ضریبی برای میزان تقریب جواب واقعی ارائه می‌دهند همچنین وجود جواب خود را در بازهٔ خطای اعلام شده تضمین می‌کنند .( مثلا جواب آنها ۲ برابر جواب بهینه است) منتها جواب خود را در زمان چندجمله‌ای تولید می‌کنند
الگوریتمهای تقریبی برای مسائل P نیز استفاده می‌شوند ولی به ازای ورودی‌های بزرگ خوب عمل نمی‌کنند.
یکی از مثالهای معروف برای الگوریتمهای تقریبی، مسئله پوشش راسی (vertex cover) در گراف است : پیدا کردن یال پوشش داده نشده و اضافه کردن هر دو رأس آن به مجموعه پوشش رأسی تا زمانی که هیچ یال پوشش نیافته نماند . واضح است که مجموعه جوابهای این الگوریتم دو برابر جوابهای بهینه یعنی مجموعه کمترین رأس‌ها برای پوشش دادن همه یالها در یک گراف است؛ پس ضریب ثابت این الگوریتم ۲ است .
الگوریتمهای تقریبی موجود برای مسائل ان پی-سخت با هم تفاوت بسیاری دارند؛ مثلاً مسئله بسته بندی(bin packing problem ) را می‌توان به ازای هر ضریب بزرگتر از یک تقریب زد ، (اگر بتوانیم الگوریتمی تقریبی با ضریب یک برای چنین مسائلی ارائه دهیم P=NP می‌شود) به این خانواده از مسائل PTAS می‌گویند؛ درحالیکه ثابت شده است که برای برخی مسائل دیگر هیچ الگوریتم تقریبی ای یافت نمی‌شود مگر آنکه P=NP شود مانند مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) (maximum clique problem)
مسائل ان پی-سخت را می‌توان با دستورکارهای خطی (integer programs) (مسائل برنامه ریزی خطی ای که http://pnu-club.com/imported/2012/12/2.pngهای صحیح دارند ) متناظر کرد و در نتیجه آنها را در زمانهای نمایی حل کرد (مسائل IP در مرتبه زمانی نمایی حل می‌شوند )
تضمین کارایی الگوریتمهای تقریبی
می توانیم برای برخی از الگوریتمهای تقریبی، خصوصیاتی را اثبات کنیم مثلاً برای http://pnu-club.com/imported/2012/12/3.pngالگوریتمهای تقریبی ثابت شده است که تقریب http://pnu-club.com/imported/2012/12/4.png بیشتر ( و یا کمتر ) از http://pnu-club.com/imported/2012/12/5.png برابر جواب بهینه http://pnu-club.com/imported/2012/12/6.png نخواهد بود :
ضریب http://pnu-club.com/imported/2012/12/5.png را ضریب تضمین کارایی نسبی می‌گویند . هر الگوریتم تقریبی ای تضمین کارایی مطلق و یا کران خطای http://pnu-club.com/imported/2012/12/7.png دارد اگر:
http://pnu-club.com/imported/2012/12/8.png
به طور مشابه نسبت کارایی مطلق http://pnu-club.com/imported/2012/12/9.png الگوریتم های تقریبی http://pnu-club.com/imported/2012/12/10.png :
http://pnu-club.com/imported/2012/12/11.png
(http://pnu-club.com/imported/2012/12/12.png یک نمونه از مسئله و http://pnu-club.com/imported/2012/12/13.png تضمین کارایی http://pnu-club.com/imported/2012/12/10.png روی http://pnu-club.com/imported/2012/12/12.png است .)
در واقع http://pnu-club.com/imported/2012/12/9.png بزرگترین کران نسبت تقریب http://pnu-club.com/imported/2012/12/14.png روی همه نمونه‌های مسئله است . همچنین نسبت کارایی مجانبی http://pnu-club.com/imported/2012/12/15.png :
http://pnu-club.com/imported/2012/12/16.png
از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
در علوم کامپیوتر الگوریتم های تقریبی، الگوریتمهایی برای پیداکردن راه حل های تقریبی برای مسائل بهینه سازی هستند.این الگوریتم ها اغلب برای حل تقریبی مسائل ان پی-سخت (NP-hard) بکار می‌روند زیرا بسیاری از مسائل بهینه سازی ان پی-سخت هستند ( در واقع بررسی کردن درستی جواب اینگونه مسائل با حل کلی آنها معادل است ) طبق تئوری پیچیدگی محاسباتی (Computational complexity theory) تا زمانیکه http://pnu-club.com/imported/2012/12/1.png، الگوریتمهای کارامد با زمان چند جمله ای برای چنین مسائلی پیدا نخواهد شد مگر اینکه P=NP که چنین فرضی هم خیلی بعید است .
برخلاف روش‌های مکاشفه ای (Heuristics) که راه حلهایی بهینه، اغلب بدون اثبات و بدون کران برای جواب خود هستند؛ الگوریتمهای تقریبی راه حلهایی شبه بهینه همراه با ضریبی برای میزان تقریب جواب واقعی ارائه می‌دهند همچنین وجود جواب خود را در بازهٔ خطای اعلام شده تضمین می‌کنند .( مثلا جواب آنها ۲ برابر جواب بهینه است) منتها جواب خود را در زمان چندجمله‌ای تولید می‌کنند
الگوریتمهای تقریبی برای مسائل P نیز استفاده می‌شوند ولی به ازای ورودی‌های بزرگ خوب عمل نمی‌کنند.
یکی از مثالهای معروف برای الگوریتمهای تقریبی، مسئله پوشش راسی (vertex cover) در گراف است : پیدا کردن یال پوشش داده نشده و اضافه کردن هر دو رأس آن به مجموعه پوشش رأسی تا زمانی که هیچ یال پوشش نیافته نماند . واضح است که مجموعه جوابهای این الگوریتم دو برابر جوابهای بهینه یعنی مجموعه کمترین رأس‌ها برای پوشش دادن همه یالها در یک گراف است؛ پس ضریب ثابت این الگوریتم ۲ است .
الگوریتمهای تقریبی موجود برای مسائل ان پی-سخت با هم تفاوت بسیاری دارند؛ مثلاً مسئله بسته بندی(bin packing problem ) را می‌توان به ازای هر ضریب بزرگتر از یک تقریب زد ، (اگر بتوانیم الگوریتمی تقریبی با ضریب یک برای چنین مسائلی ارائه دهیم P=NP می‌شود) به این خانواده از مسائل PTAS می‌گویند؛ درحالیکه ثابت شده است که برای برخی مسائل دیگر هیچ الگوریتم تقریبی ای یافت نمی‌شود مگر آنکه P=NP شود مانند مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) (maximum clique problem)
مسائل ان پی-سخت را می‌توان با دستورکارهای خطی (integer programs) (مسائل برنامه ریزی خطی ای که http://pnu-club.com/imported/2012/12/2.pngهای صحیح دارند ) متناظر کرد و در نتیجه آنها را در زمانهای نمایی حل کرد (مسائل IP در مرتبه زمانی نمایی حل می‌شوند )
تضمین کارایی الگوریتمهای تقریبی
می توانیم برای برخی از الگوریتمهای تقریبی، خصوصیاتی را اثبات کنیم مثلاً برای http://pnu-club.com/imported/2012/12/3.pngالگوریتمهای تقریبی ثابت شده است که تقریب http://pnu-club.com/imported/2012/12/4.png بیشتر ( و یا کمتر ) از http://pnu-club.com/imported/2012/12/5.png برابر جواب بهینه http://pnu-club.com/imported/2012/12/6.png نخواهد بود :
ضریب http://pnu-club.com/imported/2012/12/5.png را ضریب تضمین کارایی نسبی می‌گویند . هر الگوریتم تقریبی ای تضمین کارایی مطلق و یا کران خطای http://pnu-club.com/imported/2012/12/7.png دارد اگر:
http://pnu-club.com/imported/2012/12/8.png
به طور مشابه نسبت کارایی مطلق http://pnu-club.com/imported/2012/12/9.png الگوریتم های تقریبی http://pnu-club.com/imported/2012/12/10.png :
http://pnu-club.com/imported/2012/12/11.png
(http://pnu-club.com/imported/2012/12/12.png یک نمونه از مسئله و http://pnu-club.com/imported/2012/12/13.png تضمین کارایی http://pnu-club.com/imported/2012/12/10.png روی http://pnu-club.com/imported/2012/12/12.png است .)
در واقع http://pnu-club.com/imported/2012/12/9.png بزرگترین کران نسبت تقریب http://pnu-club.com/imported/2012/12/14.png روی همه نمونه‌های مسئله است . همچنین نسبت کارایی مجانبی http://pnu-club.com/imported/2012/12/15.png :
http://pnu-club.com/imported/2012/12/16.png