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