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

حجم فایل : 2.4 MB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 41
راهبرد شاخه و حد (Branch and bound) 2 راهبرد شاخه و حد (Branch and bound) در رویکرد شاخه‌وحد نیز مانند رویکرد عقبگرد از ...
درخت فضای حالت استفاده می‌کنیم.
تفاوت این دو رویکرد در این است که:
(1) در شاخه‌وحد محدود نیستیم تا برای پیمایش درخت فضای حالت فقظ از پیمایش ...
Preorder استفاده کنیم. بلکه ...
می‌توانیم از هر نوع پیمایش سیستماتیک دیگر یا خلاقانه استفاده کنیم
(2) روش شاخه و حد فقط برای مسائل بهینه‌سازی مناسب است. 3 راهبرد شاخه و حد در این رویکرد برای هر گره در درخت فضای حالت، حد (bound) ای محاسبه می‌شود تا
مشخص شود که آن گره امیدبخش است یا خیر.
bound هر گره بیانگر حدی از مقدارهای m(x,y) است که با گسترش آن گره به دست می‌آید.
اگر bound از بهترین m(x,y) ای که تاکنون بدست آمده‌است بهتر نباشد در این صورت ...
گره امیدبخش نیست ودرغیراینصورت
امیدبخش است. 4 راهبرد شاخه و حد با این توضیحات الگوریتم عقبگرد ارائه شده برای مساله کوله‌پشتی صفرویک عملا الگوریتم ...
شاخه و حد است چراکه ...
در آن الگوریتم هم گره امیدبخش نبود چنانچه bound از maxprofitای که تا آن زمان بدست آمده بود بزرگتر نبود. 5 راهبرد شاخه و حد علاوه بر این رویکرد می‌توانیم رویکرد ساده‌تر «جستجوی سطح اول با هرس کردن شاخه و حد» را داشته باشیم. 6 راهبرد شاخه و حد رویکرد جستجوی سطح اول با هرس کردن شاخه و حد شامل:
1- ابتدا مشاهده ریشه
2- سپس تمامی گره‌های در سطح اول
3- سپس تمامی گره‌های در سطح دوم و ...
7 راهبرد شاخه و حد void breadth_first_branch_and_bound (state_space_tree T, number& best){
queue_of_node Q;
node u, v,
initialize (Q); // Initialize Q to be empty.
v = root of T; // Visit root.
enqueue (Q, v);
best = value (v);
while (! empty (Q)){
dequeue (Q, v);
for (each child u of v){ // Visit each child.
if (value (u) is better than best)
best = value (u);
if (bound (u) is better than best)
enqueue (Q, u);
}
}
} 8 راهبرد شاخه و حد مساله کوله‌پشتی زیر با n=4 و W=16 را درنظر بگیرید: 9 راهبرد شاخه و حد
















10 راهبرد شاخه و حد «جستجوی اولین-بهترین با هرس‌کردن شاخه و حد»
به صورت عمومی استراتژی جستجوی سطح اول مزیتی نسبت به رویکرد عقبگرد ندارد. چراکه ...
در آنجا درخت به صورت عمقی پیمایش می‌شد و در اینجا به صوت سطحی
جستجوی سطح اول می‌تواند با پیشنهاد‌ زیر زودتر پاسخ بهینه را پیدا کند:
بعد از آنکه تمامی فرزندان ی...