پاورپوینت درس طراحی الگوریتم ها - فصل پنجم: راهبرد شاخه و حد

بخشی از پاورپوینت

اسلاید 1 :

راهبرد شاخه و حد
Branch & Bound approach

درس طراحی الگوریتم ها

اسلاید 2 :

مقدمه

الگوریتم شاخه و حد، شکل بهبود یافته ای از الگوریتم عقبگرد است.
راهبرد طراحی در شاخه و حد از آن جهت به عقبگرد شباهت دارد که در آن برای حل مسئله از درخت فضای حالت استفاده می شود.
مزایای راهبرد شاخه و حد نسبت به عقبگرد:
ما را به پیمایش خاصی از درخت محدود نمی کند.
فقط برای مسائل بهینه سازی به کار می رود.
الگوریتم شاخه و حد در هر گره از درخت فضای حالت، عددی (حدی) را محاسبه می کند تا تعیین شود که آیا آن گره امیدبخش است یا خیر.

اسلاید 3 :

مقدمه .

اگر آن حد بهتر از مقدار بهترین حلی که تاکنون پیدا شده، نباشد، گره غیر امیدبخش است.
در غیر اینصورت، امیدبخش می باشد.
علاوه بر استفاده از حدی برای تعیین امیدبخشی یک گره، می توان حدود گره های امید بخش را مقایسه نمود و فرزندان گرهی با بهترین حد را زودتر ملاقات کرد.
به روش فوق بهترین جستجو با هرس کردن شاخه و حد گفته می شود.
پیاده سازی این روش، شکل اصلاح شده ای از روش موسوم به جستجوی عرضی با هرس کردن شاخه و حد است.

اسلاید 4 :

جستجوی عرضی (اول سطح) درخت

در جستجوی عرضی، ابتدا ریشه ملاقات می شود و سپس همه فرزندان آن به ترتیب از چپ به راست به صورت سطحی ملاقات خواهند شد.

اسلاید 5 :

حل یک مسئله با رویکرد شاخه و حد

یک مسئله را با دو راهکار می توان به روش شاخه و حد حل نمود:
استفاده از جستجوی عرضی و در کنار آن هرس کردن درخت فضای حالت با شاخه و حد
استفاده از بهترین جستجو و هرس کردن با شاخه و حد

اسلاید 6 :

جستجوی عرضی با هرس کردن شاخه و حد

در این روش، کار از گره ریشه شروع شده و حد برای آن محاسبه می گردد.
تصمیم گیری درمورد اینکه آیا فرزندان یک گره ملاقات شوند، در هنگام ملاقات آن گره صورت می گیرد.
یعنی اگر گره جاری امیدبخش باشد، فرزندان آن باید بعداً به صورت اول سطح، ملاقات و بررسی شوند.
و اگر غیر امیدبخش باشد نیازی به ملاقات فرزندانش نیست.
تمام گره های داخل صف، ملاقات می شوند.
ملاقات گره ها تا جایی ادامه می یابد که دیگر گره امیدبخشی وجود نداشته باشد.

اسلاید 7 :

الگوریتم کلی جستجوی عرضی با هرس کردن شاخه و حد

اسلاید 8 :

بهترین جستجو با هرس کردن شاخه و حد

در این روش، کار از گره ریشه شروع شده و حد برای آن محاسبه می گردد.
تصمیم گیری درمورد اینکه آیا فرزندان یک گره ملاقات شوند، در هنگام ملاقات آن گره صورت می گیرد.
یعنی اگر گره جاری امیدبخش باشد، فرزندان آن باید در صف اولویت قرار گیرند که بعداً، ملاقات و بررسی شوند. (اولویت بر اساس مقدار حد گره)
و اگر غیر امیدبخش باشد نیازی به ملاقات فرزندانش نیست.
تمام گره های داخل صف اولویت قبل از ملاقات، بررسی می شوند که آیا امیدبخش هستند یا خیر. در صورت امید بخش بودن، ملاقات می شوند.
ملاقات گره ها تا جایی ادامه می یابد که دیگر گره امیدبخشی وجود نداشته باشد.

اسلاید 9 :

الگوریتم کلی بهترین جستجو با هرس کردن شاخه و حد

اسلاید 10 :

مسئله کوله پشتی صفر و یک

هدف دزد تعیین مجموعه ای از اشیاء است که ارزش کل آنها بیشینه باشد به طوری که وزن کل آنها از W بیشتر نشود.
ابتدا نسخه ساده ای از حل مسئله با استفاده از جستجوی عرضی با هرس کردن شاخه و حد ارائه می دهیم.
سپس شکل بهبود یافته آن را با روش بهترین جستجو با هرس کردن شاخه و حد بیان خواهیم کرد.

اسلاید 11 :

بررسی امید بخشی

اگر weight مجموع اوزان قطعات گنجانده شده تا گره i باشد:
در صورتی که weight ≥ W گره جاری غیر امیدبخش است.
می توان از شرایط روش حریصانه در کوله پشتی کسری برای تعیین حد بالای ارزش قابل حصول از هر گره، استفاده نمود:

قطعات براساس مقدار pi/wi به ترتیب نزولی مرتب می شوند.
در هر گره که باشیم، نمی توانیم با انتخاب قطعات بعدی بهره بیشتری از حالت کوله پشتی کسری بدست آوریم (bound).

اگر profit حاصلجمع ارزش قطعاتی باشد که تاکنون انتخاب شده اند.
به متغیرهای bound و totweight مقادیر اولیه profit و weight را می دهیم.
سپس به روش حریصانه قطعات باقیمانده را برداشته و ارزش آن را به bound و وزن آن را به totweight اضافه می کنیم تا به قطعه ای برسیم که اگر وزن آن را اضافه کنیم از W بیشتر شود.
کسری از آن قطعه را که باقیمانده وزن اجازه می دهد، برداشته و ارزش مقدار آن کسر را به bound اضافه می کنیم.

اسلاید 12 :

بررسی امید بخشی .

اگر گره در سطح i قرار داشته باشد و گره واقع در سطح k، شئیی است که حاصلجمع اوزان را از W بیشتر می کند:

اگر maxprofit مقدار بهره از بهترین حلی باشد که تاکنون پیدا شده است.
در این صورت اگر bound ≤ maxprofit، گره i غیر امیدبخش است.

اسلاید 13 :

مثال مسئله کوله پشتی (جستجوی عرضی)

اسلاید 14 :

درخت فضای حالت برای جستجوی عرضی هرس شده

اسلاید 15 :

ساختمان داده هر گره در درخت فضای حالت

برای حل مسئله کوله پشتی به روش جستجوی عرضی با هرس کردن شاخه و حد، هر گره از درخت را با ساختار زیر نگه می داریم:

اسلاید 16 :

الگوریتم جستجوی عرضی با هرس کردن شاخه و حد برای مسئله کوله پشتی صفرویک

اسلاید 17 :

محاسبه حد برای هر گره در کوله پشتی صفرو یک

اسلاید 18 :

مثال کوله پشتی صفرویک (بهترین جستجو)

در اینجا پس از ملاقات همه فرزندان یک گره مفروض، میتوانیم به همه گره های امید بخش و گسترش نیافته پرداخته و گره ای که بهترین حد را داراست گسترش دهیم.

اسلاید 19 :

1) گره (0,0)
Profit = 0$
Weight = 0
Maxprofit = 0$
totweight = 0+2+5 = 7
Bound = 0 + 40 + 30 + (16-7)*5 = 115$
گره امید بخش است زیرا: (weight<16) and (bound > maxprofit)