پاورپوینت Backtracking بازگشت به عقب

پاورپوینت Backtracking بازگشت به عقب

پاورپوینت  Backtracking بازگشت به عقب دارای 8 اسلاید با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید.

ویژگیها

ابتدا در سال 1950 توسط D.H. Lehmer  ابداع شد و R. J. Walker در 1960 یک محاسبه الگوریتمی برای آن انجام داد. 

اغلب مسائلی که با این روش حل می شوند از نوعی هستند که از اصول, مفاهیم, نمایش, پیمایش و جستجوی درختها استفاده می کنند. 

این روش به صورت یک جستجوی عمقی روی درخت عمل می کند.

برای حل اغلب مسائلی که به دنبال یک دسته جواب یا یک جواب بهینه در  شرایط خاص هستند قابل استفاده است.

چنانچه در مرحله ای از الگوریتم کلیه انتخابهای ممکن بررسی گردد و هیچ کدام قابل قبول نباشد باید تصمیم مرحله قبل را تغییر داد. یعنی باید از سطح جاری درخت تصمیم به سطح قبل بازگشت. 

چنانچه مسأله بیش از یک جواب داشته باشد همه جوابها را پیدا می کنیم.

مرتبه زمانی نامعقول. در مسائل تصمیم گیری مجموعه انتخابها و یا تصمیم های ممکن بسیار بزرگ است و به صورت چند جمله ای نمی باشد (2n, n!,…). روش بازگشت به عقب مرتبه زمانی را کاهش نمی دهد ولی حالتهای مورد بررسی را کاهش می دهد.

گره وعده گاه (promising): اگر به هنگام ملاقات گره مشخص شود که احتمالا آن گره به جواب منجر می شود.

مثال: مسأله n-وزیر

هدف قرار دادن n وزیر در یک صفحه شطرنج n×n است به طوری که هیچ دو وزیری یکدیگر را تهدید نکنند. برای مثال می توان مسأله 4 وزیر را درنظر گرفت.

هیچ دو وزیری نمی توانند در یک سطر باشند. می توان هر وزیر را در هریک از چهار ستون صفحه قرار داد: 256=4×4×4×4 حالت

تحلیل پیچیدگی زمانی

تعیین تعداد گره های بررسی شده:

    در سطح صفر: یک گره

    در سطح یک: n گره

    در سطح دو: n2 گره

    ...

    در سطح n: nn گره

T(n)=1+n2+n3+…+nn=

با توجه به این که هیچ دو وزیری در یک ستون قرار نمی گیرد:

T(n)=1+n+n×(n-1)+…+n!

تعداد واقعی از مقدار فوق هم کمتر است.

ppt: نوع فایل

سایز:18.5 KB 

تعداد اسلاید:8