پاورپوینت طراحی الگوريتم ها

نوع فایل: پاورپوینت

قابل ویرایش 26 اسلاید

مساله  n وزیر

مساله  حاصل جمع زیر مجموعه ها

مساله رنگ آمیزی گراف

مساله مدارهای همیلتونی

مساله کوله پشتی 0-1

فرض کنید شما میخواهید از میان تعدادی گزینه مجموعه ای  از تصمیم ها را انتخاب کنید اما

شما اطلاعات کافی برای نحوه انتخاب ندارید

هر تصمیم خود منجر به مجموعه جدیدی از تصمیم ها می شود

عقبگرد روشی برای تست دنباله های مختلف است تا به راه حل برسید

از تکنیک عقبگرد برای حل مسائلی استفاده می شود که در آن ها دنباله ای از اشیاء از یک مجموعه مشخص انتخاب می شود، به طوری که در این دنباله معیارهایی برآورده شود.

مفید برای حل مسائل تصمیم گیری(Decision Making)

مسائل تصمیم گیری جزء مسائلی هستند که پیچیدگی محاسباتی بالایی دارند (پیچیدگی نمایی – فاکتوریل دارند) از این لحاظ به مسائل NP-Complete معروف هستند(مسائلی که راه حل کارا(راه حل چندجمله ای) برای آنها یافت نشده است)

تکنیک عقبگرد یک جستجوی عمقی (depth -first) روی یک درخت است(پیمایش پیشوندی) که به این درخت درخت تصمیم(یا درخت فضای حالات) می گویند

یک مثال کلاسیک از عقبگرد، مسئله n وزیر است.