|
40 Т аб л и ц а 1.4.1 I 1 2 3 4 а, 3 2 4 5 2 1 3 4 Пусть Я = 6. Строим на плоскости систему координат, одна ось которой соответствует предметам, а вторая —их весу. По оси предметов отмечаем номера предметов 1,2,3,4 (рис. 1.4.7). Из начала координат проводим две дуги одна горизонтальная в точку (1,0), а другая наклонная в точку (1,2), где 2—вес первого предмета. Первая дуга соответствуетслучаю, когда первый предмет не берется, а вторая когда он берется. Из каждой полученной точки (1, 00) и (1,2) проводим также по две дуги для второго предмета. Получаем четыре точки (2,0), (2,1), (2,2) и (2,3), соответствующие четырем возможным вариантам для двух предметов. Продолжая таким образом, получим сеть, приведеннуюна рис. 1.4.7. Рис. 1.4.7 Очевидно, что любой путь в сети, из начальной вершины 0 в одну из конечных вершин соответствует некоторому набору предметов. И наоборот, любому набору предметов, суммарным весом не более 6 однозначно соответствует путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному весу предметов. Примем длины горизонтальных дуг равными 0, а длины наклонных равными |
Метод динамического программирования В основе метода лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некоторой специальным образом построенном семействе возможных траекторий. Принцип оптимальности Беллмана гласит: любой участок оптимальной траектории оптимален [17,22, 26]. В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети. Дадим иллюстрацию метода на примере классической задачи о ранце. Имеются п предметов. Каждый предмет имеет ценность ci{ и вес с,. Требуется выбрать подмножество Q предметов так, чтобы их суммарная ценность A(Q) = £сц isQ была максимальной при ограничении на суммарный вес Z c i S R ieq Способ построения сети рассмотрим на примере. Имеются четыре предмета, данные о ценностях и весах которых приведены в таблице I. Таблица 1. i 1 2 3 4 а* 3 2 4 5 Ci 2 1 3 4 Пусть R = 6. Строим на плоскости систему координат, одна ось которой соответствует предметам, а вторая их весу. По оси предметов отмечаем номера предметов 1,2,3,4 (Рис. 1.7). Из начала координат проводим две дуги —одна горизонтальная в точку (1,0), а другая наклонная в точку (1,2), где 2 вес первого предмета. Первая дуга соответствует случаю, когда первый предмет не берется, а вторая когда он берется. Из каждой полученной точки (1, 00) и (1,2) проводим также по две дуги для второго предмета. Получаем четыре точки (2,0), (2,1), (2,2) и (2,3), соответствующие четырем возможным вариантам для двух предметов. Продолжая таким образом, получим сеть, приведенную на Рис. 1.7. Очевидно, что любой путь в сети, из начальной вершины 0 в одну из конечных вершин соответствует некоторому набору предметов. И наоборот, любому набору предметов, суммарным весом не более 6 однозначно соответствует 84 путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному весу предметов. Примем длины горизонтальных дуг равными 0, а длины наклонных равными ценности соответствующего предмета. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной ценности Рис. 1.7. соответствующего набора предметов. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на Рис. 1.7 толстыми дугами. Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.8. Первая матрица соответствует второму слою сети рис. 1.7. В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья —четвертому. Если в матрице имеется несколько клеток с одинаковыми весами, то в следующую матрицу для этого значения веса берется максимальное значение ценности. Это и есть принцип оптимальности Веллмана для матричного представления метода динамического программирования. В последнем столбике рис. 1.8 приведены оптимальные значения суммарной ценности предметов при любых ограничениях на вес ранца. Метод динамического программирования является эффективным методом решения некоторых задач дискретной оптимизации, существенно сокращая перебор. Так, например, для рассмотренной задачи о ранце при целочисленных значениях весов предметов объем вычислений пропорционален числу вершин сети, то есть не более чем R3n. При заданном R объем вычислений растет про85 |