litceysel.ru
добавить свой файл
1

гимназия «Дмитров» –  из  – 16.11.2010



Информатика и ИКТ


План урока

11 класс



Принцип динамического программирования
на примере одной задачи



учитель Выдра Валерий Анатольевич


Используемые технологии


  • компьютерная технология;

  • технология ТРИЗ (теория решения изобретательских задач).


Сверхзадача урока


  • развить у учеников нестандартное мышление;

  • побудить к поиску эффективных решений;

  • научить решать «нерешаемые» задачи.


Цель урока


  • научить отыскивать в задаче (проблеме) противоречия и разрешать их;

  • научить учеников формулировать идеальное решение задачи;

  • научить подбирать ресурсы для разрешения противоречий;

  • сформировать умение анализировать решение задачи с точки зрения получения идеального результата.


План урока


  • возобновление базовых операций работы с массивами;

  • повторение основных приёмов работы с процедурами и функциями;

  • повторение механизма рекурсии;

  • повторение метода решения задач «перебор с возвратом»;

  • постановка задачи;

  • решение методом «перебор с возвратом»;

  • разбор решения, определение недостатков;

  • решение методом динамического программирования;

  • анализ решения;

  • подведение итогов.


Ход урока


  • опрос учеников по основным понятиям темы «массивы»;

  • опрос по теме процедуры и функции;

  • опрос учеников по методу решения задач «перебор с возвратом»;

  • постановка задачи;

  • решение методом «перебор с возвратом»;


  • разбор недостатков в решении;

  • решение методом динамического программирования;

  • набор программы на компьютере;

  • анализ решения;

  • выдача домашнего задания.



Опрос


  • какие основные операции с массивами существуют?

  • что такое процедура (функция)?

  • какая необходимость использования процедур (функций)?

  • что такое рекурсия?

  • каков механизм рекурсии?

  • в чём заключается принцип «перебора с возвратом»?

  • какой класс задач поддаётся решению с помощью перебора с возвратом?



Задание


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


Пример:


N
=3, K=2

Возможные пути: 1,1,1

1,2

2,1

Ответ: 3




3




2




1










Задача довольно просто решается с помощью метода «перебор с возвратом» (backtracking).

Ещё раз вспоминаем:

  • что такое перебор с возвратом?
  • с помощью какого программного приёма обычно осуществляется «перебор с возвратом»? (с помощью рекурсии).


Итак, мы находимся в данный момент в клетке с номером i
. Из неё мы можем пойти в клетки i+1, i+2, … i+k. Из тех клеток мы можем попасть в соответствующие для них наборы клеток. Таким образом можно осуществить рекурсивное движение (до конца поля). Стало быть нужна процедура, которая прежде всего определяет, достигли мы конца поля или нет. Если достигли, то считаем этот вариант и выходим из процедуры (откатываемся на шаг назад). Если не достигли, делаем следующий шаг (рекурсивно вызываем процедуру для следующей клетки). Процедура закончит свою работу, когда будут исчерпаны все варианты.

Программный код процедуры:


procedure go(i:integer); {в i - текущий номер поля с фишкой}

var j:integer; {j - длина очередного хода фишки}

begin

if i=n then inc(c) {считаем вариант, если дошли до конца поля}

else

for j:=1 to k do

if i+j<=n then go(i+j); {генерация след. варианта}

end;


Получаем удовлетворительное решение. Удовлетворительное, потому что оно даёт правильный результат. Однако, вполне ли оно удовлетворительно? Попробуем запустить задачу с параметрами N=30, K=11. Компьютер задумается... При входных данных N=30, K=15 – прочно подвиснет. Почему? Ведь это отнюдь не такие большие данные! Попробуем разобраться.

Не лукавя, встанем на рельсы технологии ТРИЗ – теории решения изобретательских задач. Задачу ведь можно отнести к классу изобретательских (в ней надо что-то улучшить).

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


Прежде чем попытаться разрешить это противоречие, давайте определимся, что мы в конечном итоге хотим получить? Мы хотим получить правильное решение за приемлемое время, причём для всех входных данных, а не только для маленьких. Разрешимо ли это противоречие? Разрешимо. Но для этого мы применим совсем другой подход к решению. Мы не будем генерировать пути, так как этого в задаче совсем не требуется, но именно на это уходит львиная доля времени. Мы количество попаданий в конечную клетку будем определять через количества попаданий в предыдущие клетки. Не генерировать новые пути, а работать только с количествами попаданий в каждую клетку. Это принципиально. Таким образом, мы одним махом избавимся от всех повторных пересчётов.

Перейдём на язык формул. В некую клетку i фишка может попасть только из k предыдущих клеток. Тогда, если число попаданий в каждую из этих клеток обозначить через s[i-1], s[i-2], … s[i-k], то число попаданий в клетку i будет равно сумме этих значений. Просто при этом каждый путь в эти клетки удлинится ещё на один ход фишки (а именно в клетку i). Если номер клетки i меньше k, то к сумме попаданий фишки в предыдущие клетки добавится ещё единица (прямой ход в клетку i). Вот и всё.

Программный код будет выглядеть так:


a[1]:=1; {число вариантов для первой клетки}

for i:=2 to n do {заполнение динамической таблицы}

if i<=k then begin {пока длина хода меньше k}

a[i]:=1;

for j:=1 to i-1 do a[i]:=a[i]+a[j];

end

else begin {длина хода больше k}

a[i]:=0;

for j:=i-k to i-1 do a[i]:=a[i]+a[j];

end;

writeln(a[n]); {печать результата}


Анализ решения

Проанализируем решение. Для хранения промежуточных результатов нам потребуется массив (линейный, размер N). В первую клетку ставим единицу (количество попаданий в первую клетку), далее в каждую клетку (элемент массива) записываем сумму k предыдущих клеток (кроме k первых клеток). Таким образом решение задачи сводится к элементарному заполнению таблицы. Объём вычислений пропорционален размеру поля N. Время решения при этом будет приемлемым даже для значительных входных данных.



Итог


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


Творческое домашнее задание


Найти какие-либо другие варианты решения задачи, помимо разобранных на уроке.


г.Дмитров, ул. Инженерная 24а тел 8(496)223-56-50