Метод ветвей и границ |
Основная идея |
|
|
Метод ветвей и границ. Основная идея
Пусть x текущий рекорд и UB(D) = f(x ).
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 4. |
9.03.2016 |
5 / 8 |
Метод ветвей и границ |
Основная идея |
|
|
Метод ветвей и границ. Основная идея
Пусть x текущий рекорд и UB(D) = f(x ).
Вычисляем LB(D).
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 4. |
9.03.2016 |
5 / 8 |
Метод ветвей и границ |
Основная идея |
|
|
Метод ветвей и границ. Основная идея
Пусть x текущий рекорд и UB(D) = f(x ). Вычисляем LB(D).
Åñëè UB(D) = LB(D), òî STOP, x оптимальное решение. Иначе, разбиваем D на подмножества D = d1 [ [ dk.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 4. |
9.03.2016 |
5 / 8 |
Метод ветвей и границ |
Основная идея |
|
|
Метод ветвей и границ. Основная идея
Пусть x текущий рекорд и UB(D) = f(x ). Вычисляем LB(D).
Åñëè UB(D) = LB(D), òî STOP, x оптимальное решение. Иначе, разбиваем D на подмножества D = d1 [ [ dk.
Для каждого подмножества вычисляем LB(di), UB(di), i = 1; : : : ; k.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 4. |
9.03.2016 |
5 / 8 |
Метод ветвей и границ |
Основная идея |
|
|
Метод ветвей и границ. Основная идея
Пусть x текущий рекорд и UB(D) = f(x ). Вычисляем LB(D).
Åñëè UB(D) = LB(D), òî STOP, x оптимальное решение. Иначе, разбиваем D на подмножества D = d1 [ [ dk.
Для каждого подмножества вычисляем LB(di), UB(di), i = 1; : : : ; k.
Åñëè f(x ) > UB(di), òî меняем рекорд.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 4. |
9.03.2016 |
5 / 8 |
Метод ветвей и границ |
Основная идея |
|
|
Метод ветвей и границ. Основная идея
Пусть x текущий рекорд и UB(D) = f(x ). Вычисляем LB(D).
Åñëè UB(D) = LB(D), òî STOP, x оптимальное решение. Иначе, разбиваем D на подмножества D = d1 [ [ dk.
Для каждого подмножества вычисляем LB(di), UB(di), i = 1; : : : ; k.
Åñëè f(x ) > UB(di), òî меняем рекорд.
Åñëè LB(di) > f(x ), òî отбрасываем di.
Иначе разбиваем di на подмножества, и т.д. Поскольку D конечное множество и одноэлементные множества всегда отбрасываются, то процесс конечен и дает оптимальное решение.
Кононова П. А. (ФИТ НГУ) |
Теория принятия решений. Лекция 4. |
9.03.2016 |
5 / 8 |