Вікіпедія

Метод гілок і меж: відмінності між версіями

Інтерактивний перегляд історії
[неперевірена версія][неперевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
доповнення
Vark (обговорення | внесок)
12 редагувань
доповнення, правопис
Рядок 4:
 
== Алгоритм ==
Результатом роботи алгоритма є знаходження максимуму функції на множині допустимій множині. При чому множина можу бути як дискретною, так і раціональною. В ході роботи алгоритму виконується дві операції: розбиття вихідної множини на підмножини(гілки), та знаходження оцінок(меж). Існує оцінка множини зверхузгори та оцінка знизу. Оцінка зверхузгори - точка що гарантовано не менша за максимум на заданії підмножин. Оцінка знизу - точка що гарантовано не більша за максимум на заданії підмножині. Множина що має найбільшу оцінку зверху зветься рекордною. На початку вся множина вважається рекордною.
# Рекордна множина розбивається на підмножини;
# Знайти оцінки зверхузгори та знизу для нових підмножин;
# Визначити максимальну оцінку знизу серед усіх підмножин;
# Видалити ті множини у яких оцінка зверху менша за максимальну оцінку знизу;
# Знайти максимальну оцінку зверхузгори серед усіх підмножин ту вважати її рекордною;
# Якщо не досягнуто дискрентості, або необхідної точності перейти по пункту 1;
Результатом роботи є значення між оцінкою зверхузгори та знизу для рекордної множини.
Точністю є різниця між верхнею та нижньою оцінками, тобто для дискретних множин алгоритм завершений тоді, коли ці оцінки співпадають.
Метод використовується для вирішення деяких NP-повних задач. Швидкість алгоритму залежить від вигляду функції та способу визнацення оцінок, але гарантовано не більша за повний перебір.
 
== Джерела інформації ==
Отримано з https://uk.wikipedia.org/wiki/Метод_гілок_і_меж