ویکی‌پدیا

ان‌پی سخت: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
Levin~fawiki (بحث | مشارکت‌ها)
۶۴ ویرایش‌ها
بدون خلاصۀ ویرایش
Ebrambot (بحث | مشارکت‌ها)
ربات‌ها
۱۶۴٬۵۲۷ ویرایش‌ها
جز ربات: ویرایش جزئی
خط ۱:
[[Imageپرونده:P np np-complete np-hard.svg|thumb|300px|left|[[Euler diagram]] for [[P (complexity)|P]], [[NP (complexity)|NP]], [[NP-complete]], and NP-hard set of problems]]
مجموعه ی «'''ان‌پی-سخت'''» شامل چندهزار مساله ی مختلف با کاربردهای فراوان است که تاکنون برای آن ها راه حل سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد.این که راه حل سریعی برای آن ها وجود ندارد هم اثبات شده است.البته ثابت شده است که اگر فقط برای یکی از این مساله ها راه حل سریعی پیدا شود٫این راه حل موجب حل سریع بقیه ی مساله ها خواهد شد.البته احتمال پیدا شدن چنین الگوریتمی ضعیف است.منظور از راه حل سریع آن است که زمان اجرای آن با اندازه ی ورودی مساله به صورت [[چندجمله ای]] رابطه داشته باشد.
== ریشه ی انگلیسی ==
'''ان پی-سخت:''' [[Wikipediaویکی‌پدیا:NP (complexity)|Non-deterministic Polynomial-time]] hard)→[[Wikipediaویکی‌پدیا:NP-hard|NP-hard]])
* حل نشدنی درزمان چندجمله ای بر حسب اندازه ی ورودی مساله ( زمان معقول)
== مفهوم و مقایسه ی آن با ان پی-کامل ==
مساله ی H '''ان پی-سخت''' است اگر و فقط اگر مساله ی L از نوع [[Wikipediaویکی‌پدیا:NP-complete|'''ان پی-کامل''']] موجود باشد ٫ به طوری که زمان حل آن بر حسب [[چندجمله‌ای]] قابل کاهش به Hباشد: ( L ≤ <sub>T</sub>H )به عبارتی دیگر L را میتوان در زمان زیاد با ماشین [[Wikipediaویکی‌پدیا:oracle|اوراکل]] H حل کرد.به طور غیررسمی ما میتوانیم به الگوریتمی فکر کنیم که میتواندزیرروالی را برای حل H فراخوانی کند و L را در زمان زیاد حل کند اگر فراخوانی آن زیر روال فقط یک گام برای محاسبه طول بکشد.
مسائل ان پی-سخت ممکن است از هر نوعی باشند:[[مسئله تصمیم|مسائل تصمیم گیری]]٫[[Wikipediaویکی‌پدیا:search problems|مسائل جستجو]]٫[[Wikipediaویکی‌پدیا:optimization problems|مسائل بهینه سازی]].
طبق روال تعریف: (توجه داشته باشید که اینها صرفاً ادعا هستند نه تعریف):
* مساله ی H حداقل به سختی مسالهٔ L است. چون H میتواند برای حل L استفاده شود.
* چون L [[Wikipediaویکی‌پدیا:NP-compelete |ان پی-کامل]] است ٫بنابراین به سختی مسائل نوع '''ان پی '''است. مساله ی H حداقل به سختی مساله ی '''ان پی''' است.اما H نباید '''ان پی''' باشد و بنابراین نباید از نوع [[مسئله تصمیم|مسائل تصمیم گیری]] باشد(حتی اگر از نوع مسایل تصمیم گیری باشد نیازی ندارد ازنوع مسائل '''ان پی''' باشد.)
* مسائل [[Wikipediaویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با زمان زیاد با ۱ واحد کاهش به یکدیگر تبدیل میشوند(همچنین تحولات چند جمله‌ای نیز نامیده میشوند.)
همه ی مسائل [[Wikipediaویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با کاهش H میتوانند در زمان زیاد حل شوند.بنابراین همه ی مسائل در '''ان پی''' قابل کاهش به H هستند.توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:
# از [[Wikipediaویکی‌پدیا:NP-complete|'''ان پی-کامل:''']][[مسئله تصمیم|مسائل تصمیم گیری]] به مسائل [[Wikipediaویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با تحولات چندجمله‌ای
# از L به H با کاهش چند جمله‌ای [[ماشین تورینگ|تورینگ]]. [http://fa.wikipedia.org/wiki/%D9%85%D8%A7%D8%B4%DB%8C%D9%86_%D8%AA%D9%88%D8%B1%DB%8C%D9%86%DA%AF]
 
* اگر یک [[الگوریتم]] چندجمله‌ای برای هر مساله ی ان پی-سخت موجود باشد٫ سپس [[الگوریتم|الگوریتم‌]]های چندجمله‌ای برای همه ی مسائل در '''ان پی '''وجود دارند و بنابراین [[P = NP]]
* اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند.زمانی که [[P = NP]] باشد ٫ مسائل حل نمیشوند.حتی اگر مسائل ان پی-سخت بتوانند در زمان زیاد حل شوند.
* اگر [[Wikipediaویکی‌پدیا:optimization problems|مسائل بهینه سازی]] ٫H یک نسخه ی تصمیم گیری [[Wikipediaویکی‌پدیا:NP-complete|'''ان پی-کامل''']] داشته باشند٫ H یک ان پی-سخت است.
* یک اشتباه رایج این است که فکر میکنیم '''ان پی''' در ان پی-سخت بر پایه ی غیر چند جمله‌ای است. اگر چه به طور گسترده انتظار میرود که هیچ الگوریتم غیر چند جمله‌ای بر حسب تابع زمانی برای مسائل ان پی- سخت وجود ندارد ولی این موضوع هنوز اثبات نشده‌است. علاوه بر این مسائل از نوع '''ان پی''' همچنین شامل همه ی مسائلی هستند که میتوانند در چندجمله‌ای از [[تابع ]] زمان حل شوند.
 
== روش حل مسایل ان پی-سخت ==
روش های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مساله ی ان پی-سخت وجود دارد:
* '''راه حل تقریبی قابل اثبات'''( '''[[الگوریتم‌های تقریبی|الگوریتم‌های تقریبی]]''' ):که در آن یک الگوریتم سریع برای حل مساله ارائه میشود ولی اثبات میشود که اندازه ی خروجی ضریبی از اندازه ی خروجی بهینه ی مساله است.
* '''[[الگوریتم مکاشفه‌ای|الگوریتم‌های مکاشفه‌ای]]''':با این که الگوریتم هایی سریع هستند و به صورت تقریبی جواب را به دست می آورند٫اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد.بسیاری از این الگوریتم ها به صورت تجربی آزمایش میشوند.برخی از این الگوریتم ها از «روش حریصانه» برای حل استفاده میکنند.
 
 
=== الگوریتم ها ===
راه‌های معمول مقابله با چنین مسائلی عبارتند از:
* طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
* استفاده از «الگوریتم‌های مکاشفه‌ای»( [[Wikipediaویکی‌پدیا:Heuristic | Heuristic]] ) که جواب‌هایی به‌دست می‌دهد که احتمالاٌ درست هستند.
* پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
== نمونه مسائل ان پی-سخت ==
* [[مسئله فروشنده دوره‌گرد ]]
* مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) ([http://en.wikipedia.org/wiki/Maximum_clique_problem maximum clique problem])
== منابع ==
 
* {{cite book|author = Edwin D. Reilly| year = 2004 | title = [http://books.google.ca/books?id=5Jaa1BVverIC&lpg=PA562&dq=Computers%20and%20Intractability:%20A%20Guide%20to%20the%20Theory%20of%20NP-Completeness&pg=PA560#v=onepage&q=Computers%20and%20Intractability%3A%20A%20Guide%20to%20the%20Theory%20of%20NP-Completeness&f=false] Concise encyclopedia of computer science | publisher = John Wiley and Sons Ltd | isbn = }}
 
* [[نظریه پیچیدگی محاسباتی]]▼
 
[[en:NP-hard]]
▲*[[نظریه پیچیدگی محاسباتی]]
برگرفته از «https://fa.wikipedia.org/wiki/ان‌پی_سخت»