Метод гілок і меж (англ. Branch-and-Bound) — один з поширених методів дискретної оптимізації. Метод працює на (дереві рішень) та визначає принципи роботи конкретних алгоритмів пошуку розв'язків, тобто, є мета-алгоритмом. Для різних задач комбінаторної оптимізації створюють спеціалізовані алгоритми гілок та меж.
Ідею методу було вперше сформульовано A.H. Land та A.G. Doig (1960) в галузі дослідження операцій. R.J. Dakin (1965) розробив простий для впровадження алгоритм.
Алгоритм
Результатом роботи алгоритму є знаходження максимуму функції на допустимій множині. При чому множина може бути як дискретною, так і раціональною. В ході роботи алгоритму виконується дві операції: розбиття вихідної множини на підмножини (гілки), та знаходження оцінок (меж). Існує оцінка множини згори та оцінка знизу. Оцінка згори — точка що гарантовано не менша за максимум на заданій підмножині. Оцінка знизу — точка що гарантовано не більша за мінімум на заданій підмножині. Множина що має найбільшу оцінку зверху зветься рекордною. На початку вся множина вважається рекордною.
- Рекордна множина розбивається на підмножини;
- Знайти оцінки згори та знизу для нових підмножин;
- Визначити максимальну оцінку знизу серед усіх підмножин;
- Видалити ті множини у яких оцінка зверху менша за максимальну оцінку знизу;
- Знайти максимальну оцінку згори серед усіх підмножин та вважати її рекордною;
- Якщо не досягнуто дискретності, або необхідної точності перейти по пункту 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
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет