|
Если удается отбросить все элементы разбиения, то рекорд — оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д. Рассмотрим дискретную экстремальную (для определенности — на минимум) задачу в общем виде. Пусть задано дискретное множество А и определенная на нем функция f. Обозначим минимум функции f на X как F(X). Требуется найти х0 е A: f(x0) = F(A). Введем следующие замечания. Замечание 1. Пусть А = А0 U A! U ... U Ак, Aj П Aj = 0, i ф j . Причем, F(A) < F(A0), т. е. на Ао минимум не достигается. Тогда справедливо следующее: F(A) = min (F(Aj) i е 1 : к}. Замечание 2. Пусть Ф функция, заданная на совокупности подмножеств множества А так, что Ф(Х) < F(X) VXCIA. Пусть х* произвольный элемент А и пусть Р = f(x*). Тогда справедливо следующее: F(A) = min {Р, min (F(Aj) i < 1 : к, Ф(А0 < Р}}. = Эти два замечания позволяют предложить следующую технологию поиска минимума. Разобьем множество А на какие-либо подмножества Aj и на каждом из них найдем нижнюю оценку Ф. Для элементов множества А будем вычислять значения функции f и запоминать наименьшее в качестве рекордного значения. Все подмножества, у которых оценка выше рекордного значения функции (Р), объединим в подмножество А0, чтобы в дальнейшем не рассматривать. Теперь выберем какое-либо из множеств Ai5 i > 0. Разобьем это множество на несколько более мелких подмножеств. При этом мы будем продолжать улучшать рекордное значение Р . Этот процесс продолжается до тех пор, пока не будут просмотрены все множества Aj, i > 0 [127, с. 313]. Более наглядно метод ветвей и границ (поиск с возвратом) можно объяснить с помощью дерева возможностей. Узлы такого дерева можно рассмат 83 |
подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и оно подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д. Рассмотрим дискретную экстремальную (для определенности — на минимум) задачу в общем виде. Пусть задано дискретное множество А и определенная на нем функция f. Обозначим минимум функции f на X как F(X). Требуется найти Хо ^ А: f(xo) = F(A). Введем следующие замечания. Замечание 1. Пусть А = Ао U A i U ... U А^ А{ П Aj = 0, i 7 j . Причем, ^ F(A) < F(Ao), т. е. на Aq минимум не достигается. Тогда справедливо следующее: F(A) = min {F(Ai) i ^ 1 : Ic}. Замечание 2. Пусть Ф функция, заданная на совокупности подмножеств множества А так, что Ф(Х) < F(X) V X C I A . Пусть х* произвольный элемент А и пусть = f(x'''). Тогда справедливо следующее: F(A) = min {f^, min {F(Ai) i e l : k, Ф(АО < f^}}. Эти два замечания позволяют предложить следующую технологию поиска минимума. Разобьем множество А на какие-либо подмножества Ai и на каждом из них найдем нижнюю оценку Ф. Для элементов множества А будем вычислять значения функции f и запоминать наименьшее в качестве рекордного значения. Все подмножества, у которых оценка выше рекордного значения функции ( f ) , объединим в подмножество Ао, чтобы в дальнейшем не рассматривать. Теперь выберем какое-либо из множеств Aj, i > 0. Разобьем это множество на несколько более мелких подмножеств. При этом мы будем продолжать улучшать рекордное значение Р . Этот процесс продолжается до тех пор, пока не будут просмотрены все множества Ai, i > О [120, с. 313]. Более наглядно метод ветвей и границ (поиск с возвратом) можно объяснить с помощью дерева возможностей. Узлы такого дерева можно рассматривать как совокупности конфигураций (подмножества А; множества А), а каждый потомок некоторого узла представляет подмножество этой совокупности. 99 |