پاورپوینت انشعاب وتحديد (pptx) 13 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 13 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
1
انشعاب وتحديد Branch & Bound
2
تفاوتها و شباهتهای دو روش بازگشت به عقب و انشعاب و تحدید
روش پیمایش درخت (گراف)
اصولا دو روش جستجوی اصلی برای پیمایش گرافها در حالت کلی وجود دارد :
جستجو در پهنا با جستجوی ردیفی ( سطحی )(Breadth First Search)
جستجو در عمق یا جستجوی عمقی (Depth First Search)
الگوی جستجو برای روش بازگشت به عقب ( عقبگرد ) به صورت جستجو در عمق می باشد. اما در روش انشعاب و تحدید یکی از روشهای جستجوی درخت ، جستجو به ترتیب پهنا ( سطحی ) می باشد .
به روش جستجو به روش سطحی اصطلاحا جستجوی FIFO ( اولین ورودی - اولین خروجی ) نیز گویند . در این الگوریتم از یک صف استفاده می شود ، هر نودی که پیمایش می شود ، در صورت دارا بودن شرایط مورد نظر ، به انتهای صف افزوده می شود .
4
4
15
17
16
14
12
13
11
10
8
9
6
4
5
7
3
2
1
مثال
يك درخت با گره هاي شماره گذاري شده بر اساس يك جستجوي عمقي .
در اینجا شکل- 2 را که در مبحث باز گشت به عقب مطرح شد ، به روش سطحی پیمایش می کنیم . (یافتن عنصر k )
find
شکل - 2
a
b
c
d
k
h
u
t
f
g
e
n
m
r
s
صف :
b
c
d
e
f
g
h
k
a
5
هرس کردن شاخه ها
در هر دوروش سعی می شود شاخه هایی از درخت هرس شود .در اینصورت تعداد حالات ایجاد شده کاهش یافته و در نتیجه زمان لازم برای اجرای الگوریتم کاهش می یابد .
گرچه این کار مرتبه زمانی را به حد قابل قبولی کاهش نمی دهد ، اما برای تعداد داده های کم زمان اجرا را به حد قابل قبولی کاهش می دهد .
در روش بازگشت به عقب امکان تغییر ترتیب بررسی گره ها پیش بینی نشده است ، اما در روش انشعاب و تحدید این امکان وجود دارد .
در برخی مسائل ، با انجام محاسبات اضافی می توان میزان امید برای رسیدن به جواب را در هر شاخه برآورد کرد .
مساله ای که به روش بازگشت به عقب حل می گردد می تواند بیش از یک جواب داشته باشد و هیچ جواب بر دیگری امتیازی ندارد. اما در اغلب مسائلی که به روش انشعاب و تحدید حل می شوند مهم یافتن جواب بهینه است .
همانندالگوریتم عقبگرد ، زمان الگوریتمهای انشعاب و تحدید نیز معمولا در بدترین حالت زمانی نمایی (یا بدتر) می باشد .
7
تفاوتها و شباهتهای دو روش بازگشت به عقب و انشعاب و تحدید
مثال 1
حل مسئله فروشنده دوره گرد با استفاده از روش انشعاب و تحدید
هدف : یافتن یک دور کامل به گونه ای که از یکی از گره ها پیمایش آغاز کرده و هر گره را تنها یک بار ملاقات کنیم و به گره اولیه بر گردیم .
فرض کنید می خواهیم مسیری روی گراف داده شده G پیدا کنیم که ماتریس وزن گراف G به صورت زیر باشد :
چون مسیر باید کامل باشد، باید همه گره ها را در برگیرد ، پس میتوان هریک از گره ها را به عنوان نقطه شروع عملیات انتخاب کرد .
8
حل مسئله کوله پشتی صفر و یک با استفاده از روش انشعاب و تحدید
به طور کلی ، روش جستجو عرضی مزیتی بر جستجوی عمقی (عقبگرد) ندارد . اما می توانیم جستجوی خود را با استفاده از حد (bound) بهبود دهیم تا علاوه بر تعیین امید بخش بودن یک گره ، کار دیگری هم انجام دهد.
فرض کنید چهار قطعه با وزن ها و ارزشهای مشخص بصورت زیر داریم و حداکثر تحمل کوله پشتی 16 باشد یعنی:w = 16 , n = 4
مشخصات قطعات در جدول زیر بر اساس Pi/Wi مرتب شده اند :
مثال 2
9
تمام تعاریفی که در حل مسائل به روش عقبگرد داشتیم ، تمامی آنها در روش انشعاب و تحدید نیز معتبر می باشد .
تنها تفاوتی که وجود دارد نحوه پیمایش درخت است .
درخت فضای حالت هرس شده که با استفاده از جستجوی عرضی بدست آمده است در صفحه بعد نمایش داده شده است .
10