Треугольник

Задача о Черепашке

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

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

Черепашке необходимо попасть из пункта А в пункт В. На каждом углу она может поворачивать только на север или только на восток. Время движения по каждой улице указано на рисунке. Требуется найти минимальное время, за которое Черепашка может попасть из пункта А в пункт В.

Путь, показанный на рисунке линиями со стрелкой, требует 21 единицу времени. Отметим, что каждый путь состоит из 6 шагов: трех на север и трех на восток. Количество возможных путей Черепашки 20 (С63 ). Мы можем перебрать все пути и выбрать самый быстрый. Это метод полного перебора (ответ - 21). Для вычисления каждого времени требуется пять операций сложения, а для нахождения ответа 100 операций сложения и 19 операций сравнения. Задача решается вручную. Однако при N, равном 8, у Черепашки уже 12870 путей. Подсчет времени для каждого пути требует 15 операций сложения, а в целом - 193050 сложений и 12869 сравнений, то есть порядка 200000 операций. Компьютер при быстродействии 1000000 операций в секунду найдет решение за 0.2 секунды, а человек? Предположим, что N равно 30, тогда количество различных путей 60!*(30!*30!). Это очень большое число, его порядок 1017. Количество операций, необходимых для поиска решения, равно 60*1017. Компьютер с быстродействием 1000000 операций в секунду выполнит за год порядка 3.2*1013 операций (подсчитайте). А сейчас не трудно прикинуть количество лет, требуемых для решения задачи.

Вернемся к исходной задаче. Начнем строить путь Черепашки от пункта В. Каждому углу присвоим вес, равный минимальному времени движения Черепашки от этого угла до пункта В. Как его находить? От углов X, Y очевидно. Для угла Z время движения Черепашки в пункт В через угол X 15 единиц, а через угол Y 11 единиц. Берем минимальный, то есть вес угла будет равен 11. Продолжим вычисления. Их результаты приведены на рисунке. Путь, отмеченный стрелками, является ответом задачи. Оценим количество вычислений. Для каждого угла необходимо выполнить не более двух операций сложения и одной операции сравнения, то есть три операции. При N, равном 300, количество операций - 3*301*301, это меньше 1000000, и компьютеру потребуется меньше одной секунды. Итак, много лет при N=30 и 1 секунда при N=300.

Идея второго способа решения задачи основана на методе динамического программирования. Заслуга его открытия принадлежит американскому математику Ричарду Беллману. Выделим особенность задачи, которая позволяет решить ее описанным способом. Мы начинаем с угла В, и для каждого угла найденное число является решением задачи меньшей размерности. Поясним эту мысль. Если бы мы решали задачу поиска пути Черепашки из пункта Т в пункт В, то найденное число 17 - решение задачи. Для каждого угла найденное значение времени не изменяется и может быть использовано на следующих этапах.

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

               
             
           
         
       

· Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.

· Число строк в треугольнике > 1 и <100.

· Треугольник составлен из целых чисел от 0 до 99.

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

 

 

7 0 0 0 0 3 8 0 0 0 8 1 0 0 0 2 7 4 4 0 4 5 2 6 5

Будем вычислять матрицу R:array[1..MaxN,0..MaxN+1] следующим образом, предварительно обнулив ее элементы:

R[1,1]=D[1,1]

R[i,j]=max(D[i,j]+R[i-1,j],D[i,j]+R[i-1,j-1])

для i=2..N; j=1..i.

Ее вид:

0 7 0 10 15 0 18 16 15 0 20 25 20 19 0 24 30 27 26 24

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