Обучающая программа «Bellman»

Для освоения метода динамического программирования, иллюстрации его возможностей и условий применимости разработана специальная обучающая компьютерная программа «Bellman».

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

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

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

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

Программа не предъявляет высоких требований к объему оперативной памяти компьютера и его быстродействию и может использоваться практически на любой персональной ЭВМ.

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

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

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

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

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

Вначале программа предлагает пользователю убедиться в бесперспективности метода полного перебора при поиске оптимального пути на двумерной сетке. Она формулирует задачу, задает несколько простых вопросов на понимание ее условия и особенностей и предлагает пользователю вопрос о количестве путей из точки А в точку В, т.е. о числе вариантов, из которых предстоит сделать выбор при полном переборе вариантов. Это число определяется размерами сетки тип. Пользователю предъявляются несколько формул для расчета числа вариантов, в частности mn, (m+n)!/(m!+n!), (m+n)!/(m!n!) и др. Для правильного ответа на этот вопрос нужно уяснить, что каждому варианту пути из точки А в точку В соответствует ровно m шагов по вертикали и ровно п шагов по горизонтали, но последовательность этих шагов для каждого пути своя. Если шагу по горизонтали соответствует 0, а шагу по вертикали 1, то очевидно, что вариант пути — это выбор размещения ш единиц по ш+п местам (оставшиеся п мест займут нули). Для размещения первой единицы имеется ш+п возможностей, для второй ш+п-1 и т.д. В итоге получаем формулу с факториалами (m+n)!/(m!n!).

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

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

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

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

Начальный вариант соответствует последовательности из ш единиц и п нулей, при этом на экране зеленой линией обведены левая вертикальная и верхняя горизонтальная границы сетки. Например, для сетки 4x4 начальная последовательность 11110000.

Первая серия вариантов соответствует перемещению последней единицы вправо, т.е. зеленая линия имеет один уступ, который смещается вправо (рис. П1.1)

В течение обработки всей первой серии вариантов вертикальная зеленая линия совпадает с левой вертикальной границей сетки.

П 1,1. Первая серия вариантов

Рис. П 1,1. Первая серия вариантов

Вторая серия вариантов соответствует переходу от последовательности 11011000 к последовательности 11010001. Третья серия— это переход от 11001100 к 11001001 и т.д. Левая зеленая вертикальная линия укорачивается только после перебора всех вариантов, не требующих ее изменения. Если на экране присутствует вертикальная зеленая линия где-то в левой части сетки, то до конца расчета еще далеко, так как в конце рассматриваются последовательности от 00011110 до 0000111 (рис. П 1.2), т.е. вертикальная часть зеленой линии присутствует только на предпоследней и последней вертикали сетки.

П 1.2. Последняя серия вариантов

Рис. П 1.2. Последняя серия вариантов

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

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

Сделав вывод о нецелесообразности использования метода полного перебора, программа задает вопрос о применимости простой идеи, а именно: из каждого узла идти в соседний с наименьшими затратами, не думая о последствиях, т.е. смотреть только на один шаг вперед. Эта идея отвергается.

Далее программа разъясняет принцип оптимальности Р. Веллмана и соответствующий алгоритм решения данной задачи.

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

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

В итоге программа сообщает количество верных и неверных ответов суммарно по всем вопросам с учетом всех попыток ответа.

Контрольные вопросы

  • 1. В задаче поиска оптимального пути на двумерной сетке в качестве целевой функции приняли сумму шаговых затрат плюс количество изменений направления (поворотов), умноженное на заданное число, т.е. штраф за повороты. Можно ли использовать для поиска оптимального пути при такой целевой функции метод динамического программирования, и если да, то как?
  • 2. Если в задаче поиска оптимального пути на двумерной сетке ограничено число поворотов, а варианты, сходящиеся в одном узле, считаются сравнимыми, то возможна ли ситуация «вырождения вариантов», т.е. остановка процесса поиска из-за исчерпания лимита поворотов?
  • 3. Если для решения некоторой вариационной задачи поиска оптимальной плоской кривой (экстремали) используется модель поиска оптимального пути на двумерной сетке, то можно ли утверждать, что отклонение от оптимума (максимальная разность ординат), обусловленное искусственным введением дискретности, не превышает шага сетки?
  • 4. Если для решения задачи поиска оптимальной кривой искусственно вводится дискретность и разбивается сначала крупная, а затем мелкая сетка, то как могут повлиять на выбор шага сетки свойства целевой функции, наличие и конкретный вид ограничений на искомую кривую?
  • 5. Можно ли утверждать, что наличие локальных экстремумов не существенно при использовании метода динамического программирования?
  • 6. В задаче поиска оптимального пути на двумерной сетке в качестве целевой функции приняли не сумму шаговых затрат, а логарифм (натуральный) этой суммы. Можно ли решить задачу поиска оптимального пути с такой целевой функцией по методу динамического программирования?

Приложение 2.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >