Глава 25. Путь с максимальной суммой в числовом треугольнике :: Идеи реализации

Идеи реализации
	Глава 25. Путь с максимальной суммой в числовом треугольнике

Идеи реализации

Метод грубой силы

Нетерпеливые люди конечно же захотят организовать перебор всех возможных путей, ведущих от вершины треугольника к числам в нижнем ряду. Прежде чем программировать такой перебор, давайте подсчитаем пути. Каждый путь, дошедший до $k$ -й строки треугольника, можно продолжить до $(k + 1)$ -й строки ровно двумя способами: шагнув или влево, или вправо. Так что с возрастанием количества строк число путей растёт в геометрической прогрессии, увеличиваясь с каждой новой строкой в два раза. Для треугольника с $n$ строками потребуется $n - 1$ шаг, поэтому число возможных путей равно $2^{n - 1}$ . После пары десятков строк количество вариантов достигнет десятков миллионов, и тут метод полного перебора (метод грубой силы) утратит всю свою брутальную привлекательность.

Всё же разберём этот метод, поскольку он по-своему интересен.

Если каждый шаг вниз и влево кодировать нулём, а вниз и вправо — единицей, путь будет кодироваться последовательностью нулей и единиц. Такие последовательности, как мы знаем, находятся во взаимно-однозначном соответствии с целыми неотрицательными числами (одним из возможных соответствий является запись числа в двоичной системе). Поэтому перебор путей в треугольнике c $n$ строками — это в сущности перебор не более чем $(n - 1)$ -значных двоичных чисел, то есть чисел в диапазоне $0 ‥ 2^{n} - 1$ . Таким образом, следует перебирать целые неотрицательные числа из указанного диапазона. Каждое число разбирается на двоичные цифры (это удобно делать начиная с младших цифр). Пользуясь последовательностью цифр как маршрутом в треугольнике, суммируем встречающиеся числа. Для получившейся последовательности сумм индуктивно находим максимум.

Рекурсивное решение

Пронумеруем строки треугольника индексами $j$ , а числа в каждой строке — индексами $i$ , $0 ⩽ j ⩽ n$ , $0 ⩽ i ⩽ j$ . Обозначим число, стоящее в треугольнике в $j$ -й строке и на $i$ -м месте как $t_{j, i}$ . Заметим, что в типичном случае маршрут может придти к числу $t_{j, i}$ из двух чисел, расположенных на предыдущей строке: $t_{j - 1, i - 1}$ и $t_{j - 1, i}$ . Исключение составляют числа, стоящие на правой и левой сторонах треугольника, соответственно $t_{j, 0}$ (в него ведёт единственный путь из $t_{j - 1, 0}$ ) и $t_{j, j}$ (из $t_{j - 1, j - 1}$ ).

Разберём по отдельности все три случая. Введём обозначение $m_{j, i}$ для максимальной суммы среди всех путей, ведущих к числу $t_{j, i}$ .

если $i = j = 0$ , то $m_{j, i} = t_{j, i}$ ;
если $0 < i < j$ , то, очевидно, $m_{j, i} = t_{j, i} + \max (m_{j - 1, i - 1}, m_{j - 1, i})$ ;
если $i = 0$ , то $m_{j, 0} = t_{j, 0} + m_{j - 1, 0}$ ;
если $i = j$ , то $m_{j, j} = t_{j, j} + m_{j - 1, j - 1}$ .

Эти выражения означают, что вычисление $m_{j, i}$ сводится к вычислению значений $m_{j - 1, i - 1}$ и $m_{j - 1, i}$ (или в особых случаях одного из них). Напрашивается рекурсивное решение, в котором вычислению $m_{j, i}$ посвящена отдельная процедура. Ответом в задаче будет максимальное из чисел $m_{n, i}$ ( $n$ — номер последней строки треугольника, $0 ⩽ i ⩽ n$ ).

Чтобы не разбирать отдельно особые случаи (когда элемент $m_{j, i}$ находится на левой или правой границе треугольника и не имеет левого или правого верхнего соседа), положим $m_{j, i} = - \infty$ , если $i < 0$ или $i > j$ . Тем самым мы сделаем те пути, которые пытаются выйти за пределы треугольника, абсолютно непривлекательными с точки зрения вычисляемой вдоль них суммы. Они заведомо не выдержат конкуренции с путями, поворачивающими в другую сторону, что нам, собственно, и нужно.

Рекурсия с мемоизацией

Рекурсивное решение имеет свои недостатки. Во-первых, глубина рекурсивных вызовов достигает числа строк в треугольнике, а Perl, как мы знаем, нервно относится к глубокой рекурсии. Второй недостаток, гораздо более существенный, связан с тем, что рекурсивная процедура вызывается многократно для вычисления $m_{j, i}$ для одних и тех же $j$ , $i$ . Например, для треугольника на рисунке мы заставили процедуру выводить на экран числа $(j, i)$ , для которых она вызывается. Получилась такая последовательность вызовов: $(3, 0)$ , $(2, 0)$ , $(1, 0)$ , $(0, 0)$ , $(3, 1)$ , $(2, 0)$ , $(1, 0)$ , $(0, 0)$ , $(2, 1)$ , $(1, 0)$ , $(0, 0)$ , $(1, 1)$ , $(0, 0)$ , $(3, 2)$ , $(2, 1)$ , $(1, 0)$ , $(0, 0)$ , $(1, 1)$ , $(0, 0)$ , $(2, 2)$ , $(1, 1)$ , $(0, 0)$ , $(3, 3)$ , $(2, 2)$ , $(1, 1)$ , $(0, 0)$ . Видно, что для каждой пары процедура вызывается в среднем по $2,6$ раза. Аналогичный анализ для треугольника с пятнадцатью строками показывает, что для каждой пары процедура вызывается в среднем примерно $546$ раз. Количество избыточных повторных вызовов катастрофически растёт с увеличением размеров треугольника.

Тут нам на помощь приходит мемоизация. Будем хранить в памяти, помимо самого треугольника $t_{j, i}$ , ещё и таблицу $m_{j, i}$ . При вызове процедуры с параметрами $(j, i)$ ищем первым делом число $m_{j, i}$ в таблице, и, если находим, тут же возвращаем его. И уж если ячейка таблицы пока ещё не заполнена, только в этом случае вычисляем её, прибегая к рекурсивным вызовам, а вычислив, возвращаем.

Индуктивное решение

Все предыдущие решения имеют ещё один недостаток, помимо уже упомянутых. В каждом из них необходимо перед началом вычислений держать в памяти весь треугольник $t_{j, i}$ (а в решении с мемоизацией ещё и $m_{j, i}$ ).

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

Та функция, вычислению которой посвящена программа, не является индуктивной, однако можно построить индуктивное расширение. Это функция, вычисляющая таблицу $s_{i}$ . Так мы обозначим максимальную из сумм вдоль всевозможных путей, ведущих из вершины треугольника к $i$ -му числу в его последней строке, $0 ⩽ i ⩽ n$ . Ясно, что искомая функция вычисляется, если известны значения $s_{i}$ , как наибольшее из них: $f (ω) = \max_{0 ⩽ i ⩽ n} s_{i} (ω)$ .

Убедиться в индуктивности функции $s_{i}$ позволяют формулы перевычисления. Пусть $r_{i}$ — очередной ряд чисел из треугольника. Тогда $s_{i} (ω ∟ r_{i}) = r_{i} + \{\begin{cases} s_{i} (ω) & при i = 0, \\ \max (s_{i - 1} (ω), s_{i} (ω)) & при 0 < i < n, \\ s_{i - 1} (ω) & при i = n \end{cases}$ (здесь $n$ — количество элементов в новой строке треугольника, и, заодно, номер этой строки).


Глава 25. Путь с максимальной суммой в числовом треугольнике		Разработка

Информатика-54© А. Н. Швец