Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Метод гілок і меж англ Branch and Bound один з поширених методів дискретної оптимізації Метод працює на дереві рішень та

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

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

Метод гілок і меж (англ. 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

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Metod gilok i mezh angl Branch and Bound odin z poshirenih metodiv diskretnoyi optimizaciyi Metod pracyuye na derevi rishen ta viznachaye principi roboti konkretnih algoritmiv poshuku rozv yazkiv tobto ye meta algoritmom Dlya riznih zadach kombinatornoyi optimizaciyi stvoryuyut specializovani algoritmi gilok ta mezh Ideyu metodu bulo vpershe sformulovano A H Land ta A G Doig 1960 v galuzi doslidzhennya operacij R J Dakin 1965 rozrobiv prostij dlya vprovadzhennya algoritm AlgoritmRezultatom roboti algoritmu ye znahodzhennya maksimumu funkciyi na dopustimij mnozhini Pri chomu mnozhina mozhe buti yak diskretnoyu tak i racionalnoyu V hodi roboti algoritmu vikonuyetsya dvi operaciyi rozbittya vihidnoyi mnozhini na pidmnozhini gilki ta znahodzhennya ocinok mezh Isnuye ocinka mnozhini zgori ta ocinka znizu Ocinka zgori tochka sho garantovano ne mensha za maksimum na zadanij pidmnozhini Ocinka znizu tochka sho garantovano ne bilsha za minimum na zadanij pidmnozhini Mnozhina sho maye najbilshu ocinku zverhu zvetsya rekordnoyu Na pochatku vsya mnozhina vvazhayetsya rekordnoyu Rekordna mnozhina rozbivayetsya na pidmnozhini Znajti ocinki zgori ta znizu dlya novih pidmnozhin Viznachiti maksimalnu ocinku znizu sered usih pidmnozhin Vidaliti ti mnozhini u yakih ocinka zverhu mensha za maksimalnu ocinku znizu Znajti maksimalnu ocinku zgori sered usih pidmnozhin ta vvazhati yiyi rekordnoyu Yaksho ne dosyagnuto diskretnosti abo neobhidnoyi tochnosti perejti po punktu 1 Rezultatom roboti ye znachennya mizh ocinkoyu zgori ta znizu dlya rekordnoyi mnozhini Tochnistyu ye riznicya mizh verhnoyu ta nizhnoyu ocinkami tobto dlya diskretnih mnozhin algoritm zavershenij todi koli ci ocinki zbigayutsya ZastosuvannyaMetod vikoristovuyetsya dlya virishennya deyakih NP povnih zadach Shvidkist algoritmu zalezhit vid viglyadu funkciyi ta sposobu viznachennya ocinok ale garantovano ne bilshe za povnij perebir PosilannyaDakin 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

Дата публікації:
Топ