مرجع دانلود پاورپوینت های درسی

حجم فایل : 734.2 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 28
1 بنام خدا 2 طراحي الگوريتم ها 3

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