نظریه np در الگوریتم

نمونه ای از مسائلی که نمی توان آنها را به روش سنتی حل کرد مسائل NP هستند. مجموعه «ان پی-سخت» شامل چندهزار مساله مختلف با کاربردهای فراوان است که تاکنون برای آنها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه حل سریعی برای آنها وجود ندارد هم اثبات شده است. البته ثابت شده است که اگر فقط برای یکی از این مساله ها راه حل سریعی پیدا شود، این راه حل موجب حل سریع بقیه مساله ها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه حل سریع آن است که زمان اجرای آن با اندازه ورودی مساله به صورت چندجمله ای رابطه داشته باشد. روش های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مساله NP-Hard وجود دارد: • راه حل تقریبی قابل اثبات(الگوریتم های تقریبی): که در آن یک الگوریتم سریع برای حل مساله ارائه می شود ولی اثبات می شود که اندازه خروجی ضریبی از اندازه خروجی بهینه مساله است. • الگوریتم های مکاشفه ای: با این که الگوریتم هایی سریع هستند و به صورت تقریبی جواب را به دست می آورند، اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد. بسیاری از این الگوریتم ها به صورت تجربی آزمایش می شوند. برخی از این الگوریتم ها از «روش حریصانه» برای حل استفاده می کنند.

کلیدواژه ها:

مسائل ان-پی ، NP-HARD ، الگوریتم های تقریبی ، روش های حل مسئله ، الگوریتم مکاشفه ای ، بهینه سازی مسئله.