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

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

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


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

Многоэтапные процессы принятия решений

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

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

Основная идея, которая привела к созданию вычислительного метода, была сформулирована в начале 50-х годов прошлого века Р. Веллманом (R. Bellman), сделавшим самый большой вклад в развитие метода, который он назвал «динамическое программирование» [3], но который чаще называют просто метод Веллмана.

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

Реализация метода для каждого конкретного многошагового процесса принятия решений, как правило, требует разработки нового алгоритма. Многие практические задачи, которые можно решать с помощью этого метода, были рассмотрены его автором совместно с Дрейфусом (S. Dreyfus) [4].

Первоначально метод предлагался для решения сравнительно узкого класса задач, возникающих в процессах, которые развиваются во времени. Отсюда и название: динамическое программирование, причём слово программирование скорее означало планирование, чем разработку компьютерных программ. Фактически этот метод, как и симплекс- метод Данцига для решения задач линейного программирования, был разработан на заре «компьютерной эры», то есть до массового применения вычислительной техники. Тогда слово «programming» на русский язык переводилось как планирование, и метод Р. Веллмана первоначально назывался динамическое планирование. Через некоторое время после появления первых работ Р.Веллмана выяснилось, что для многих задач, которые не являются многоэтапными в явном виде, эту многоэтапность можно организовать искусственно и применить метод Веллмана.

Для изложения основной идеи метода рассмотрим сначала простую задачу поиска оптимального пути на двумерной прямоугольной сетке, в которой разрешены переходы из одного узла в другой только по горизонтали (вправо) или по вертикали (вверх). Заданы затраты на каждый из возможных переходов и требуется найти путь с минимальными суммарными затратами из левого нижнего угла сетки (рис. 3.1 точка А) в правый верхний угол (точка В). Такой путь называется оптимальным. Узлы сетки пронумерованы так, как показано на рис. 3.1, где шип задают соответственно вертикальный и горизонтальный размеры сетки (число шагов по вертикали и горизонтали соответственно).

Затраты на переход в узел i, j по горизонтали (из узла i, j-1) обозначим gij, а по вертикали (из узла i-1, j) - Vij. В точке А соответствующие величины равны нулю. Таким образом, исходными данными в этой задаче являются: m, п и все шаговые затраты gy и vy. (i = 0,1,2,..., m; j = 0,1,2, ..., n). Всего n(m+l) чисел gy и m(n+l) чисел vy, то есть всего 2mn+m+n переходов и соответствующих им затрат.

При небольших размерах сетки можно попытаться решить задачу методом полного перебора вариантов возможных путей из точки А в точку В. Однако эта идея абсолютно бесперспективна уже при величинах m и п в несколько десятков из- за резкого роста числа вариантов возможных путей из точки А в точку В с увеличением размеров сетки.

Пример задачи поиска оптимального пути

Рис. 3.1. Пример задачи поиска оптимального пути

Действительно, каждому варианту пути из точки А в точку В соответствует ровно ш шагов по вертикали и ровно п шагов по горизонтали, но последовательность этих шагов для каждого варианта своя. Если шагу по горизонтали поставить в соответствие 0, а шагу по вертикали 1, то очевидно, что вариант пути

- это выбор размещения m единиц по ш+п возможным местам (оставшиеся п мест займут нули). Для размещения первой единицы имеется ш+п возможностей, для второй - ш+п-1 возможностей и т.д. В итоге получаем формулу для числа вариантов пути N.

Уже при

Следующая идея состоит в том, чтобы из точки А идти в том направлении, которое требует минимальных затрат на первом шаге (первый ход), не думая о затратах на последующих шагах, и так в каждой точке. То есть рассматривать только затраты на данном шаге и выбирать тот переход, для которого на данном шаге затраты минимальны. Легко убедиться в ошибочности этой идеи даже при m-n-1 (рис. 3.2).

Действительно, если первый шаг выбрать по вертикали в точку С (затраты 2 против 7), то в итоге после второго шага получим суммарные затраты равные 12, а при выборе на первом шаге «неоптимального» решения (точка D) суммарные затраты равны всего лишь 8.

Оптимальный путь ADB, а не АСВ

Рис. 3.2. Оптимальный путь ADB, а не АСВ

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

Поиск оптимального пути можно рассматривать как многошаговый процесс. На первом шаге находимся в точке А и имеем две возможности: пойти вверх или направо. Мы убедились на рассмотренном примере (рис. 3.2), что сделать выбор нельзя, так как нужно учитывать последствия этого выбора. При любом выборе попадём мы в точку (0,1) или (1,0), встанет та же задача выбора из двух возможностей и опять выбор сделать нельзя и т.д. Однако, существуют точки, в которых нет выбора. Эти точки С и D находятся в одном шаге от последней точки В и имеют координаты (ш,п-1) и (m-l,n) (рис. 3.3).

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

Выбор на последних шагах

Рис. 3.3. Выбор на последних шагах

На рис. 3.3 это 10 для точки Е и 8 для точки G. А что делать, если мы в двух шагах от финиша окажемся в точке F? Ответ кажется простым: надо идти в точку С, а не в точку D, так как несмотря на то, что на предпоследнем шаге затраты больше (2 против 1), но с учётом затрат на оставшийся путь (4 против 7) суммарные затраты на путь до точки В окажутся меньше (6 против 8). Конечно из точки F надо идти в точку С, но при одном непременном условии: ничто не может помешать нам это сделать, нет никакой связи с тем, как мы попали в данную точку или как говорят нет «предыстории». В нашей задаче такой связи нет, но в более сложных задачах она вполне возможна. Например, могло быть задано дополнительное условие: суммарное количество изменений направления (поворотов) не больше заданного числа. Тогда мы, во-первых, должны знать сколько было сделано поворотов до попадания в точку F, и каким образом (по горизонтали или по вертикали) мы попали в эту точку, то есть должны знать предысторию. Может оказаться, что мы попали в точку F по горизонтали и уже исчерпали заданный «лимит» поворотов, тогда переход из точки F в точку С просто невозможен, так как это уже лишний поворот. Получается, что сделать оптимальный выбор в точке F нам может помешать предыстория.

Продолжим поиск оптимального пути в нашей задаче, в которой таких осложнений нет, и предыстория не имеет значения. В точке F мы запомним затраты на весь оставшийся путь при условии, что выбран оптимальный вариант: переход в точку С. Сделав ещё шаг назад, то есть оказавшись за три шага до финиша, мы увидим, что ситуация полностью аналогична предыдущей. Выбора или нет (точки на крайней верхней или крайней правой стороне сетки) или есть две возможности, но для каждой из них уже известны последствия выбора. Так, оказавшись в точке М, мы выберем не точку F, для которой затраты до конца пути равны 6, а казавшуюся бесперспективной точку Е, для которой эти затраты равны 10, но суммарные затраты на весь оставшийся путь меньше (13 против 14). При этом выборе мы решаем совсем простую задачу: суммируем затраты на каждый из возможных переходов на данном шаге (в точку Е или в точку F) с уже известными затратами на дальнейший путь по оптимальному для выбранной точки варианту. Поступая аналогичным образом, мы рано или поздно в своём обратном движении придём в начальную точку А (рис. 3.4). Но при этом уже будут известны последствия для каждого из вариантов выбора (пойти по вертикали в точку К или по горизонтали в точку L), так как для каждой из них уже вычислены и записаны затраты на весь оставшийся путь до точки В. Это ситуация аналогична той, что представлена на рис. 3.4.

Выбор на первом шаге

Рис. 3.4. Выбор на первом шаге

Теперь ничто не мешает нам сделать выбор, куда идти из точки А. Просуммируем затраты из А в К с тем, что записано для точки К на весь оставшийся путь от К до В. Затем просуммируем затраты из А в L с тем, что записано для L на путь из L в В и выберем наименьшую из сумм, которая и будет равна суммарным затратам по оптимальному пути. В примере на рис. 3.4 получаем для точки К число 99, а для точки L 100 и, следовательно, теперь ясно, что идти надо в точку К. Но нам нужны не только эти минимальные из всех возможных затраты, но и сам оптимальный путь. Пока мы знаем куда идти из точки А на первом шаге. А дальше? Дальше знаем только затраты на весь оставшийся путь. Чтобы не оказаться в такой ситуации неопределённости, при записи затрат на оставшийся путь в каждой из промежуточных точек (C,D,E,F,G,M и т.д.

рис. 3.3) нужно записывать и сделанный выбор: куда идти из этих точек. Если это сделано, то при выборе из точки А куда идти: в точку К или L, в любой из них уже будет записано куда идти дальше (по вертикали или по горизонтали, то есть 1 или 0) и т. д. Обратным разворотом мы дойдём до точки В и восстановим оптимальный путь.

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

В данной задаче мы исследовали многошаговый процесс от последнего шага к первому. Но ничто не мешает развернуть его и рассмотреть шаги в прямом направлении, то есть от точки А к точке В, ничего не меняя в методе Р. Веллмана по существу.

Применительно к рассматриваемой нами задаче поиска оптимального пути на двумерной сетке алгоритм примет следующий вид.

  • 1. Из точки А делаем шаг в каждом из возможных направлений, запоминаем в точках К и L затраты и направление, по которому пришли в эту точку (0- по горизонтали и 1 по вертикали). Соответственно для точки К запомним 12 и 1, а для точки L 5 и 0.
  • 2. На втором и всех последующих шагах, кроме последнего, если в точку ведёт один путь (шаги по левой и нижней сторонам сетки), то просто запоминаем суммарные затраты на путь от начала и направление откуда пришли, а если в точке сходятся два варианта (на рис. 3.4 это точка Н, а на рис. 3.3 точки М, F и др.), то сравниваем две возможности: прийти в эту точку по горизонтали или по вертикали. Для каждой из них вычисляем суммарные затраты на путь от начала до данной точки, выбираем тот вариант, для которого эти суммарные затраты минимальны, запоминаем их и соответствующее им направление. Таким образом, происходит отбраковка вариантов, сходящихся в точке: вариант с наибольшими затратами отбрасывается и все его продолжения далее не анализируются. Естественно, это можно сделать только в таких простых задачах «без предыстории» как наша, когда совпадают множества возможных продолжений сравниваемых вариантов и отбраковка варианта никак не влияет на возможности выбора в дальнейшем.
  • 3. На последнем шаге в точку В ведут два направления и по каждому из них всё известно: для каждой точки (на рис. 3.3 это точки С и D) записаны затраты на весь путь от начала и направление откуда пришли в эту точку. Снова суммируем затраты по вариантам, выбираем наименьшие, а затем обратным разворотом восстанавливаем оптимальный путь.

В реальных задачах многоэтапные процессы могут иметь не один исход (точку финиша) или начало (точку старта), а несколько. Однако это не мешает применить метод Р. Веллмана.

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

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

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