دانلود پاورپوینت انشعاب وتحديد

بنام خدا 1 انشعاب وتحديد ‏Branch & Bound 2 تفاوتها و شباهتهای دو روش بازگشت به عقب و انشعاب و تحدید روش پیمایش درخت (گراف) .I اص#وال دو روش جس#تجوی اص#لی ب#رای پیم#ایش گرافه#ا در ح#الت کلی وج#ود دارد : ‏ جستجو در پهنا با جستجوی ردیفی ( سطحی )(Breadth First )Search ‏ جستجو در عمق یا جستجوی عمقی ()Depth First Search ‏ الگ#وی جس#تجو ب#رای روش بازگش#ت ب#ه عقب ( عقبگ#رد ) ب#ه ص#ورت ی باش#د .ام#ا د#ر روش #انش#ع#اب و تح#دی#د ی#کی از# عم#ق م # جس#تج#و در # # روش#های جس#تجوی درخت ،جس#تجو ب#ه ت#رتیب پهن#ا ( س#طحی ) می باشد . ‏ به روش جس#تجو ب#ه روش س#طحی اص#طالحا جس#تجوی FIFO ک ور#یتم #از #ی# # ن ورودی# #- #اولی#ن #خ#روجی )# #ن#یز گو##ین#د . #د #ر ا#ین #الگ# # ( ا#ولی # ه #م#ی #ش#و#د # ،##ه#ر #ن#ود#ی #ک#ه# #پیم#ای#ش#م#ی #ش#و# #د ،د#ر##ص#ورت# ف ##اس#ت#فاد # ص# # می شود . دارا بودن شرایط مورد نظر ،به انتهای صف افزوده 4 مثال ي#ك درخت ب#ا گ#ره ه#اي ش#ماره گ#ذاري ش#ده ب#ر اس#اس ي#ك جستجوي عمقي . 1 2 3 7 13 4 6 12 17 5 11 16 4 10 9 15 8 14  در اینج#ا ش#کل 2 -را ک#ه در مبحث ب#از گش#ت ب#ه عقب مط#رح ش#د ، به روش سطحی پیمایش می aکنیم ( .یافتن عنصر ) k ‏d ‏r ‏c ‏s ‏b ‏k ‏h ‏u ‏find ‏g ‏f ‏t ‏e ‏m ‏n شکل 2 - صف k : 5 ‏h ‏g ‏f ‏e ‏d ‏c ‏b ‏a تفاوتها و شباهتهای دو روش بازگشت به عقب و انشعاب و تحدید .II ‏ ‏ ‏ ‏ ‏ 7 هرس کردن شاخه ها در ه#ر دوروش س#عی می ش#ود ش#اخه ه#ایی از درخت ه#رس ش#ود .در ا#ینص#ورت تع#دا#د ح#االت ایج#اد ش#ده ک#اهش #یافت#ه و در ن#تیج#ه زم#ان #الزم برای اجرای الگوریتم کاهش می یابد . ‏ گرچ#ه این ک#ار مرتب#ه زم#انی را ب#ه ح#د قاب#ل قب#ولی ک#اهش نمی ده#د ، #ام#ا #ب#ر#ای #تع#دا#د دا#ده ه#ای #ک#م #زم#ا#ن #اج#ر#ا# #را #ب#ه #ح#د# #ق#اب#ل# #قب#و#ل#ی ک#اهش می دهد . در روش بازگش#ت ب#ه عقب امک#ان تغی#یر ت#رتیب بررس#ی گ#ره ه#ا پیش بی#نی ن#ش#ده #اس#ت #،ام#ا در #روش انش#عاب#و تحدی#د ای#ن امک#ان #وج#ود دارد . در ب#رخی مس#ائل ،ب#ا انج#ام محاس#بات اض#افی می ت#وان م#یزان امی#د ب#رای رسیدن به جواب را در هر شاخه برآورد کرد . مس#اله ای ک#ه ب#ه روش بازگش#ت ب#ه عقب ح#ل می گ#ردد می توان#د بیش از ی ا#مت#ی#از#ی ن#دا#رد# #.ا#م#ا در# چ ج#و#اب #ب#ر #د#یگ#ر # د و ه#ی# # ی#ک #ج#واب #داش#ت#ه #باش# # اغ#لب مس#ا#ئلی #ک#ه #ب#ه ر#و#ش #انش#عاب و# #تح#دی#د ح#ل #می #ش#و#ند #مهم #ی#ا#فتن جواب بهینه است . همانن#دالگوریتم عقبگ#رد ،زم#ان الگوریتمه#ای انش#عاب و تحدی#د ن#یز معم#وال در بدترین حالت زمانی نمایی (یا بدتر) می باشد . مثال 1 حل مسئله فروشنده دوره گرد با استفاده از روش انشعاب و تحدید هدف :ی#افتن ی#ک دور کام#ل ب#ه گون#ه ای ک#ه از یکی از گ#ره ه#ا پیم#ایش آغ#از کرده و هر گره را تنها یک بار مالقات کنیم و به گره اولیه بر گردیم . فرض کنی#د می خ#واهیم مس#یری روی گ#راف داده ش#ده Gپی#دا ک#نیم ک#ه ماتریس وزن گراف Gبه صورت زیر 1 2 باشد 3 : 4 5 20 10 4 14 0 1 7 8 7 0 14 2 16 7 0 5 4 3 2 0 9 7 11 4 0 4 17 7 18 5 چون مس#یر بای#د کام#ل باش#د ،بای#د هم#ه گ#ره ه#ا را در برگ#یرد ،پس میت#وان هریک از گره ها را به عنوان نقطه شروع عملیات انتخاب کرد . 8 مثال 2 حل مس0ئله کول0ه پش0تی ص0فر و ی0ک ب0ا اس0تفاده از روش انشعاب و تحدید به ط#ور کلی ،روش جس#تجو عرض#ی مزی#تی ب#ر جس#تجوی عمقی (عقبگ#رد) ن#دارد .ام#ا می ت#وانیم جس#تجوی خ#ود را ب#ا اس#تفاده از ح#د ( )boundبهب#ود دهیم ت#ا عالوه ب#ر تع#یین امی#د بخش ب#ودن ی#ک گ#ره ، کار دیگری هم انجام دهد. ف#رض کنی#د چه#ار قطع#ه ب#ا وزن ه#ا و ارزش#های مش#خص بص#ورت زیر داریم و حداکثر تحمل کوله پشتی 16باشد یعنیw = 16 , : ‏n=4 ‏i ‏Pi ‏Wi ‏Pi/Wi #رتب ش#ده $40م #اس Pi/Wi $20اس مشخص#ات قطع#ات در ج#دول زی#ر ب#ر 1 2 اند : 9 $6 5 $30 2 $5 10 $50 3 $2 5 $10 4 تم#ام تع#اریفی ک#ه در ح#ل مس#ائل ب#ه روش عقبگ#رد داش#تیم ،تم#امی آنه#ا در روش انش#عاب و تحدی#د ن#یز معتبر می باشد . ‏تنها تفاوتی که وجود دارد نحوه پیمایش درخت است . ‏درخت فض#ای ح#الت ه#رس ش#ده ک#ه ب#ا اس#تفاده از جس#تجوی عرض#ی بدس#ت آم#ده اس#ت در ص#فحه بع#د نمایش داده شده است . 10 )0,0( $0 0 $115 )1,1( $40 2 $115 $40 Item 1 2 )2,1( Item 2 $30 5 10 $120 17 $20 $40 2 $98 )3,2( $70 7 $80 )4,1( Item 4 $10 5 $0 0 $82 $70 7 $115 )3,1( Item 3 $50 )1,2( $100 17 $0 )2,2( )3,4( )3,3( $40 2 $50 $90 12 $98 )4,2( $90 12 $90 11 الگوریتم بهترین جستجو با هرس کردن انشعاب وتحدید بای مسئله کوله پشتی صفر و یک Void Knapsack (int n , int p[ ] , int w[ ] ,int w , int & number) { priority - queue - of - node PQ ; node U,V ; initialize (PQ) ; V.level = V.profit = V.weight = 0 ; maxprofit = 0 ; V.bound = bound (V) ; insert (PQ,V) ; while ( ! Empty (PQ) ) { remove (PQ,V) ; if ( V.bound > maxprofit ) { 12 U.level = V.level + 1 ; U.weight = V.weight + w [U.level] ; U.profi = V.profit + p [U.level] ; if (U.weight <= W && U.profit > maxprofit) maxprofit = U.profit U.bound = bound (U) ; if ( U.bound > mazprofit) insert (PQ,U) ; U.weight = V.weight ; U.profi = V.profit ; U.bound = bound (U) ; if ( U.bound > mazprofit) insert (PQ,U) ; } } } 13 خالصه فصل فض#ای مس#ئله ای ک#ه ب#ا اس#تفاده از روش انش#عاب و تحدی#د ح#ل می ش#ود باید با یک گراف قابل نمایش باشد . الگ#وی جس#تجو در درخت ب#رای روش بازگش#ت ب#ه عقب روش جس#تجوی عم#قی اس#ت در #حال#یک#ه ب#رای رو#ش انش#عاب #و تحد#ی#د جس#تجوی رد#یفی #ی#ا جستجو در پهنا می باشد . برای روش انش#عاب و تحدی#د می ت#وان الگ#وریتم جس#تجوی بهین#ه ای بن#ام #س ور#یتم# #ب#ا ه#ر # و ب#ا ه#رس# #ک#ردن ا#نش#ع#اب و ت#حدی#د ا#رائ#ه دا#د .##این #ا#لگ# # جس#ت#ج # # ک#ردن#فضای ح#االت #تعداد#مقایسه ه#ا د #ر جستجو#را بهینه می #کند . در اغلب مس#ائلی ک#ه ب#ه روش انش#عاب و تحدی#د ح#ل می ش#وند ه#دف ی#افتن جواب بهینه است . همانن#د الگوریتمه#ای عقبگ#رد ،زم#ان الگوریتمه#ای انش#عاب و تحدی#د ن#یز در 14 بدترین حالت ،زمان نمایی یا بدتر می باشد .