Метод гілок і меж: відмінності між версіями
[неперевірена версія] | [неперевірена версія] |
Vark (обговорення | внесок) доповнення, правопис |
Vark (обговорення | внесок) |
||
Рядок 24: | Рядок 24: | ||
* Dakin, R. J. (1965). ''A tree-search algorithm for mixed integer programming problems''. In: The Computer Journal, Volume 8, S. 250-255 [http://comjnl.oxfordjournals.org/cgi/content/abstract/8/3/250 online] |
* Dakin, R. J. (1965). ''A tree-search algorithm for mixed integer programming problems''. In: The Computer Journal, Volume 8, S. 250-255 [http://comjnl.oxfordjournals.org/cgi/content/abstract/8/3/250 online] |
||
* Land, A. H. und A. G. Doig (1960). ''An automatic method of solving discrete programming problems''. In: Econometrica 28, S. 497-520 [http://links.jstor.org/sici?sici=0012-9682%28196007%2928%3A3%3C497%3AAAMOSD%3E2.0.CO%3B2-M online] |
* Land, A. H. und A. G. Doig (1960). ''An automatic method of solving discrete programming problems''. In: Econometrica 28, S. 497-520 [http://links.jstor.org/sici?sici=0012-9682%28196007%2928%3A3%3C497%3AAAMOSD%3E2.0.CO%3B2-M online] |
||
* http://boris.cdu.edu.ua/download/compmat3_2005.pdf |
|||
Версія за 22:40, 6 березня 2013
Метод гілок і меж (англ. 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