Метод гілок і меж

Алгоритми пошуку графами та деревами
α–β A* B* Бахромовий Беллмана — Форда Британського музею Борувки В глибину В ширину Гілок та меж D* Двоспрямований Дейкстри Джонсона Едмондса З вертанням зворотний перехід З ітеративним заглибленням З обмеженням глибини IDA* Крускала Лексикографічний у ширину На стрибкових точках Перший-найліпший Прима Променевий SMA* Сходження на вершину Флойда — Воршелла
Переліки
Алгоритми на графах Алгоритми пошуку Список алгоритмів на графах
Пов'язані теми
Динамічне програмування Пошукова гра Пошук по графу Обхід дерева

Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на дереві рішень та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж.

Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм.

Алгоритм

Результатом роботи алгоритму є знаходження максимуму функції на допустимій множині. При чому множина може бути як дискретною, так і раціональною. В ході роботи алгоритму виконується дві операції: розбиття вихідної множини на підмножини (гілки), та знаходження оцінок (меж). Існує оцінка множини згори та оцінка знизу. Оцінка згори — точка що гарантовано не менша за максимум на заданій підмножині. Оцінка знизу — точка що гарантовано не більша за мінімум на заданій підмножині. Множина що має найбільшу оцінку зверху зветься рекордною. На початку вся множина вважається рекордною.

1. Рекордна множина розбивається на підмножини;
2. Знайти оцінки згори та знизу для нових підмножин;
3. Визначити максимальну оцінку знизу серед усіх підмножин;
4. Видалити ті множини у яких оцінка зверху менша за максимальну оцінку знизу;
5. Знайти максимальну оцінку згори серед усіх підмножин та вважати її рекордною;
6. Якщо не досягнуто дискретності, або необхідної точності перейти по пункту 1;

Результатом роботи є значення між оцінкою згори та знизу для рекордної множини. Точністю є різниця між верхньою та нижньою оцінками, тобто для дискретних множин алгоритм завершений тоді, коли ці оцінки збігаються.

Застосування

Метод використовується для вирішення деяких NP-повних задач. Швидкість алгоритму залежить від вигляду функції та способу визначення оцінок, але гарантовано не більше за повний перебір.

Посилання

• Dakin, R. J. (1965). A tree-search algorithm for mixed integer programming problems. In: The Computer Journal, Volume 8, S. 250—255 online
• Land, A. H. und A. G. Doig (1960). An automatic method of solving discrete programming problems. In: Econometrica 28, S. 497—520 online
• http://boris.cdu.edu.ua/download/compmat3_2005.pdf