|
РОССИЙСКАЯ АЛ УСУДЛРСТПСННАЯ ^ БИБЛИОТЕКА ценности соответствующего предмета. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной ценности соответствующего набора предметов. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на рис. 1.4.7толстыми дугами. Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.4.8. Первая матрица соответствует второму слою сети рис. 1.4.7. В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья четвертому. Если в матрице имеется несколько клеток с одинаковыми весами, то в следующую матрицу для этого значения веса берется максимальное значение ценности. Это и есть принцип оптимальности Веллмана для матричного представления метода динамического программирования. В последнем столбике рис. 1.4.8 приведены оптимальные значения суммарной ценности предметов при любых ограничениях на вес ранца. Метод динамического программирования является эффективным методом решения некоторых задач дискретной оптимизации, существенно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных значениях весов предметов объем вычислений пропорционален числу вершин сети, то есть не более чем Л п. При заданном Л объем вычислений растет пропорционально п, что свидетельствует о высокой эффективности метода. К сожалению, метод динамического программирования применим к ограниченному классузадач. Подводя итоги краткого обзора основных методов решения задач дискретной оптимизации отметим, что к точным методам решения (или к методам решения с оценкой точности) относятся метод ветвей и границ и метод динамического программирования. Эффективность метода ветвей и границ в |
путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному весу предметов. Примем длины горизонтальных дуг равными 0, а длины наклонных равными ценности соответствующего предмета. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной ценности Рис. 1.7. соответствующего набора предметов. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на Рис. 1.7 толстыми дугами. Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.8. Первая матрица соответствует второму слою сети рис. 1.7. В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья —четвертому. Если в матрице имеется несколько клеток с одинаковыми весами, то в следующую матрицу для этого значения веса берется максимальное значение ценности. Это и есть принцип оптимальности Веллмана для матричного представления метода динамического программирования. В последнем столбике рис. 1.8 приведены оптимальные значения суммарной ценности предметов при любых ограничениях на вес ранца. Метод динамического программирования является эффективным методом решения некоторых задач дискретной оптимизации, существенно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных значениях весов предметов объем вычислений пропорционален числу вершин сети, то есть не более чем R3n. При заданном R объем вычислений растет про85 т порционально п, что свидетельствует о высокой эффективности метода. К сожалению, метод динамического программирования применим к ограниченному классу задач. оу / 5 3X / 5 X XX X XXо / о / X У 1х X 4 / / о / о W / 2 / 6 X XX 0X X о 0X Х о XуУ / х З jоу Х о ЗУ X 4 У2 щ / / 9 6Х / 9 \ у Х 4 X X 9X Л .2 4X Хб 4X /6 8X Л \ X X 7у Хо X X 6X X 8 X X X ° х Хо ° х Хо X уУ / х 4 о/ Хо 0 / X 5 10^ 1 4 '1 2 11 10 Рис. 1.8. Подводя итоги краткого обзора основных методов решения задач дискретной оптимизации отметим, что к точным методам решения (или к методам решения с оценкой точности) относятся метод ветвей и границ и метод динамического программирования. Эффективность метода ветвей и границ в существенной степени зависит от точности нижних (или верхних) оценок оптимального решения на подмножествах решений. Получение хороших оценок во многих случаях по сложности сравнимо с решением исходной задачи. Метод динамического программирования, как уже отмечалось выше, применим к ограниченному классу задач. Описываемый в следующих параграфах метод сетевого программирования с одной стороны обобщает метод динамического программирования (при сетевом представлении типа дерева), а с другой стороны для общего случая дает достаточно универсальный алгоритм получения нижних (верхних) оценок, что позволяет эффективно применять метод ветвей и границ. 86 |