دانلود مقالات ISI درباره روش انشعاب و حد، الگوریتم شاخه و حد + ترجمه فارسی

روش انشعاب و حد یک الگو طراحی الگوریتم برای مسائل بهینه سازی است. این روش در یک جستوجوی فضای حالات جواب های احتمالی مسئله را پیمایش می‌کند. در اینجا مجموعه‌ی جواب های احتمالی به صورت یک درخت در نظر گرفته می‌شود که ریشه‌ی آن متناظر با همه‌ی جواب‌ها و انشعابات آن زیر مجموعه‌هایی از جواب های احتمالی اند، قبل از پیمایش مجموعه جواب های یک زیر شاخه،الگوریتم مجموعه جواب های شاخه را با کران پایین و بالای جواب مسئله‌ی بهینه سازی به طور کلی چک می‌کند و درصورتی که زیر شاخه توانایی تولید جواب بهینه‌تر برای مسئله را نداشته باشد،از پیمایش کل زیر شاخه صرف نظر می‌شود. ویژگی‌های روش: برای حل مسائل بهینه سازی‌ای که الگوریتمی با زمان چند جمله ای برای آن ها پیدا نشده است،از الگوریتم هایی با پیچیدگی نمایی که زمان اجرای پایینی دارند استفاده می‌شود، روش انشعاب و حد در این سبک مسائل گزینه‌ی مناسبی است. ایده کلیدی الگوریتم شاخه و حد این است: درصورتی که حد پایین برای بعضی گره‌های درخت (مجموعه‌ای از راه حل‌های پیشنهادی) A بزرگتر از دیگر گره‌ها B است، در آن صورت با اطمینان می‌تواند A از جستجو دور انداخته شود. این مرحله هرس کردن نام دارد و معمولاً با متغیر جهانی m (مشترک در میان تمام گره‌ها از درخت) پیاده سازی می‌شود، که حداقل حد بالایی که تاکنون دیده شده در میان تمام حاشیه‌ها را ثبت می‌کند. هر گره کران پایین که بزرگتر از m است می‌تواند دور انداخته شود. کاربرد: این رویکرد برای حل تعدادی از مسائل NP سخت استفاده می‌شود. از قبیل: مسئله کوله پشتی، برنامه ریزی، عددصحیح، برنامه ریزی غیر خطی، مسئله فروشنده دوره‌گرد، مشکل تخصیص درجه دوم،Maximum satisfiability problem، جستجو نزدیکترین همسایه، مسئله برش موجودی، تجزیه و تحلیل نویزهای اشتباه. می‌توان در شاخه و حد ابتکارات مختلفی بکار برد. برای مثال، ممکن است کسی بخواهد مرحله شاخه کردن را زمانی که شکاف بین حد پایین و بالا به کوچکتر از یک آستانه شد، پایان دهد. این هنگامی استفاده می‌شود که راه حل به اندازه کافی برای اهداف کاربردی خوب باشد و می‌تواند محاسبات لازم را تا حد زیادی کاهش دهد. این نوع راه حل قابل اجرا است بخصوص زمانیکه تابع هزینه به کار رفته شلوغ یا حاصل برآورد آماری باشد، و همچنین دقیقاً شناخته نشده باشد، بلکه در طیف وسیعی از ارزش‌ها با احتمال خاص شناخته شده‌اند. نمونه‌ای از کاربرد آن در زیست شناسی است. هنگام انجام تجزیه و تحلیل برای ارزیابی روابط تکاملی بین موجودات، که اغلب در آن مجموعه داده‌های غیرعملی بزرگی هستند. به همین دلیل روش شاخه و حد اغلب در الگوریتم درخت جستجو در بازی استفاده می‌شود که مهمترین آنها در هرس آلفا-بتا استفاده می‌شود.