پاورپوینت Backtracking بازگشت به عقب
| دسته بندی | علوم پایه |
| بازدید ها | 1 |
| فرمت فایل | ppt |
| حجم فایل | 18 کیلو بایت |
| تعداد صفحات فایل | 8 |
پاورپوینت 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
پاورپوینت مسأله کوله پشتی 1-0 با روش backtracking
| دسته بندی | علوم پایه |
| بازدید ها | 1 |
| فرمت فایل | ppt |
| حجم فایل | 18 کیلو بایت |
| تعداد صفحات فایل | 7 |
پاورپوینت مسأله کوله پشتی 1-0 با روش backtracking
پاورپوینت مسأله کوله پشتی 1-0 با روش backtracking دارای 7 اسلاید با ظاهری زیبا ، متفاوت ، مفید، مختصر و قابل ویرایش می باشد قسمتی از متن را ببینید و در صورت تمایل خرید کنید.
حل مسأله با استفاده از درخت فضای حالت
تا پایان جستجو امکان فهمیدن این که آیا یک گره جواب است یا خیر وجود ندارد.
باید بهینه سازی را درنظر داشت. اگر مجموع ارزش گره ها بیشتر از بهترین جوابی باشد که تا کنون به دست آورده ایم, مقدار بهترین جواب را به مقدار جدید تغییر می دهیم.
فرض: weight: مجموع وزن کالاهایی که تاکنون به گره ای اضافه شده اند.
profit : مجموع ارزش کالاهایی که تا گرعه جاری به حساب آمده اند.
bound: یک حد بالا برای ارزشی که می توانیم با بسط گره به آن برسیم.
totweight: حداکثر وزن کالاهای قابل انتخاب
maxprofit: مقدار ارزش بهترین جوابی که تا کنون پیدا شده.
کالاها را به صورت غیرنزولی بر اساس مقادیر pi / wi مرتب می کنیم.
گره سطح k : گرهی که موجب تجاوز مجموع وزن از مرز M می شود.
در سطح i پیش بینی از حداکثر ارزش قابل دستیابی, برابر با مجموع ارزش به دست آمده به علاوه ارزش کالاهای باقی مانده تا سطح k-1 به علاوه مقدار قابل انتخاب از کالای k ام (با فرض این که بتوان بخشی از آن را انتخاب کرد) می باشد.
bound ≤ maxprofit : گره غیر وعده گاه است.
الگوریتم مسأله کوله پشتی با روش backtracking
void knapsack(int i, int profit, int weight)
{ if weight <= M && profit > maxprofit)
{ maxprofit=profit;
numbest=i;
bestset=include;
}
if (promising (i))
{ include[i+1]=“yes”;
knapsack(i+1, profit+p[i+1],weight+w[i+1]);
include[i+1]=“no”;
knapsack(i+1, profit,weight);
}
ppt: نوع فایل
سایز:18.8 KB
تعداد اسلاید:7