66 Рис. 2.5. И ллю страция методов программирования: а динамического (ветвь дерева); б дихотом ического (произвольное дерево). Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотом ического программирования м ож но сформулировать следующ им образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот п р ш щ и п оптимальности м ож но записать следую щ им образом: где р(у) множество пар (i, j) , та ки х что (yi, y j) = у. О б щ и й с л у ч а й Рассмотрим произвольное сетевое представление ф ункции f(x), задаваемое сетью, выходом которой является верш ина, соответствующ ая ф ункции f(x), а выходами верш ины, соответствующ ие переменным Xj, i = l, n . Рассмотрим множество конечны х верш ин, которы е не являются висячими, т.е. и х степени захода больше 1. Разделим произвольным образом затраты ф(хО на ki частей, где ki число заходящ их д уг. Ф актически м ы ка к бы разделили верш ину i на ki висячих верш ин с соответствующ ей частью затрат. Далее применяем описан |
функций ф(х1) и ф2(хг) для соответствующих значений Х и хг. Так, например, клетке (xi,X2) = (3,2) соответствует сумма Ф1(3) + Ф2(2) = 2 0 + 10 = 30. Далее будем называть эту сумму затратами на достижение соответствующего состояния. 2 шаг. Из всех элементов матрицы имеющих одно и то же значение y = fi(Xi,X2) выбираем элемент с минимальной сытимой Ф(х1)+ср2(х2). Минимальную сумму записываем в нижнюю половину клетки, соответствующей этому значению у в верхней матрице. Так, например, значению у = 3 соответствуют 5 ‘элементов нижней матрицы: (3;2), (4;2), (3;3), (4;3) и (2;4). Из них элемент (3;2) имеет минимальную сумму 30 (это число записано в нижней половине соответствующей клетки). Поэтому в верхней матрице значению у = 3 соответствует число 30, записанное в нижней половине соответствующей клетки. Далее шаги 1и 2 повторяются для верхней матрицы. В результате для каждого значения f(x) мы получаем минимальную величину ф(х). Несложно обобщить описанный алгоритм на случай производльного дихотомического представления функции f(x) в виде дерева. Шаги 1 и 2 алгоритма повторяются, начиная с висячих вершин дерева дихотомического представления. Заметим, что дихотомическое представление Рис. 3.1 имеет тип ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае, когда дихотомическое представление имеет вид дерева, является обобщением метода динамического программирования, распгаряя круг задач, решаемых на основе данного подхода (Рис. 3.2). Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программи57 рования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Метод динамического программирования (ветвь дерева) Метод дихотомического программирования (произвольное дерево) Рис. 3.2. Формально этот принцип оптимальности можно записать следующим образом: Ф к(у)= min [ф( (yi)+ Общий случай Рассмотрим произвольное дихотомическое представление функции f(x), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами — вершины, соответствующие переменным Xj, i = I,n . Рассмотрим множество конечных вершин, которые не являются висячими, то есть их степень захода больше 1. Разделим произвольным образом затраты ф](Х) на kj частей, где kj число заходящих дуг. Фактиче58 |