پاورپوینت تکنیک عقب گرد در طراحی الگوریتم (pptx) 26 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 26 اسلاید
قسمتی از متن PowerPoint (.pptx) :
1
طراحي الگوريتم ها
Computer algorithms
تکنیک عقبگرد (Back-Tracking)
2
فصل هفت
تکنیک عقبگرد در طراحی الگوریتم
3
Computer algorithms
مساله n وزیر
مساله حاصل جمع زیر مجموعه ها
مساله رنگ آمیزی گراف
مساله مدارهای همیلتونی
مساله کوله پشتی 0-1
4
Backtracking
فرض کنید شما میخواهید از میان تعدادی گزینه مجموعه ای از تصمیم ها را انتخاب کنید اما
شما اطلاعات کافی برای نحوه انتخاب ندارید
هر تصمیم خود منجر به مجموعه جدیدی از تصمیم ها می شود
عقبگرد روشی برای تست دنباله های مختلف است تا به راه حل برسید
5
از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که در این دنباله معیارهایی برآورده شود.
مفید برای حل مسائل تصمیم گیری(Decision Making)
مسائل تصمیم گیری جزء مسائلی هستند که پیچیدگی محاسباتی بالایی دارند (پیچیدگی نمایی – فاکتوریل دارند) از این لحاظ به مسائل NP-Complete معروف هستند(مسائلی که راه حل کارا(راه حل چندجمله ای) برای آنها یافت نشده است)
تکنیک عقبگرد یک جستجوی عمقی (depth -first) روی یک درخت است(پیمایش پیشوندی) که به این درخت درخت تصمیم(یا درخت فضای حالات) می گویند
یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.
6
در برخی از الگوریتم های عقبگرد می توان یک جواب را قبل از رسیدن به برگ درخت فضای حالات پیدا کرد
روش جستجوی عمقی
1
2
3
4
5
6
7
8
9
10
11
7
تعریف گره امیدبخش
یک گره را امیدبخش (promising) نامیم اگر به هنگام ملاقات گره مشخص شود که آن گره به جواب منتهی می شود
تعریف گره غیرامیدبخش
یک گره را غیر امیدبخش (non-promising) نامیم اگر به هنگام ملاقات گره مشخص شود که آن گره به جواب منتهی نمی شود
8
شمای کلی الگوریتم
آیا گره امیدبخش است؟
9
مساله 4 وزیر
16 * 15 * 14 * 13 =(16!/(16-4)!)
برای کاهش تعداد حالات فرض می کنیم که هر وزیر فقط در یک سطر می تواند باشد.
4*4*4*4=256
