|
Далее будем называть эту сум м у затратами иа достижение соответствую щ его состояния. 2 ш аг. И з всех элементов матрицы, им ею щ их одно и то же значение y = f](X b Хз) выбираем элемент с м инимальной сум м ой (р](Х])+ф2(х2). М и н и мальную сум м у записываем в н и ж н ю ю половину клетки, соответствующ ей этому значению у в верхней матрице. Так, например, значению у = 3 соответствую т 5 элементов ниж ней матрицы: (3; 2), (4; 2), (3; 3), (4; 3) и (2; 4). И з них элемент (3; 2) имеет м иним альную сум м у 30 (это число записано в ниж ней половине соответствующ ей клетки). П оэтом у в верхней матрице значению у = 3 соответствует число 30, записанное в ниж ней половине соответствующ ей клетки. Далее ш аги 1 и 2 повторяются для верхней ма-фицы. В результате для каж дого значения f(x ) м ы получаем минимальное значение ф(х). Н а рис. 2.4 круж кам и выделены минимальные заф аты. Несложно обобщ ить описанны й метод на слзшай произвольного сетевого представления ф ункции f(x ) в виде дерева. Главное, чтобы задачи, соответствующ ие каж дой вершине сетевого представления имели эффективные методы решения. В случае дихотом ического представления это всегда имеет место. Заметим, что дихотомическое представление (см. рис. 2.4) имеет с ф у кту р у в виде ветви дерева. В этом случае метод дихотом ического программирования переходит в метод динамического проф аммирования. Т аким образом, метод дихотом ического проф аммирования в случае дихотом ического представления в виде дерева, является обобщ ением метода динам ического программирования, расширяя кр у г задач, реш аемых на основе данного подхода (Рис. 2.5). 65 |
функций ф(х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 |