|
47 нию у = 3 соответствует число 30, записанное в нижней половине соответствующей клетки. Далее шаги 1и 2 повторяются для верхней матрицы. В результате для каждого значения Дх) мы получаем минимальное значение ср(х). На рис. 1.5.4 кружками выделены минимальные затраты. Несложно обобщить описанный метод на случай произвольного сетевого представления функции Дх) в виде дерева. Главное, чтобы задачи, соответствующие каждой вершине сетевого представления имели эффективные методы решения. В случае дихотомического представления это всегда имеет место. Заметим, что дихотомическое представление (см. рис. 1.5.4) имеет структуру в виде ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае дихотомического представления в виде дерева, является обобщением метода динамического программирования, расширяя круг задач, решаемых на основе данного подхода (рис. 1.5.5). Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное а. Рис. 1.5.5. |
Несложно обобщить описанный метод на случай произвольного сетевого представления функции f(x) в виде дерева. Главное, чтобы задачи, соответствующие каждой вершине сетевого представления имели эффективные методы решения. В случае дихотомического представления это всегда имеет место. Заметим, что дихотомическое представление (см. рис. 2.4) имеет структуру в виде ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае дихотомического представления в виде дерева, является обобщением метода динамического программирования, расширяя круг задач, решаемых на основе данного подхода (Рис. 2.5). Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот принцип оптимальности можно записать следующим образом: а. Рис. 2.5. Иллюстрация методов программирования: а —динамического (ветвь дерева); б дихотомического (произвольное дерево). где р(у) множество пар (i, j), таких что fk(у*, yj) = у. 91 |