ان‌پی سخت: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Yamaha5Bot (بحث | مشارکت‌ها) جز ←مفهوم و مقایسهٔ آن با ان پی-کامل: ارجاع اشتباه با استفاده از AWB |
FreshmanBot (بحث | مشارکت‌ها) جز اصلاح فاصله مجازی + اصلاح نویسه با استفاده از AWB |
||
خط ۷:
* حل نشدنی درزمان چندجمله‌ای بر حسب اندازهٔ ورودی مسئله (زمان معقول)
== مفهوم و مقایسهٔ آن با ان پی-کامل ==
مسئلهٔ H '''ان پی-سخت''' است اگر و فقط اگر مسئلهٔ L از نوع [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] موجود باشد ٫
مسائل ان پی-سخت ممکن است از هر نوعی باشند:[[مسئله تصمیم|مسائل تصمیم گیری]]٫[[ویکی‌پدیا:search problems|مسائل جستجو]]٫[[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]].
طبق روال تعریف: (توجه داشته باشید که اینها صرفاً ادعا هستند نه تعریف):
* مسئلهٔ H حداقل به سختی مسئلهٔ L است. چون H
* چون L [[ویکی‌پدیا:NP-compelete|ان پی-کامل]] است ٫بنابراین به سختی مسائل نوع '''ان پی '''است. مسئلهٔ H حداقل به سختی مسئلهٔ '''ان پی''' است.اما H نباید '''ان پی''' باشد و بنابراین نباید از نوع [[مسئله تصمیم|مسائل تصمیم گیری]] باشد(حتی اگر از نوع مسایل
* مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با زمان زیاد با ۱ واحد کاهش به یکدیگر تبدیل
همهٔ مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با کاهش H میتوانند در زمان زیاد حل شوند.بنابراین همهٔ مسائل در '''ان پی''' قابل کاهش به H هستند.توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:
# از [[ویکی‌پدیا:NP-complete|'''ان پی-کامل:''']][[مسئله تصمیم|مسائل تصمیم گیری]] به مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با تحولات چندجمله‌ای
خط ۱۸:
* اگر یک [[الگوریتم]] چندجمله‌ای برای هر مسئلهٔ ان پی-سخت موجود باشد٫ سپس [[الگوریتم]]های چندجمله‌ای برای همهٔ مسائل در '''ان پی '''وجود دارند و بنابراین [[مسئله برابری پی و ان‌پی]]
* اگر P ≠ NP باشد ٫ مسائل ان پی-سخت راه حلی در زمان‌های زیاد ندارند.زمانی که [[مسئله برابری پی و ان‌پی]] باشد ٫ مسائل حل نمی‌شوند.حتی اگر مسائل ان پی-سخت بتوانند در زمان زیاد حل شوند.
* اگر [[ویکی‌پدیا:optimization problems|مسائل بهینه سازی]] ٫H یک نسخهٔ
* یک اشتباه رایج این است که فکر
== روش حل مسایل ان پی-سخت ==
روش‌های مختلفی برای حل سریع ولی نزدیک به بهینه برای یک مسئلهٔ ان پی-سخت وجود دارد:
* '''راه حل تقریبی قابل اثبات'''('''[[الگوریتم‌های تقریبی]]'''):که در آن یک الگوریتم سریع برای حل مسئله ارائه می‌شود ولی اثبات می‌شود که اندازهٔ خروجی ضریبی از اندازهٔ خروجی بهینهٔ مسئله‌است.
* '''[[الگوریتم مکاشفه‌ای|الگوریتم‌های مکاشفه‌ای]]''':با این که الگوریتم‌هایی سریع هستند و به صورت تقریبی جواب را به دست می‌آورند٫اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد.بسیاری از این الگوریتم‌ها به صورت تجربی آزمایش
=== الگوریتم‌ها ===
راه‌های معمول مقابله با چنین مسائلی عبارتند از:
* طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از
* استفاده از «الگوریتم‌های مکاشفه‌ای»([[ویکی‌پدیا:Heuristic|Heuristic]]) که جواب‌هایی به‌دست می‌دهد که احتمالاً درست هستند.
* پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
| |||