Название: Алгоритмы - Учебное пособие ( Редактор )

Жанр: Экономика

Просмотров: 1716


2. 3. динамическое программирование

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

 

Таким образом, динамическое программирование следует применять, если задача удовлетворяет следующим условиям:

оптимальность для подзадач: будем говорить, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальное решение ее подзадач;

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

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

2.3.1. Волновой алгоритм

Изменим формулировку задачи о лабиринте. Пусть нам требуется найти кратчайший по количеству перемещений путь. В этом случае  и применим «метод волны», суть которого в следующем. Начальную клетку помечают, например, меткой со значением 1, а затем значение метки увеличивается на каждом шаге. Очередное значение метки записывается в свободные клетки, соседние с клетками, размеченными на предыдущем шаге. В любой момент времени множество клеток, не занятых препятствием, разбивается на три класса: помеченные и изученные (окрасим их темно-серой краской); помеченные и неизученные (окрасим их серой краской); и непомеченные (эти клетки будут белыми). Для хранения клеток серого цвета лучше всего использовать структуру данных «очередь». Программа заканчивается в двух случаях: при достижении клетки выхода из лабиринта (это означает, что выход из лабиринта найден) или при невозможности разметить очередную клетку (попадание в тупик), а очередь пуста (это означает, что выход из лабиринта не найден). Начальная клетка находится вверху слева, конечная – внизу справа.

Этот процесс показан на рис. 2.6.

Темно-серые клетки – это уже обработанные клетки, серые клетки – еще не обработанные, стоящие в «очереди». Метки в этих клетках определяют кратчайший путь из начальной клетки с координатой 1,1. Белые – еще не обработанные клетки, расстояние до которых не определено.

 

   

Шаг 1  Шаг 2  Шаг 3  Шаг 4

 

                             

Шаг 5  Шаг 6  Шаг 7

 

                              

Шаг 8  Шаг 9  Шаг 10

 

Рис. 2.6

Алгоритм

1  Volna (Iвх, Jвх, Iвых, Jвых )

2  Метка ¬ 1

3  Лабиринт[Iвх, Jвх] ¬ 1

4  Очередь(Iвх, Jвх)    /*  помещаем в очередь координаты клетки – входа в лабиринт */

5  while очередь не пуста , и не найдено решение do

6  I, J ¬Очередь      /* читаем из очереди координаты очередной клетки */

7    if (I=Iвых и J=Jвых) /* координаты клетки выхода из лабиринта */

8    решение найдено

9    else for (всех соседей клетки Лабиринт[I,J] )

10   if (сосед – белая клетка )

11     сосед ¬ Лабиринт[I,J] +1  /* вычисляем новое значение метки и присваиваем его всем соседям */

12   Очередь (координаты соседей клетки Лабиринт[I,J]) /* помещаем координаты соседей в очередь */

13   fi /* конец внутреннего оператора if */

14                                                        od  /* конец цикла for */

15   fi /* конец внешнего оператора if */

16                                                         od /*конец цикла while */

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

2.3.2. Примеры задач, иллюстрирующие метод

динамического программирования

Задача о черепашке. Разбор основной идеи метода и ее обсуждение можно сделать на классической задаче о черепашке. Черепашке необходимо попасть из пункта А в пункт В, двигаясь по клеточному полю. Находясь в текущей клетке, черепашка может двигаться только на север или на восток. Время движения в каждом направлении указано на направляющих стрелках (рис. 2.7).

 

а    б

Рис.  2.7

 

Требуется найти минимальное время, за которое черепашка попадает из пункта А в пункт В. Если каждый перекресток в городе представить вершиной, а направления движения черепашки – дугами, то получим размеченный граф G(V, D, M).

Количество вершин графа – 16. Множество вершин – это углы таблицы (рис. 2.8), пронумерованные следующим образом : угол А будет иметь номер 1, а угол В – номер 16. Остальные углы можно пронумеровать произвольным порядком.

D – множество дуг графа. Каждая вершина графа, если она не лежит на границе таблицы, имеет две входящих и две выходящих дуги. М – множество меток, размечающих дуги. В нашем случае – это расстояния от одного угла до другого. 

Путь, отмеченный жирными стрелками, (см. рис 2.7) требует 21 единицу времени. Количество возможных путей черепашки 20(С36 ), так как любой путь черепашки из пункта А в пункт В состоит из шести шагов: трех на север и трех на восток. Если решать эту задачу методом полного перебора, то потребуется выполнить 100 операций сложения (5 × 20) и 19 операций сравнения, чтобы выбрать самый быстрый путь. Задача данной размерности решается вручную. Однако при N = 8, у черепашки уже 12870 путей. И здесь уже понадобится 193050 (15 × 12870) операций сложения и 12869 сравнений, т. е. порядка 200 000 операций. Компьютер при быстродействии 1000000 операций в 1 с найдет решение за 0,2 с. Сможет ли человек вручную найти решение? Предположим, что N = 30, тогда количество различных путей 60! × 30! × 30!. Это очень большое число, его порядок 1017. Количество операций, необходимых для поиска решения полным перебором, равно 60 × 1017. Наш компьютер с быстродействием 1 000 000 операций в 1 с за год может выполнить 3,2 × 1013 операций. Нетрудно определить, сколько лет потребуется компьютеру для решения этой задачи такой размерности.

Идея динамического программирования состоит в том, чтобы запоминать минимальное время, за которое черепашка может добраться до каждого угла, двигаясь из угла А (в нашей таблице) см. рис. 2.8 (углу А присвоен номер 1). Начнем строить

 

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

1

0

3

 

 

 

 

 

4

 

 

 

 

 

 

 

 

2

 

0

2

 

 

 

5

 

 

 

 

 

 

 

 

 

3

 

 

0

5

 

3

 

 

 

 

 

 

 

 

 

 

4

 

 

 

0

5

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

0

 

 

 

 

 

 

7

 

 

 

 

6

 

 

 

 

6

0

 

 

 

 

2

 

 

 

 

 

7

 

 

 

 

 

4

0

 

 

7

 

 

 

 

 

 

8

 

 

 

 

 

 

2

0

6

 

 

 

 

 

 

 

9

 

 

 

 

 

 

 

 

0

5

 

 

7

 

 

 

10

 

 

 

 

 

 

 

 

 

0

5

 

 

 

9

 

11

 

 

 

 

 

 

 

 

 

 

<\/a>") //-->