لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : 
.ppt ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 8 اسلاید
قسمتی از متن .ppt :
Backtracking
1
Backtracking بازگشت به عقب
Backtracking
2
ویژگیها
ابتدا در سال 1950 توسط D.H. Lehmer ابداع شد و R. J. Walker در 1960 یک محاسبه الگوریتمی برای آن انجام داد.
اغلب مسائلی که با این روش حل می شوند از نوعی هستند که از اصول, مفاهیم, نمایش, پیمایش و جستجوی درختها استفاده می کنند.
این روش به صورت یک جستجوی عمقی روی درخت عمل می کند.
برای حل اغلب مسائلی که به دنبال یک دسته جواب یا یک جواب بهینه در شرایط خاص هستند قابل استفاده است.
چنانچه در مرحله ای از الگوریتم کلیه انتخابهای ممکن بررسی گردد و هیچ کدام قابل قبول نباشد باید تصمیم مرحله قبل را تغییر داد. یعنی باید از سطح جاری درخت تصمیم به سطح قبل بازگشت.
Backtracking
3
چنانچه مسأله بیش از یک جواب داشته باشد همه جوابها را پیدا می کنیم.
مرتبه زمانی نامعقول. در مسائل تصمیم گیری مجموعه انتخابها و یا تصمیم های ممکن بسیار بزرگ است و به صورت چند جمله ای نمی باشد (2n, n!,…). روش بازگشت به عقب مرتبه زمانی را کاهش نمی دهد ولی حالتهای مورد بررسی را کاهش می دهد.
گره وعده گاه (promising): اگر به هنگام ملاقات گره مشخص شود که احتمالا آن گره به جواب منجر می شود.
ویژگیها (ادامه)
Backtracking
4
مثال: مسأله n-وزیر
هدف قرار دادن n وزیر در یک صفحه شطرنج n×n است به طوری که هیچ دو وزیری یکدیگر را تهدید نکنند. برای مثال می توان مسأله 4 وزیر را درنظر گرفت.
هیچ دو وزیری نمی توانند در یک سطر باشند. می توان هر وزیر را در هریک از چهار ستون صفحه قرار داد: 256=4×4×4×4 حالت
پاورپوینت درمورد Backtracking بازگشت به عقب
