بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
در رویکرد شاخه‌وحد نیز مانند رویکرد عقبگرد از ...
درخت فضای حالت استفاده میکنیم.
تفاوت این دو رویکرد در این است که:
(1) در شاخه‌وحد محدود نیستیم تا برای پیمایش درخت فضای حالت فقظ از پیمایش ...
Preorder استفاده کنیم. بلکه ...
می‌توانیم از هر نوع پیمایش سیستماتیک دیگر یا خلاقانه استفاده کنیم
(2) روش شاخه و حد فقط برای مسائل بهینه‌سازی مناسب است.
اسلاید 2 :
راهبرد شاخه و حد
در این رویکرد برای هر گره در درخت فضای حالت، حد (bound) ای محاسبه می‌شود تا
مشخص شود که آن گره امیدبخش است یا خیر.
bound هر گره بیانگر حدی از مقدارهای m(x,y) است که با گسترش آن گره به دست می‌آید.
اگر bound از بهترین m(x,y) ای که تاکنون بدست آمده‌است بهتر نباشد در این صورت ...
گره امیدبخش نیست ودرغیراینصورت
امیدبخش است.
اسلاید 3 :
با این توضیحات الگوریتم عقبگرد ارائه شده برای مساله کوله‌پشتی صفرویک عملا الگوریتم ...
شاخه و حد است چراکه ...
در آن الگوریتم هم گره امیدبخش نبود چنانچه bound از maxprofitای که تا آن زمان بدست آمده بود بزرگتر نبود.
اسلاید 4 :
علاوه بر این رویکرد می‌توانیم رویکرد ساده‌تر «جستجوی سطح اول با هرس کردن شاخه و حد» را داشته باشیم.
اسلاید 5 :
رویکرد جستجوی سطح اول با هرس کردن شاخه و حد شامل:
1- ابتدا مشاهده ریشه
2- سپس تمامی گره‌های در سطح اول
3- سپس تمامی گره‌های در سطح دوم و ...
اسلاید 6 :
«جستجوی اولین-بهترین با هرس‌کردن شاخه و حد»
به صورت عمومی استراتژی جستجوی سطح اول مزیتی نسبت به رویکرد عقبگرد ندارد. چراکه ...
در آنجا درخت به صورت عمقی پیمایش می‌شد و در اینجا به صوت سطحی
جستجوی سطح اول می‌تواند با پیشنهاد زیر زودتر پاسخ بهینه را پیدا کند:
بعد از آنکه تمامی فرزندان یک گره مشاهد شد ...
به جای اینکه بیاییم و از اول صف گره بعدی را برداریم و فرزندان آن را مشاهده کنیم ...
بیاییم گره‌ی را از صف برداریم که دارای bound بزرگتری از بقیه باشد و فرزندان آن را مشاهده کنیم.
این رویکرد دارای سرعت همگرایی بیشتری نسبت به دو حالت قبل است.
اسلاید 7 :
void best_first_branch_and_bound(state_space_tree T,number& best){
priority_queue_of_node PQ;
node u, v;
initialize (PQ); // Initialize PQ to be empty.
v = root of T;
best = value(v);
insert (PQ, v);
while (! empty (PQ)) {
remove (PQ, v);
if (bound (v) is better than best)
for (each child u of v) { // promising.
if (value(u) is better than best)
(best = value (u);
if (bound (u) is better than best)
insert (PQ, u);
}
}
}
اسلاید 8 :
Traveling Salesperson Problem (TSP)
Goal:
find the shortest path in a …
directed graph that …
starts at a given vertex,
visits each vertex in the graph exactly once,
and ends up back at the starting vertex.
Such a path is called an optimal tour.
Because it does not matter where we start, the starting vertex can simply be the first vertex.
اسلاید 9 :
The adjacency matrix of a graph and
An optimal tour for that graph.
اسلاید 10 :
An obvious state space tree:
level1: each vertex other than the starting one
level2: each vertex other than the starting one and the one chosen at level 1
next levels: and so on.
