Полная версия

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Оптимальное использование транспортных средств

Будем рассматривать задачу:

Найти

при

Ci>0 и ai>0 (i=l,... ,п). Целочисленность ai и Ci (i= 1,... ,n) не обязательна.

Эта задача соответствует возможности выбирать несколько одинаковых

предметов для оптимальной загрузки транспортных средств. При ki =1, i=l,___,n

получаем упоминавшуюся задачу о рюкзаке, в которой каждый предмет имеется в одном экземпляре.

В общем случае не даёт оптимального решения казалось бы очевидное стремление упорядочить предметы в порядке убывания стоимости, приходящейся на единицу веса, и последовательно брать их максимально возможное количество до исчерпания грузоподъёмности.

Задача оптимальной загрузки транспортного средства решена Р. Веллманом [3] с помощью разбиения регулярной сетки и дальнейшей реализации его метода динамического программирования.

Отметим, что при неудачном выборе дискрета можно получить неоптимальные решения. Это следует из простого примера: грузоподъёмность (ресурс) 7 единиц, имеется 2 предмета весом по 1, 2 предмета весом по 1.7 и 2 предмета по 2.6 единиц. Стоимость предмета для простоты примем численно равной его весу. Алгоритм Р.Беллмана [3] требует задания регулярной сетки состояний и

«привязки» реальных состояний к узлам сетки. Если взять дискрет равный наименьшему весу, то есть 1 и строго следовать этому алгоритму, то получим решение : взять 2 первых и по одному второй и третий предмет (2+1.7+2.6=6.3), тогда как оптимальное решение: взять первый, два вторых и третий предмет(1+3.4+2.6=7). Характерно, что и при дискрете 0.5 получается тот же не оптимальный результат при использовании регулярной сетки. Конечно, при дискрете 0.1 никакой ошибки не возникает, но задание малого дискрета требует анализа большого числа состояний, что, как будет показано ниже, совершенно не нужно, если отказаться от использования регулярной сетки состояний и рассматривать на каждом шаге только подмножество Парето множества реальных состояний.

Для иллюстрации применимости и эффективности динамического программирования с использованием множеств Парето рассмотрим несколько задач типа 4.1.

Начнём с задачи об оптимальной загрузке транспортного средства в её самой простой постановке [4, 22, 33], т.е. с задачи о рюкзаке. Решение этой задачи в течение многих лет приводится в различных источниках как пример применения метода динамического программирования. К сожалению, это решение показывает, что формальный подход может приводить к тому, что плохая реализация метода динамического программирования в некоторых случаях менее эффективна, чем примитивный метод полного перебора.

Задача состоит в следующем. Имеется транспортное средство заданной грузоподъёмности Q и набор предметов различного веса и стоимости. Нужно выбрать набор различных предметов с максимальной суммарной стоимостью и суммарным весом, не превосходящим грузоподъёмности. Численный пример заимствован из книги [6].

Имеется автомашина грузоподъёмностью Q=35 единиц веса и шесть предметов, веса и стоимости которых указаны в таблице 4.1.

Таблица 4.1. Исходные данные

Предмет П|

И,

п2

Из

П4

п5

п6

Вес qi

4

7

11

12

16

20

СТОИМОСТЬ Cj

7

10

15

20

27

34

Суммарный вес предметов превышает грузоподъёмность машины и поэтому требуется эту грузоподъёмность использовать оптимальным образом, то есть взять такие предметы, суммарный вес которых не превышает Q= 35, а суммарная стоимость максимальна.

Согласно [6, с Л 04] рассматривается шесть шагов (этапов), на каждом из которых принимается решение брать соответствующий предмет в машину или не брать. Номер шага соответствует номеру предмета в таблице 2. На каждом шаге всего лишь два возможных решения (управления) 0- не брать соответствующий предмет и 1 -брать. Состояние системы S перед очередным шагом характеризуется ресурсом грузоподъёмности, который ещё остался в нашем распоряжении до полной загрузки машины после того, как предыдущие шаги выполнены, т.е. решён вопрос брать или не брать предметы с меньшими номерами и какие-то из них погружены в машину. Для каждого состояния S предлагается найти Wi(S)- суммарную максимальную стоимость предметов, которыми можно «догрузить» машину при данном значении S, и положить Xi(S)=l, если мы берём данный (i-ый) предмет, и Xi(S)=0, если не берём. Величины Xi(S) (i=l,2,...,6) называются «условные оптимальные шаговые управления». Их последовательность определяет набор взятых предметов. Они называются условными, так как зависят от состояния S.

В целом процесс поиска оптимального варианта загрузки машины представлен таблицей 4.2.

В соответствии с решением, изложенным в [6, с. 105-106], рассматриваются только целые значения и для S получается 36 значений (от 0 до 35 включительно). Выбор целочисленных значений при таких исходных весах очевиден, а вот рассмотрение такого большого числа состояний ничем не диктуется и не является необходимым, если рассматривать процесс, начиная не с последнего, а с первого шага. Вместо этого в [6] рассматривается классический алгоритм (от конца к началу), то есть вначале рассматриваются все переходы на шестом шаге в конечное состояние.

Таблица 4.2. Процесс решения задачи (от конца к началу)

i=

=6

i=

=5

=A

i=

3

i=

2

1=1

S

Xi

Wi

Xi

Wi

Xi

Wi

Xi

Wi

Xi

Wi

Xi

Wi

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

2

0

0

0

0

0

0

0

0

0

0

3

0

0

0

0

0

0

0

0

0

0

4

0

0

0

0

0

0

0

0

0

0

5

0

0

0

0

0

0

0

0

0

0

6

0

0

0

0

0

0

0

0

0

0

7

0

0

0

0

0

0

0

0

1

10

8

0

0

0

0

0

0

0

0

1

10

9

0

0

0

0

0

0

0

0

1

10

10

0

0

0

0

0

0

0

0

1

10

11

0

0

0

0

0

0

1

15

0

15

12

0

0

0

0

1

20

0

20

0

20

13

0

0

0

0

1

20

0

20

0

20

14

0

0

0

0

1

20

0

20

0

20

15

0

0

0

0

1

20

0

20

0

20

16

0

0

1

27

0

27

0

27

0

27

17

0

0

1

27

0

27

0

27

0

27

18

0

0

1

27

0

27

0

27

0

27

19

0

0

1

27

0

27

0

27

1

30

20

1

34

0

34

0

34

0

34

0

34

21

1

34

0

34

0

34

0

34

0

34

22

1

34

0

34

0

34

0

34

0

34

23

1

34

0

34

0

34

1

35

1

37

24

1

34

0

34

0

34

1

35

1

37

25

1

34

0

34

0

34

1

35

1

37

26

1

34

0

34

0

34

1

35

1

37

27

1

34

0

34

0

34

1

42

1

44

28

1

34

0

34

1

47

0

47

0

47

29

1

34

0

34

1

47

0

47

0

47

30

1

34

0

34

1

47

0

47

0

47

31

1

34

0

34

1

47

1

49

0

49

32

1

34

0

34

1

54

0

54

0

54

33

1

34

0

34

1

54

0

54

0

54

34

1

34

0

34

1

54

0

54

0

54

35

1

34

0

34

1

54

0

54

i

57

0

57

Можно, конечно, просчитать все возможные комбинации на первых пяти шагах и выявить возможные состояния системы на шестом шаге (то есть сколько могло остаться ресурса грузоподъёмности после того, как определились варианты решений относительно первых пяти предметов).

В данной задаче таких состояний 32, а допустимых по грузоподъёмности и того меньше. Но при большом числе шагов этот перебор просто не целесообразен. Поэтому и рассматриваются все 36 состояний перед шестым шагом как возможные, хотя не все они могут быть достижимы.

Первые 20 из них (осталось от 0 до 19 единиц грузоподъёмности) не позволяют взять шестой предмет, вес которого 20 единиц. Им соответствует Хб=0, Уб=0. Остальным 16 состояниям соответствует Хб=1, Уб=34, так как стоимость шестого предмета равна 34. Переходя к пятому шагу, то есть решая вопрос брать или не брать пятый предмет весом 16 и стоимостью 27, снова рассматриваются 36 возможных состояний и для каждого из них определяется оптимальное шаговое управление. Для состояний с S от 0 по 15 включительно выбора нет, так как вес пятого предмета 16, а осталось меньше. Для состояний с Sc 16 по 19 включительно можно взять пятый предмет или не брать. Если не брать, на шестой всё равно не хватит грузоподъёмности (нужно не менее 20). Поэтому для этих состояний X5=l, W5=27. Для состояний с S от 20 по 35 есть выбор: брать пятый (следовательно, не брать шестой) или не брать пятый, но взять шестой предмет. Для этих состояний xs=0, Ws=34 (хб=1), так как шестой предмет брать выгоднее, чем пятый, а оба взять нельзя.

Далее рассматриваем четвёртый шаг, то есть решаем брать или не брать четвёртый предмет весом 12 и стоимостью 20. Предлагается снова рассматривать все 36 возможных состояний (по числу оставшихся в нашем распоряжении единиц грузоподъёмности). Состояниям с 0 по 11 включительно соответствует Х4=0 и W4=0, так как ни один из оставшихся предметов взять нельзя. Состояниям с 12 по 15 включительно соответствует х4=1 и W4=20 (берём четвёртый предмет, а на оставшиеся пятый и шестой не хватает грузоподъёмности). Состояниям с 16 по 19 включительно соответствует решение не брать четвёртый предмет, а взять пятый (на два предмета нехватает ресурса) и, следовательно х4=0 и W4=27. Состояниям с 20 по 35 соответствует выбор не брать четвёртый предмет, а взять пятый. Соответственно х4=0 и W4=34. При дальнейших переходах от большего номера шага к меньшему при рассмотрении любого состояния нам нет необходимости исследовать все возможные комбинации относительно всех оставшихся предметов, так как для всех состояний на всех уже рассмотренных шагах известно, что нужно делать (брать или не брать соответствующий предмет) и к чему это приведёт при оптимальном выборе, то есть суммарная стоимость погруженных предметов. Достаточно рассмотреть в какие состояния мы попадаем, если берём или не берём очередной предмет, то есть уменьшаем на соответствующую величину остающийся ресурс грузоподъёмности или оставляем его неизменным. Каждому из полученных состояний соответствует своя максимальная стоимость погруженных предметов, которую запомнили на шаге, номер которого на 1 больше. Если берём рассматриваемый предмет, к ней прибавляется его стоимость, а если нет, то соответствующая этому переходу стоимость не меняется. Сравнивая две стоимости, принимаем решение брать или не брать рассматриваемый предмет.

Например, на четвёртом шаге находимся в состоянии S=17. Это означает: предполагаем после решения судьбы первых трёх предметов у нас осталось 17 единиц грузоподъёмности, а предстоит решать судьбу 4, далее 5 и 6 предмета. Если берём четвёртый предмет, то переходим в состояние S=5, так как вес четвёртого предмета равен 12, а если не берём, то переходим в состояние 17. Состоянию S=5 соответствует Ws=0 и потому при Х4=1 имеем W4=20, а состоянию S= 17 соответствует Ws=27 и потому при Х4=0 имеем W4=27.

Аналогично приходится поступать вплоть до первого шага, последовательно заполняя столбцы таблицы 4.2 от шага с номером i=6 до i=2. При решении брать или не брать первый предмет (i=l) мы уже имеем столбец для i=2 и в нём для каждого из 36 состояний отражены последствия перехода в них (величина W2). Нас интересует возможность увеличения суммарной стоимости погруженных предметов, если погрузить первый предмет весом 4 и стоимостью 7. Это можно сделать всегда, так как на первом шаге наш ресурс грузоподъёмности равен 35 и перейти мы можем только в состояния 35 и 31 (все прочие числа в таблице 3 при i=2 никакого смысла не имеют и вычисляли мы их напрасно!) При переходе в состояние 35 (не берём первый предмет) имеем Wi=57, а при переходе в состояние 31(берём первый весом 4) только Wi= 49+7=56. Поэтому xi=0,Wi=57. Обратным разворотом получаем хг=1, хз=0, Х4=1,Х5=1,Хб=0. На каждом шаге для каждого из состояний мы запомнили брать или не брать соответствующий предмет(0 или 1), что и дало возможность восстановить весь план загрузки машины, который состоит в том, что надо взять предметы 2, 4 и 5 общим весом 35 и стоимостью 57.

Характерно, что даже на втором шаге при такой формализации задачи рассматриваются всё те же 36 состояний, хотя очевидно, что на первые два предмета не только нельзя полностью истратить весь ресурс грузоподъёмности, но в любом случае останется 24 единицы. Поэтому большинство состояний на этом шаге вообще можно было не рассматривать и никаких расчётов по

переходу из них в конечное состояние не делать, если двигаться от первого шага к последнему. Отсюда сразу следует, что не верно содержащееся во многих источниках, например в [6], утверждение : «В любой задаче динамического программирования «начало» и «конец» можно поменять местами. Оба подхода совершенно равносильны.» Эти подходы равносильны в смысле получаемого результата, но не затрат памяти и времени счёта на его получение

В целях сравнения анализируемого решения с методом полного перебора отметим, что необходимо запоминать таблицу 4.2, то есть 360 чисел. Не предполагая упорядоченности предметов по весу, для оценки объёма вычислений заметим, что на каждом из шагов с пятого по второй нужно для каждого из состояний (там их 36 на каждом шаге) рассматривать два решения: берём или не берём соответствующий предмет. Сначала нужно определить состояние предыдущего шага, из которого можно попасть в рассматриваемое. Например, на четвёртом шаге рассматриваем состояние 25 (всего их на каждом шаге 36). Это значит, что осталось 25 единиц грузоподъёмности и решается вопрос брать или не брать предмет весом 12 единиц и ценой 20. Если не брать, то на пятом шаге (идём с конца в начало и состояние- это оставшаяся грузоподъёмность) останутся те же 25, а если брать, то только 13. Возможные переходы и состояния пятого шага определены. Далее, нужно суммировать стоимость предмета (20 единиц) с той что была определена на пятом шаге для состояния 13 (там нуль, см. табл. 4.2) и сравнить с оценкой состояния 25 на пятом шаге (там 34, см. табл. 4.2). Получается, что при наличии 25 единиц оставшейся грузоподъёмности четвёртый предмет лучше не брать и состояние 25 на четвёртом шаге получает оценку 34 и признак перехода Xi=0). Поскольку эти вычитания, суммирования и сравнения нужно делать в каждом из 36 состояний на четырёх шагах, потребуется выполнить 144 операции сложения и вычитания.

При использовании метода полного перебора на первом шаге имеем 2 варианта (брать или не брать первый предмет), на втором шаге уже четыре состояния и столько же вариантов решения судьбы двух первых предметов. Аналогично, на третьем шаге 8 состояний (вариантов), на 4-ом не более 16 и на 5-ом не более чем 32 состояния (варианта) решения судьбы пяти предметов. Фактически при решении судьбы каждого нового предмета число состояний и, что тоже самое, число вариантов принятия решений по совокупности рассмотренных предметов, удваивается, так как каждому старому соответствует два новых состояния (брать или не брать рассматриваемый предмет). Если ресурс грузоподъёмности исчерпан, то из соответствующих состояний дальнейших переходов просто нет. Для каждого состояния известны общий вес погруженных предметов и их суммарная стоимость, то есть оценка этого состояния. При вычислении оценки каждого нового состояния оценка соответствующего старого состояния сохраняется (не берём рассматриваемый предмет) или увеличивается на его стоимость. На последнем (шестом) шаге не обязательно строить все новые состояния. Нужно взять состояние с максимальной стоимостью и, если оно позволяет взять шестой предмет, то эта комбинация даёт решение. Если же при этом ресурс грузоподъёмности превышен, то эту стоимость (соответственно решение не брать шестой предмет) надо сравнить с вариантом состояния пятого этапа, имеющего достаточный ресурс грузоподъёмности и максимальную стоимость, но проще рассмотреть все состояния после шестого шага.

Их не более 64, причём некоторые соответствуют превышению лимита грузоподъёмности.

Если каждое состояние характеризовать общим весом уже погруженных предметов и их суммарной стоимостью, то в целом схема полного перебора состоит в следующем:

Шаг предмет состояния (в скобках стоимость)

1

4(7)

0(0) 4(7)

2

7(10)

те же, что и 1 + 7(10) 11(17)

3

11(15)

те же, что и 2 + 11(15) 15(22) 18(25) 22(32)

4

12(20)

те же, что и 3 + 12(20) 16(27) 19(30) 23(37) 23(35)

27(42) 30(45) 34(52)

5

16(27)

те же, что и 4 + 16(27) 20(34) 23(37) 27(44) 27(42) 31(49) 34(52)

38(59) 28(47) 32(54) 35(57) далее все с превышением 35.

На пятом шаге имеем 27 состояний, причём одно из них 38(59) с превышением лимита грузоподъёмности. Оно оставлено для упрощения поиска тех предметов, которые нужно взять, как будет ясно из дальнейшего.

Далее, если не брать шестой предмет, то останутся те же 27 состояний и лучшее из них 35(57). Если брать шестой предмет, то на пятом шаге общий вес должен быть не более 15 и можно получить стоимость только 56 15(22)+20(34). Получаем ответ 35(57). Заметим, что на каждом шаге достаточно только к старым состояниям добавить новые и для этого нужно просто прибавить к весу и стоимости вес и стоимость рассматриваемого предмета. Это означает, что можно хранить только те состояния, которые выписаны выше, причём без повторов. Подсчитаем наибольшее число хранимых чисел и производимых вычислений. Для получения этих максимальных (завышенных) оценок предположим, что мы храним все новые состояния, даже те которые соответствуют превышению суммарной грузоподъёмности (35). Более того, будем считать, что и для шестого шага мы вычислили и запомнили 32 дополнительных состояния (берём шестой предмет). Всего запоминаемых состояний по всем шести шагам максимум 64, так как 2+2+4+8+16+32. Для каждого из них нужно хранить два числа (суммарный вес и стоимость погруженных предметов), то есть всего не более 128 чисел, вместо 360 чисел табл.4.2.

В общем случае (при произвольных данных о шести предметах без упорядочивания их по весу или стоимости) для поиска лучшего из 64 состояний нужно среди тех состояний, которые не превышают лимит грузоподъёмности (35), выбрать наибольшее по стоимости. При шести предметах для этого потребуется не более, чем 127 сравнений плюс не более 63 запоминаний текущего номера состояния с наибольшей стоимостью. Для формирования 64 состояний потребуется 114 операций сложения, так как 6 состояний соответствуют исходным весам и стоимостям плюс состояние 0(0).

В методе полного перебора не возникает дополнительных сложностей и с определением тех предметов, которые соответствуют суммарной оптимальной стоимости после того, как она найдена (обратный разворот).

Поскольку состояния у нас упорядочены (по построению, но не по весу и не по стоимости), то найдя лучшее из них, легко восстановить какие предметы ему соответствуют без дополнительного запоминания каких-либо переходов (связей). Для зтого после того, как найден номер оптимального состояния после шестого шага, используя только этот номер, восстановим, какие предметы следует взять. Если этот номер больше чем 32, шестой предмет берём и уменьшаем номер на 32, иначе шестой предмет не берём и номер не меняем. Далее полученный номер сравниваем с 16, если он больше, берём пятый предмет и вычитаем 16, иначе не берём пятый и не меняем номер. Далее сравниваем с 8 и определяемся с четвёртым предметом и если надо вычитаем 8, затем сравниваем с 4, затем с 2 и, наконец, с 1. Всего не более 5 сравнений. В нашем случае оптимальное состояние 35(57) имеет номер 27, поэтому шестой предмет не берём и номер не меняем. Так 27> 16, берём пятый предмет и вычитаем 16, остаётся 11>8, значит, берём четвёртый и вычитаем 8. Остаётся 3<4, третий не берём, 3>2, берём второй и 3-2=1 не берём первый. В итоге взяли 5,4,2 и получили суммарную стоимость 57 при суммарном весе 35.

Получается, что объём вычислений тоже меньше, чем при реализации метода динамического программирования, излагаемой в [ 6 ].

Если при той же грузоподъёмности исходные веса предметов нецелые, например 4.006 вместо 4 и 7.994 вместо 7, то для точного решения задачи с использованием регулярной сетки состояний, придётся взять дискрет 5=0.001 и на каждом шаге рассматривать 35001 состояние, тогда как при полном переборе и с нецелыми данными остаются все те же 64 варианта траектории и не меняются приведенные выше вычисления.

Таким образом, реализация метода динамического программирования, изложенная в [6], для рассматриваемой задачи (и не только для неё) и по объёму вычислений и по объёму используемой памяти хуже метода полного перебора и поэтому может служить примером того как не надо применять метод динамического программирования. Конечно, с ростом числа шагов (предметов) число вариантов по методу полного перебора резко растёт и даже такая реализация метода динамического программирования [6] становится эффективнее метода полного перебора, но сама идея рассмотрения регулярной сетки состояний и поиска на ней оптимального пути при движении от «конца в начало» несостоятельна в любой задаче, где реальные состояния не соответствуют узлам сетки.

Действительно в той же задаче, двигаясь от «начала к концу», как показано выше, можно рассматривать только реальные состояния. При этом вместо полного перебора безусловно следует использовать динамическое программирование. В этом случае на каждом шаге из всех возможных путей, приводящих в рассматриваемое состояние, нужно оставить только один (с наибольшей стоимостью), а остальные исключить вместе со всеми их продолжениями. Это можно сделать, если «дальнейшее поведение системы не зависит от того, как она попала в данное состояние». В рассматриваемой задаче есть такие состояния, например после третьего шага состояние 11 достигается двумя путями : взять только третий предмет или только два первых. В первом случае получаем стоимость 15, а во втором 17. Следовательно, 11 единиц веса для трёх предметов лучше использовать вторым способом и первый способ (брать третий и не брать два первых предмета) бесперспективен, и ни в какие комбинации при решении судьбы четвёртого и далее предметов входить не должен.

Интересно отметить, что при других весах предметов (например, дробных), двух вариантов достижения одного и того же состояния могло и не быть и в этом случае динамическое программирование ничего не даёт (если не округлять веса, то есть не притягиваться к регулярной сетке, что сопряжено с ошибками). Однако динамическое программирование и в этом случае эффективно, если его применять грамотно. Рассмотрим этот вопрос более подробно, оставаясь в рамках всё той же задачи загрузки машины, чтобы продемонстрировать как надо применять этот метод.

Итак, будем решать задачу в прямом направлении и рассмотрим те же шаги. На первом шаге решаем вопрос о первом предмете, на втором - о втором и т.д. Состоянием системы на каждом шаге будем считать уже использованный ресурс грузоподъёмности, т.е. суммарный вес уже погруженных предметов. Перед первым шагом состояние системы характеризуется числом нуль. После этого шага система может оказаться в одном из двух состояний (а не из 36). Первое состояние характеризуется по-прежнему числом нуль (первый предмет не взяли), а второе состояние характеризуется числом 4 (взяли первый предмет). Пм соответствуют стоимости 0 и 7. После второго шага (когда решили вопрос о втором предмете весом 7 и стоимостью 4) система может оказаться в одном из четырёх состояний 0(0), 4(7), 7(10) и 11(17). Первая цифра, как и ранее, - использованный ресурс, а вторая - суммарная стоимость погруженных предметов. Эти состояния означают соответственно для первых двух предметов: не брать ни одного из них, взять только первый, взять только второй, взять оба. После третьего шага могут остаться те же состояния, если не брать третий предмет весом 11 и стоимостью 15. Но могут возникнуть и новые, если берём третий предмет. Например, первые два предмета не брали, а третий решили взять. Тогда система после третьего шага перейдёт в состояние 11(15). А если взять два первых, а третий не брать, то система перейдёт в состояние 11(17). Это одно и то же состояние, но достигается оно разными путями (разная стоимость). В соответствии с принципом оптимальности путь 0,0,1 (брать только третий) можно далее не рассматривать и ни в какие дальнейшие комбинации не включать, что существенно сокращает дальнейшие вычисления, что мы уже отмечали. Поэтому после третьего шага останется семь состояний, а не восемь: 0(0), 4(7), 7(10), 11(17), 15(22), 18(25), 22(32). Эти же состояния получим после четвёртого шага, если не возьмём четвёртый предмет весом 12 и стоимостью 20. Теперь рассмотрим те состояния после четвёртого шага, в которые можно перейти из состояний после третьего шага, если взять четвёртый предмет. Пз состояния 0(0) перейти можно в состояние 12(20). Оно попадает между состояниями 11(17) и 15(22) и логично занимает своё место (больше истраченный ресурс больше и суммарная стоимость). Но вот из состояния 4(7) попадаем в состояние 16(27). Оно попадает между возможными состояниями 15(22) и 18(25). Вот тут начинается самое интересное. Судьбу четырёх первых предметов можно решить так, чтобы при общем весе 16 (4+0+0+12) получить суммарную стоимость 27 (7+0+0+20). Спрашивается, следует ли далее рассматривать состояние 18(25), которое соответствует для четырёх предметов распределению ресурса (0+7+11+0) со стоимостями (0+10+15+0)? Состояние 18(25) бесперспективно и его можно исключить из дальнейшего рассмотрения вообще. Действительно, истратив всего 16 единиц грузоподъёмности вместо 18, всегда проще размещать оставшиеся предметы. Здесь мы сравниваем не варианты (пути) достижения конкретного состояния, а сами состояния, устанавливаем бесперспективность состояния 18(25) и исключаем его вместе со всеми его продолжениями.

В итоге после четвёртого шага получаем 13, а не 16 состояний: 0(0), 4(7), 7(10), 11(17), 12(20), 15(22), 16(27), 19(30), 22(32), 23(37), 27(42), 30(45) и 34(52). На пятом шаге решается вопрос брать или не брать пятый предмет весом 16 и стоимостью 27 единиц. Если не брать, то перейдём в те же 13 состояний. А если брать, то получим несколько новых.

Рассуждая как и ранее, установим бесперспективность состояний 22(32) (так как появится состояние 20(34)), а также бесперспективность состояний 27(42), 30(45) и 34(52). Некоторые переходы оказываются недопустимыми из-за превышения лимита грузоподъёмности (Q = 35). В итоге, после пятого шага останется для дальнейшего анализа только 15 (а не 32 и не 36) состояний: 0(0), 4(7), 7(10), 11(17), 12(20), 15(22), 16(27), 19(30), 20(34), 23(37), 27(44), 28(47),

31(49), 32(54) и 35(57). Соответственно и объём вычислений меньше, чем в рассмотренных выше способах решения задачи. Осталось решить брать или не брать шестой предмет весом 20 и стоимостью 34 единицы. Если не брать, то состояние 35(57) окажется наилучшим, а если брать, то можно получить 35(56). В остальном или превышен вес 35 или меньше суммарная стоимость. Результат: максимальная стоимость составляет 57. Если мы запоминали для каждого состояния связь с предыдущим шагом (брали или не брали соответствующий предмет), то обратным разворотом восстанавливаем какие предметы были взяты (второй, четвёртый и пятый).

В целом процесс выбора оптимального варианта представлен на рис. 4.2. Пунктиром показаны бесперспективные переходы. Оптимальный вариант показан жирной линией.

Схема поиска оптимального варианта

Рис. 4.2 Схема поиска оптимального варианта

Как отмечено в [6], для динамического программирования в отличие от полного перебора вариантов увеличение числа шагов не страшно: оно приводит только к пропорциональному возрастанию объёма расчётов. Это верно при фиксированном числе состояний на каждом шаге.

Значительно важнее сократить число этих состояний, что и демонстрирует приведенный нами алгоритм.

Если в данной конкретной задаче можно обойтись и без такого снижения числа состояний, так как имеется только два возможных перехода из каждого состояния, то в более сложных задачах, это обстоятельство весьма существенно.

Данный пример показателен в нескольких отношениях.

Во-первых, формализация понятия «состояние» может быть разной. Нет смысла вводить состояния, которые в принципе не достижимы. Так и число состояний и сами состояния на каждом этапе совсем не обязательно определять заранее, оно может определяться динамически. В [6] это число состояний определяется дискретностью поиска и равно числу дискретов в общей грузоподъёмности Q, что больше, чем общее число вариантов при полном переборе на пяти шагах. При увеличении Q число состояний к при такой формализации растёт (при том же дискрете), а число вариантов при полном переборе остаётся неизменным. Это число равно 2N, где N- число предметов. Если kN>2N (например, N=10, к=110), то приведенный в [6] алгоритм может быть менее эффективен, чем полный перебор.

Во-вторых, существенное значение для разработки алгоритма поиска оптимального решения имеет выбор направления: от начала к концу или наоборот.

В- третьих, специфические особенности этой (и не только этой!) задачи позволяют модифицировать метод динамического программирования и отбраковывать не только варианты достижения промежуточных состояний, но и сами бесперспективные промежуточные состояния. В этом и состоит смысл динамического программирования с использованием множеств Парето.

При наличии нескольких экземпляров одного и того же предмета никаких дополнительных сложностей не возникает. Просто из каждого промежуточного состояния рассматриваются не два, а более переходов (по числу имеющихся экземпляров рассматриваемого на данном шаге предмета).

В рассматриваемой задаче на каждом шаге наличие неизрасходованного ресурса (запас) никак не может помешать осуществлять в дальнейшем точно такой же выбор, как и при меньшем количестве ресурса. Это и означает, что из состояния В (лучшего и по стоимости и по ресурсу, чем состояние А) всегда можно пройти в конечную точку с той же эффективностью, что и из состояния А (движение по параллельной траектории). Напомним, что оценка каждого из состояний соответствует оптимальному пути из начальной точки, который приводит в это состояние.

К сожалению, если невозможно на всех дальнейших шагах принимать в точности те же решения (управления) независимо от состояния на некотором шаге, то отбраковка состояний не всегда достаточно проста.

Отметим, что отбраковка состояний в задаче распределения ресурса стала возможной потому, что мы отказались от постоянного шага (дискретности) и перешли к формированию состояний в процессе решения задачи.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>