دانلود فایل های دانشگاهی | ان‌پی-سخت – پایان نامه های کارشناسی ارشد |
 |
-
- الگوریتم ژنتیک[۲۳]
۲-۴-۱- الگوریتم
در علوم کامپیوتر و ریاضیات، یک الگوریتم جستجو، الگوریتمی است که یک مسأله را به عنوان ورودی می‌گیرد و بعد از ارزیابی کردن راه حل های ممکن، یک راه‌حل برای آن مسأله برمی‌گرداند. هنگامی که مسأله‌ای را حل می‌کنیم معمولاً دنبال آن هستیم که بهترین راه‌حل و یا به بیان دیگر به یک حلّ بهینه از بین حل‌های ممکن برای مسأله برسیم. به محدوده‌ای که جواب‌های مسأله قابل قبول می‌باشند به طوری که جواب بهینه هم یکی از زیرمجموعه‌های این محدوده است «فضای جستجو»[۲۴] نامیده می‌شود. هر نقطه از محدودۀ فضای جستجو نشان دهندۀ یکی از روش‌های حلّ مسأله می‌باشد و یا به بیانی ساده‌تر می‌توان گفت: مجموعۀ راه حل های ممکن برای یک مسأله را فضای جستجو می‌نامند.
مهمترین عامل در حل هر مسأله، جستجو به دنبال پاسخ‌های احتمالی مسئله است. به طور کلّی با دو دسته از الگوریتم‌ها مواجه هستیم؛ بعضی از الگوریتم‌ها که با عنوان الگوریتم‌های ناآگاهانه شناخته می‌شوند الگوریتم‌هایی هستند که از روش‌های ساده‌ای برای جستجوی فضای نمونه استفاده می‌کنند. در حالی که الگوریتم‌های آگاهانه با استفاده روش‌هایی مبتنی بر دانش در بارۀ ساختار فضای جستجو، می‌کوشند تا زمان جستجو را کاهش دهند. در کتاب «راسل» این الگوریتم‌ها به شکل زیر رده‌بندی شده‌اند:
- الگوریتم‌های ناآگاهانه ۲٫ الگوریتم‌های آگاهانه
۲-۴-۱-۱- الگوریتم‌های جستجوی ناآگاهانه
یک الگوریتم جستجوی ناآگاهانه الگوریتمی است که به ماهیّت مسأله کاری ندارد. از این‌رو می‌توانند به طور عمومی طراحی شوند و از همان طراحی برای محدودۀ عظیمی از مسائل استفاده کنند، این امر نیاز به طراحی انتزاعی دارد. از جمله مشکلاتی که این چنین الگوریتم‌هایی دارند این است که اغلب فضای جستجو بسیار بزرگ است و نیازمند زمان زیادی (حتی برای نمونه های کوچک) می‌باشد. از این‌رو برای بالا بردن سرعت پردازش غالبا از الگوریتم‌های آگاهانه استفاده می‌کنند.
جستجوی لیست
الگوریتم‌های جستجویِ لیست شاید از ابتدایی‌ترین انواع الگوریتم‌های جستجو باشند. هدف آن پیدا کردن یک عنصر از مجموعه‌ای از کلیدهاست(ممکن است شامل اطلاعات دیگری مرتبط با آن کلید نیز باشد). ساده‌ترین این الگوریتم‌ها، جستجوی خطّی است که هر عنصر از لیست را با عنصر مورد نظر مقایسه می‌کند. زمان اجرای این الگوریتم از O(n) است وقتی که n تعداد عناصر در لیست باشد. اما می‌توان از روش دیگری استفاده کرد که نیازی به جستجوی تمام لیست نباشد. جستجوی دودویی اندکی از جستجوی خطّی بهتر است. زمان اجرای آن از O(log n) است. این روش برای لیستی با تعداد دادۀ زیاد بسیار کارآمدتر از روش جستجوی خطّی است. اما در این روش لیست باید قبل از جستجو مرتب شده باشد. «جستجو با میان‌یابی» برای داده های مرتب شده با تعداد زیاد و توزیع یکنواخت، مناسب‌تر از جستجوی دودویی است. زمان اجرای آن به طور متوسّط O(log(log n)) است ولی بدترین زمان اجرای آن O(n) می‌باشد. الگوریتم «گراور»[۲۵]الگوریتم پلّه‌ای است که برای لیست‌های مرتب نشده استفاده می‌شود. الگوریتم Hash Table نیز برای جستجوی لیست به کار می‌رود. به طور متوسط زمان اجرای ثابتی دارد. اما نیاز به فضای اضافه داشته و بدترین زمان اجرای آن از O(n) است.
جستجوی درختی
الگوریتم‌های جستجوی درختی، قلب شیوه های جستجو برای داده های ساخت یافته هستند. مبنای اصلی جستجوی درختی، گره‌هایی است که از یک ساختمان داده گرفته شده‌اند. هر عنصر که بخواهد اضافه شود با داده های موجود در گره‌های درخت مقایسه می‌شود و به ساختار درخت اضافه می‌شود. با تغییر ترتیب داده ها و قرار دادن آنها در درخت، درخت با شیوه های مختلفی جستجو می‌شود.
جستجوی گراف
بسیاری از مسائل در نظریۀ گراف می‌تواند با الگوریتم‌های پیمایش درخت حل شوند، مثل الگوریتم دیکسترا[۲۶]، الگوریتم کروسکال[۲۷]، الگوریتم نزدیک‌ترین‌همسایه[۲۸] و الگوریتم پریم[۲۹]. می‌توان این الگوریتم‌ها را توسعه یافتۀ الگوریتم‌های جستجوی درختی دانست.
۲-۴-۱-۲- الگوریتم‌های جستجوی آگاهانه
در یک جستجوی آگاهانه، از نوع خاصی از مسائل به عنوان راهنما استفاده می‌شود. یک گونۀ خوب، یک جستجوی آگاهانه با کارایی قابل توجّهی نسبت به جستجوی ناآگاهانه به وجود می‌آورد. الگوریتم‌های برجستۀ کمی از جستجوی آگاهانۀ یک لیست وجود دارد. یکی از این الگوریتم‌هاHash Table با یک تابع Hash که بر مبنای نوع مسأله‌ای که دردست است می‌باشد. بیشتر الگوریتم‌های جستجوی آگاهانه، بسطی از درخت‌ها هستند. همانند الگوریتم‌های ناآگاهانه، این الگوریتم‌ها برای گراف‌ها نیز می‌توانند به کار روند.
دلیل نیاز به روش‌های جستجوی آگاهانه، نیاز به کاهش هزینۀ زمانی مورد نیاز برای حلّ مسأله است. در واقع به این دلیل که ما تمایل داریم مسائل را در زمان کمتری حل کرده و از بررسی تمام حالات ممکن اجتناب کنیم، می‌بایست روشی برای تشخیص کیفیت مسیر (حتی به شکل نسبی) داشته باشیم.
جستجوی خصمانه
در یک بازی مثل شطرنج، یک درخت بازی شامل تمام حرکات ممکن توسط هر دو بازیکن و نتایج حاصل از ترکیب این حرکات وجود دارد، و ما می‌توانیم این درخت را جستجو کرده و مؤثرترین استراتژی برای بازی را بیابیم. این چنین مسائلی دارای مشخصۀ منحصر به فردی هستند. برنامه های بازی‌های رایانه‌ای، و همچنین فرم‌های هوش مصنوعی مثل برنامه‌ریزی ماشین‌ها، اغلب از الگوریتم‌های جستجو مثل الگوریتم مین‌ماکس[۳۰] (می‌نیمیم مجموعه‌ای از ماکزیمم‌ها)، هرس کردن درخت جستجو و هرس کردن آلفا-بتا استفاده می‌کنند.
۲-۴-۲- مسائل NP-Hard
نمونه‌ای از مسائلی که نمی‌توان آنها را به روش سنتی حل کرد مسائل NP هستند. مجموعه «ان‌پی-سخت» شامل چندهزار مسألۀ مختلف با کاربردهای فراوان است که تاکنون برای آنها راه‌حلّ سریع و قابل انجام در زمان معقول پیدا نشده است و به احتمال زیاد در آینده نیز یافت نخواهد شد. این که راه‌حلّ سریعی برای آنها وجود ندارد هم اثبات شده‌است. البته ثابت شده است که اگر فقط برای یکی از این مسأله‌ها راه‌حل سریعی پیدا شود، این راه‌حل موجب حلّ سریع بقیۀ مسأله‌ها خواهد شد. البته احتمال پیدا شدن چنین الگوریتمی ضعیف است. منظور از راه‌حلّ سریع آن است که زمان اجرای آن با اندازۀ ورودی مسأله به صورت چندجمله‌ای رابطه داشته باشد.
روش‌های مختلفی برای حلّ سریع ولی نزدیک به بهینه برای یک مسألۀ NP-Hard وجود دارد :
-
- راه حلّ تقریبی قابل اثبات(الگوریتم‌های تقریبی): که در آن یک الگوریتم سریع برای حلّ مسأله ارائه می‌شود ولی اثبات می‌شود که اندازۀ خروجی ضریبی از اندازۀ خروجی بهینۀ مسأله است.
- الگوریتم‌های مکاشفه‌ای: با این که الگوریتم‌هایی سریع هستند و به صورت تقریبی جواب را به دست می‌آورند، اما در مورد ضریب تقریب یا میزان خوبی الگوریتم اثباتی وجود ندارد. بسیاری از این الگوریتم‌ها به صورت تجربی آزمایش می‌شوند. برخی از این الگوریتم‌ها از «روش حریصانه» برای حل استفاده می‌کنند.
راه‌های معمول مقابله با چنین مسائلی عبارتند از:
|
[جمعه 1401-09-25] [ 10:06:00 ق.ظ ]
|
