|
Способ построения сети рассмотрим на примере. И м ею тся четыре предмета, данные о ценностях и весах которы х приведены в табл. 1 . Таблица 1.1. И сходны е данные 58 i 1 2 3 4 ai 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. Рис. 1.7. Сеть возможны х вариантов решения Очевидно, что лю бой путь в сети, из начальной верш ины О в одну из ко нечных верш ин соответствует некоторому набору предметов. И наоборот, лю бому набору предметов, суммарным весом не более 6 однозначно соответствует |
Метод динамического программирования. В основе метода лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некоторой специальным образом построенном семействе возможных траекторий. Принцип оптимальности Беллмана гласит: любой участок оптимальной траектории оптимален [17, 22, 26]. В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети. Дадим иллюстрацию метода на примере классической задачи о ранце. Имеются п предметов. Каждый предмет имеет ценность сц и вес Cj. Требуется выбрать подмножество Q предметов так, чтобы их суммарная ценность A(Q ) = 2 а , i€Q была максимальной при ограничении на суммарный вес 2 c iiR leq Способ построения сети рассмотрим на примере. Имеются четьфе предмета, данные о ценностях и весах которых приведены в таблице 1. Таблица 1.1. i 1 2 3 4 ai 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), соответствую50 щие четырем возможным вариантам для двух предметов. Продолжая таким образом, получим сеть, приведенную на Рис. 1.7. Рис. 1.7. Очевидно, что любой путь в сети, из начальной вершины О в одну из конечных вершин соответствует некоторому набору предметов. И наоборот, любому набору предметов, суммарным весом не более 6 однозначно соответствует путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному весу предметов. Примем длины горизонтальных дуг равными О, а длины наклонных равными ценности соответствующего предмета. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной ценности соответствующего набора предметов. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на Рис. 1.7 толстыми дугами. Метод динамического программирования можно представить в другой эквивалентной форме, удобной для сравнения его с методом дихотомического программирования. Эта форма не требует построения сети, а использует матричный способ вычислений рис. 1.8. Первая матрица соответствует второму слою сети рис. 1.7. В верхней половине каждой клетки указана величина веса для различных вариантов из двух первых предметов, а в нижней соответствующая ценность. Вторая матрица соответствует третьему слою, а третья —четвертому. Если в матрице имеется несколько 51 |