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

محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش
جز تمیزکاری و اصلاح متن با استفاده از AWB
خط ۱۱:
طبق روال تعریف: (توجه داشته باشید که اینها صرفاً ادعا هستند نه تعریف):
* مسالهٔ H حداقل به سختی مسالهٔ L است. چون H میتواند برای حل L استفاده شود.
* چون L [[ویکی‌پدیا:NP-compelete |ان پی-کامل]] است ٫بنابراین به سختی مسائل نوع '''ان پی '''است. مسالهٔ H حداقل به سختی مسالهٔ '''ان پی''' است.اما H نباید '''ان پی''' باشد و بنابراین نباید از نوع [[مسئله تصمیم|مسائل تصمیم گیری]] باشد(حتی اگر از نوع مسایل تصمیم گیری باشد نیازی ندارد ازنوع مسائل '''ان پی''' باشد.)
* مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با زمان زیاد با ۱ واحد کاهش به یکدیگر تبدیل میشوند(همچنین تحولات چند جمله‌ای نیز نامیده میشوند.)
همهٔ مسائل [[ویکی‌پدیا:NP-complete|'''ان پی-کامل''']] با کاهش H میتوانند در زمان زیاد حل شوند.بنابراین همهٔ مسائل در '''ان پی''' قابل کاهش به H هستند.توجه داشته باشید هر چند این شامل ترکیب کردن ۲ تبدیل است:
خط ۲۹:
راه‌های معمول مقابله با چنین مسائلی عبارتند از:
* طراحی الگوریتم‌هایی برای پیدا کردن جواب‌های دقیق که استفاده از آنها فقط برای مسائل با اندازه کوچک صورت می‌گیرد.
* استفاده از «الگوریتم‌های مکاشفه‌ای»([[ویکی‌پدیا:Heuristic | Heuristic]]) که جواب‌هایی به‌دست می‌دهد که احتمالاً درست هستند.
* پیدا کردن زیرمسئله‌هایی از مسئله یعنی تقسیم مسئله به مسئله‌های کوچکتر تا بشود از الگوریتم‌های مکاشفه‌ای بهتر و دقیق‌تری ارائه کرد.
== نمونه مسائل ان پی-سخت ==
* [[مسئله فروشنده دوره‌گرد]]
* مسئله بزرگترین خوشه (پیدا کردن بزرگترین زیرگراف کامل) ([[:w:en:Maximum_clique_problemMaximum clique problem|maximum clique problem]])
== منابع ==
{{پانویس}}