دانلود مقاله الگوریتم های تقریبی و شناخت مسائل NP

.

فهرست مطالب :

فصل اول – الگوریتم های تقریبی و شناخت مسائل NP-HARD

مقدمه

۱- الگوریتم های تقریبی – مسائل NP-Hard

۱-۱ تعاریف رسمی

۱-۱-۱ تعریف بر پایهٔ بررسی کننده

۱-۱-۲ تعریف ماشینی

۱-۱-۳ برابری تعاریف

۱-۲ چرا بعضی از مسائل NP به سختی حل می شوند؟

۱-۳ رابطه با سایر کلاسها

۱-۳-۱ خصوصیات دیگر

۱-۴ روش‌های حل مسائل NP

۱-۴-۱ محدودسازی (restriction )

۱-۴-۲ تصادف سازی(Randomization)

۱-۴-۳ تقریب سازی(Approximation)

۱-۴-۴ مکاشفه ای(Heuristic)

۱-۴-۵ پارامتر سازی(Parameterization)

۱-۵ ان‌پی سخت NP-Hard

۱-۶ مفهوم و مقایسهٔ آن با ان پی-کامل

۱-۷ روش حل مسایل ان پی-سخت

۱-۸ الگوریتم‌ها

۱-۸ نمونه مسائل ان پی-سخت

۱-۸-۱ نظریه پیچیدگی محاسباتی

۱-۸-۲ آیا P=NP است؟

۱-۸-۳ پیچیدگی زمانی

۱-۹ معرفی Np کامل

۱-۱۰ بررسی ناکارآمد بودن زمانی

۱-۱۱ روش‌هایی برای حل مسائل NP-Complete

۱-۱۲ نمونه مساله

فصل دوم- طراحی یک الگوریتم فرا ابتکاری جدید بر اساس رفتار توابع ریاضی (xCos(x و tanh(x)

۲- مقدمه

۲-۱ الگوریتم های فرا ابتکاری

۲-۲ تولید جواب در فرا ابتکاری ها

۲-۳ توابع مورد استفاده در تولید جواب

۲-۳-۱ الف)xCos(x)

۲-۳-۲ ب)tanh(x)

۲-۴ معرفی الگوریتم پیشنهادی

۲-۵ آزمون عملکرد الگوریتم

۲-۶ نتیجه گیری و پیشنهادها

فصل سوم- روش حل TSP و جدول سودوکو از مسائل NP-Hard

۳-الگوریتم ژنتیک و حلّ مسألۀ فروشندۀ دوره‌گرد

۳-۱- حل مسأله TSP به وسیله الگوریتم ژنتیک

۳-۲- مقایسه روشهای مختلف الگوریتم و ژنتیک برای TSP

۳-۳- نتیجه گیری

۳-۴- حلّ مسأله معمای سودوکو

۳-۴-۱- حل مسأله

۳-۴-۲- تعیین کروموزم

۳-۴-۳- ساختن جمعیت آغازین یا نسل اول

۳-۴-۴- ساختن تابع از ارزش

۳-۴-۵- ترکیب نمونه‌ها و ساختن جواب جدید

۳-۴-۶- ارزشیابی مجموعه جواب

۳-۴-۷- ساختن نسل بعد

منابع و ماخذ

چکیده :

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

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

مقدمه
بسیاری از مسئله‌های معمول علوم کامپیوتر در حوزهٔ مسائل NP قرار دارند. مخصوصا مدل تصمیم گیری بسیاری از مسائل جستجو و بهینه سازی در حوزهٔ NP قرار دارد. نمونه هایی از زمینه هایی که شامل مسائل NP می شوند عبارتند از : مانند جبر بولی، گراف، طراحی شبکه، زیست شناسی، فیزیک جدید، نظریه اعداد، نظریه بازی ها و پازل‌ها، نظریه زبان‌ها و ماشین‌ها و .. .
یکی از ویژگی‌های مسائل NP آن است که یک الگوریتم ساده را (که ممکن است در نگاه اول بدیهی به نظر برسد) می‌توان برای یافتن راه‌حل‌های مفید به کار برد. اما بطور کلی، این روش، روش‌های ممکن زیادی را فراهم می‌کند و بررسی کردن تمام راه‌حل‌ها، فرآیند بسیار کندی خواهد بود.
امروزه، هیچکس نمی‌داند که آیا الگوریتم سریعتری برای یافتن جواب دقیق در مسائل NP وجود دارد یا خیر. و یافتن چنین الگوریتمی وظیفه مهمی است که به عهده محققان می‌باشد. امروزه اکثر مردم تصور می‌کنند که چنین الگوریتمی وجود ندارد و بنابراین به دنبال روش دیگری (جایگزین) هستند. و نمونه‌ای از روش جایگزین، الگوریتم ژنتیکی است.
۱- الگوریتم های تقریبی – مسائل NP-Hard
در نظریه پیچیدگی محاسباتی NPیکی از بنیادی‌ترین کلاس‌ها است. NP مخفف عبارت “non deterministic polynomial” است که به زمان اجرای آن اشاره دارد.
NP مجموعهٔ کلیه مسائل تصمیم گیری است که پیدا کردن جواب بله برای آنها شامل اثبات ساده ای است که جواب حقیقتاَ باید بله باشد. بطور دقیق تر این اثبات‌های ساده باید قابل بررسی در یک زمان اجرای چند جمله ای در یک ماشین تورینگ جبری باشد. در مقابل این تعریف NP مجموعه مسائل تصمیم گیری نامیده می‌شود که در یک زمان اجرای چند جمله ای در یک ماشین تورینگ غیر جبری قابل بررسی باشند. کلاس پیچیدگی P یکی از اعضای NP است اما NP شامل کلاس‌های مهم دیگری نیز هست. که پیچیده‌ترین آنها NP-Complete است بطوریکه برای آنها هیچ الگوریتم شناخته شده قابل اجرا در زمان چند جمله ای وجود ندارد .
مهمترین سوالی که اکنون برای این کلاسها در این نظریه وجود دارد این است که آیا P=NP ؟ این سوال می پرسد که آیا چنین الگوریتمی واقعا برای مسائل NP-Complete و در کل NP وجود دارد یا خیر. این باور گسترده وجود دارد که این تساوی نمی تواند درست باشد.

۱-۱ تعاریف رسمی
NP را می توان به وسیلهٔ NTIME نیز تعریف کرد:
(NP=∪NTIME(n^k

۱-۱-۱ تعریف بر پایهٔ بررسی کننده
به منظور تعریف این چنین NP بیایید مسئلهٔ مجموع زیر مجموعه‌ها را در نظر بگیرید . فرض کنید به ما تعدادی عدد صحیح داده شده است مثلا {-۷و-۳و-۲ ۵و ۸و} و ما میخواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه‌های آن صفر می‌شود یا نه؟ در این مثال جواب بله است زیرا اعداد -۳،-۲،۵ می توانند این شرط را بررسی کنند.
هنگامیکه مقدار اعداد صحیح ورودی زیاد شود تعداد زیر مجموعه‌ها بصورت توانی افزایش می یابد و در حقیقت مسئله فوق یک مسئله NP-Complete است.
در هر حال توجه شود که اگر به ما یک زیر مجموعه مشخص بدهند ( بعضی اوقات گواه نامیده می‌شود ) ما به راحتی می توانیم بررسی کنیم که آیا مجموع آن صفر است یا خیر . ( تنها با جمع کردن اعضای آن زیر مجموعه ) و اگر مجموع صفر باشد آن زیر مجموعه یک شاهد برای این است که جواب بله است. الگوریتمی که بررسی می‌کند آیادرزیر مجموعه داده شده مجموع اعضا صفر است بررسی کننده نامیده می شود.
یک مسئله را عضو NP می نامند اگر و فقط اگر یک بررسی کننده برای آن وجود داشته باشد که در زمان اجرای چند جمله ای اجرا شود.
در مورد مسئله مجموع زیر مجموعه‌ها نیز بررسی کننده تنها نیازمند زمان اجرای خطی است که این دلیلی است برای اینکه این مسئله NP است.
توجه شود که در تعریف بر پایهٔ بررسی کننده NP نیازمند یک بررسی کننده بعنوان گواه برای جواب نه نیست. آن کلاس مسائلی که شامل یک شاهد این چنینی هستند CO-NP نامیده می شود. در حقیقت یک سوال بدون جواب دیگری در اینجا وجود دارد که آیا تمام مسائل NP دارای یک گواه برای جواب نه هستند و در نتیجه CO-NP می شوند.
۱-۱-۲ تعریف ماشینی
معادل تعاریف قبلی این تعریف نیز وجود دارد که می گوید :
NP مجموعه مسائل تصمیم گیری است که قابل حل شدن در یک زمان اجرای چند جمله ای در یک ماشین تورینگ غیر جبری می باشد.
مثال در اینجا یک فهرست نا کامل از مسائل NP را بیان می کنیم: تمام مسائل P (برای یک گواه مسئله P ما می توانیم کلا گواه را نادیده بگیریم و مسئله را در زمان اجرای چند جمله ای حل کرد. همچنین توجه شود که یک ماشین تورینگ جبری یک ماشین تورینگغیر جبری است که از هیچ کدام از توانایی‌های غیر جبری اش استفاده نمی کند. مسئله پیدا کردن مقسوم علیه‌های یک عدد صحیح: دو عدد صحیح N و K داده شده اند.می خواهیم بدانیم آیا عدد صحیحی مثل F وجود دارد که ۱<F<K و N بر F بخش پذیر باشد. مسئله یکریختی دو گراف که یکریخت بودن دو گراف را بررسی می‌کند . حالت‌های متفاوت مسئله دست فروش دوره گرد که در آن میخواهیم بدانیم آیا مسیری هست که از تمام گره‌ها در یک شبکه عبور کند. مساله درستی منطقی که در آن می خواهیم بدانیم آیا یک فرمول منطقی در زبان منطق می تواند به ازای مقادیری از متغیرها راست باشد یا خیر.
۱-۱-۳ برابری تعاریف
دو تعریف برای NP یکی به عنوان مجموعه مسائلی که قابل حل با ماشین تورینگ غیر جبری در زمان اجرای چند جمله ای هستند و دیگری مجموعه مسائلی که دارای یک بررسی کننده با زمان اجرای چند جمله ای در یک ماشین تورینگ جبری هستند با هم معادلند. اثبات این برابری در بسیاری از کتاب‌ها آمده است بطور مثال در کتاب: Sipser’s Introduction to the theory of computation section ۷.۳ برای نشان دادن این ابتدا فکر کنیم که یک بررسی کننده جبری داریم یک ماشین تورینگ غیر جبری می تواند به راحتی بصورت غیر جبری بررسی کننده را بر روی تمام حالات ممکن از رشته‌ها بررسی کند.( این کار تنها نیازمند مراحل چند جمله گونه است زیرا این ماشین می تواند با حرکات غیر جبری کاراکتر بعدی را در رشتهٔ مورد نظر را در هر مرحله پیدا کند و طول رشتهٔ داده شده نیز باید محدود به چند جمله ای باشد.) اگر یکی از این رشته‌های بررسی کننده معتبر باشد بعضی از مسیرها مورد قبول واقع می شوند و اگر هیچ رشته ای معتبر نباشد رشته یک زبان به حساب نمی آید و پس داده می شود. از طرف دیگر فرض کنیم ما یک ماشین تورینگ غیر جبری به نام A داشته باشیم و یک زبان L به آن ارائه کنیم. در هر کدام از مراحل با شمار چندجمله ای این ماشین، شاخه‌های درخت محاسبه با یک عدد صحیح ثابت مشخص می شوند که نشان دهندهٔ جهت هاست. وجود حداقل یک راه درست الزامی است و رشته ای که این مسیر را مشخص می‌کند گواهی برای بررسی کننده است. پس از آن اثبات کننده می تواند بصورت جبری A را بصورت عبور از مسیر پذیرفته شده و بررسی اینکه ار آخر نیز پذیرفته می‌شود پیاده سازی کند. اگر A داده را قبول نکند هیچ راه پذیرفته شده ای وجود ندارد و بررسی کننده هیچ گاه به جواب بله نمی رسد.
۱-۲ چرا بعضی از مسائل NP به سختی حل می شوند؟
به این علت که بسیاری مسئلهٔ مهم در این کلاس وجود دارد تلاش‌های فراوانی برای پیدا کردن الگوریتم هایی با زمان اجرای چند جمله ای برای مسائل NP صورت گرفته است. با این وجود باز هم مسائلی از NP باقی می مانند که در برابر این تلاشها مقاومت می کنندو به نظر می رسد که نیازمند زمان اجرای فراتر از چند جمله ای هستند. اینکه آیا این مسائل اصلا قابل بررسی در زمان اجرای چند جمله ای هستند یا خیر از بزرگترین مسائل در علم کامپیوتر است. ( به مسئله P=NP مراجعه شود) یکی از مفاهیم مهم در این مبحث مجموعه مسائل NP-Complete است که زیر مجموعهٔ NP به شمار می آید و به صورت غیر رسمی تر می تواند بعنوان سخت‌ترین مسائل NP به شمار بیایند. اگر یک الگوریتم زمان اجرای چند جمله ای حتی برای یکی از این مسائل پیدا شود آنگاه برای تمام این مسائل الگوریتمی با زمان اجرای چند جمله ای پیدا خواهد شد. بنا بر این علت و همچنین این علت که تا کنون تمامی تحقیقات برای بدست آوردن چنین الگوریتمی برای هر یک از این مسائل به شکست منجر شده است، هنگامیکه ثابت می‌شود مسئله ای NP-Complete است پیدا شدن الگوریتمی با زمان اجرای چند جمله ای برای آن بعید به نظر می رسد.
۱-۳ رابطه با سایر کلاسها
NP شامل تمام مسائل P می‌شود زیرا هر کس می تواند با نادیده گرفتن شواهد حل مسئله هر نمونه از این مسائل را حل کند. NP در PSPACE موجود است. برای نشان دادن این کافی است یک ماشین PSPACE درست کنیم که بر روی تمام رشته‌های گواه گردش کند و هر کدام را به یک بررسی کننده زمان اجرای چند جمله ای ارائه دهد. از آنجا که این ماشین تنها می تواند بیت هایی با تعداد چند جمله ای را بخواند نمی تواند در فضاهایی فراتر از چند جمله ای به کار رود و نمی تواند بررسی کننده ای را بپذیرد که زمان اجرایی فراتر از چند جمله ای نیاز دارد ( بنابر این ما نیازی نداریم تا گواه هایی را بررسی کنیم که زمان اجرای طولانی تری دارند.) NP همچنین در مجموعه EXPTIME موجود است. به این علت که الگوریتمیکسانی برای آن در زمان اجرای توانی موجود است. CO-NP شامل آن سری مسائلی است که گواه‌های ساده ای برای نادرست بودن دارند که بعضی اوقات مثال نقض نامیده می شود. برای مثال تست اول بودن یک عدد صحیح در حوزهٔ CO-NP قرار می گیرد زیرا می توان غیر اول بودن یک عدد را به راحتی با پیدا کردن یک عامل آن مشخص کرد . NP و CO-NP در کنار هم در اولین سطح بالای P درسلسله مراتب چند جمله ای‌ها قرار دارند. NP تنها برای ماشین‌های جبری تعریف می شود. اگر ما به بررسی کننده توانایی احتمالی بودن را نسبت دهیم ( بطور خاص ماشین BPP ) به کلاس MA می رسیم که قابل حل با قراداد آرتور- مرلین بدون برقراری ارتباط بین آرتور و مرلین است. NP کلاس مسائل تصمیم گیری است کلاس مشابه آن برای راهبرد کلاس توابع FNP است.

.

دانلود مقاله الگوریتم های تقریبی و شناخت مسائل NP

.

(فایل کامل این پروژه ۷۰ (هفتاد) صفحه word همراه با منابع و ماخذ می باشد.)

در تمامی ساعات شبانه روز >> پرداخت آنلاین و دانلود آنی فایل پس از پرداخت.