Рецидивы и генерация функций в алгоритмах

Комбинаторика играет важную роль в информатике. Мы часто используем комбинаторные методы как в анализе, так и в алгоритмах. Например, один из методов нахождения покрытия графа вершины в графе может просто проверить все \ binom {n} {k} возможных подмножеств. В то время как биномиальные функции растут экспоненциально, если k является некоторой фиксированной константой, мы получаем алгоритм полиномиального времени с помощью асимптотического анализа.$k$$\binom{n}{k}$$k$

Часто реальные проблемы требуют более сложных комбинаторных механизмов, которые мы можем определить с точки зрения повторений. Один известный пример - последовательность Фибоначчи (наивно), определенная как:

$f(n) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n = 0 \\ f(n-1) + f(n-2) & \text{otherwise} \end{cases}$

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

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

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

К счастью, это решение в закрытой форме. Не все производящие функции допускают такое компактное описание.

Теперь мой вопрос заключается в следующем: как часто генерирующие функции используются при разработке алгоритмов? Легко понять, как их можно использовать для понимания скорости роста, требуемой алгоритмом посредством анализа, но что они могут сказать нам о проблеме при создании метода для решения какой-то проблемы?

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

Генерация функций полезна при разработке алгоритмов подсчета. То есть не только когда вы ищете количество объектов, имеющих определенное свойство, но и когда вы ищете способ перечислить эти объекты (и, возможно, сгенерировать алгоритм для подсчета объектов). В главе 7 « Конкретной математики » есть очень хорошая презентация Рональда Грэма, Дональда Кнута и Орен Паташник . Приведенные ниже примеры взяты из этих книг (ошибки и отсутствие ясности - мои).

Предположим, что вы ищете способы внести изменения с помощью данного набора монет. Например, с обычными номиналами в США¹ возможны монеты . Чтобы дать ¢ 42 в изменении, одна возможность - ; другая возможность - . Мы напишем . В более общем смысле, мы можем написать производящую функцию для всех способов изменения: В более технических терминах - это термин в пространстве степенных рядов над пятью переменными[ 25 ] [ 10 ] [ 5 ] [ 1 ] [ 1 ] [ 10 ] [ 10 ] [ 10 ] [ 10 ] [ 1 ] [ 1 ] 42 ⟨ [ 25 ] [ 10 $[1], [5], [10], [25], [100]$$[25][10][5][1][1]$$[10][10][10][10][1][1]$Н = Σ ч ≥ 0 Σ Q ≥ 0 Σ d ≥ 0 Σ п ≥ 0 Σ р ≥ 0 [ 100 ] ч [ 25 ] д [ 10 ] d [ 5 ] n [ 1 ] $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$

$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$ [ 100 ] , [ 25 ] , [ 10 ] , [ 5 ] , [ 1 ] ⟨ [ 100 ] ч [ 25 ] д [ 10 ] d [ 5 ] п [ 1 ] р ⟩ = 100 ч + 25 кв + 10 d + 5 n + p v v H $H$$[100], [25], [10], [5], [1]$, Определите оценку монома в этом пространстве как Тогда способы дать центов в изменении - это количество мономов, оценка которых . Мы можем выразить в инкрементной форме, сначала записав способы чтобы дать изменение только в копейках, затем способы чтобы дать изменение в пенни и никелях, и так далее. ( виду нет монеты.) $$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$ $v$$v$$H$$P$I P = I + [ 1 ] + [ 1 ] 2 + [ 1 ] 3 + … = $N$$I$ $$\begin{gather*} P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\ N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\ D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\ Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\ H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\ \end{gather*}$$ Если вы хотите сосчитать, а не просто перечислить способы внесения изменений, то существует простой способ использования полученных формальных рядов. Примените гомоморфизм коэффициент в представляет количество способов дать центов в смену. $$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100}$$ $X^v$$S(C)$$v$

Более сложный пример: предположим, что вы хотите изучить все способы разбиения прямоугольников на 2 × 1 домино. Например, существует два способа наложить прямоугольник 2 × 2, либо с двумя горизонтальными домино, либо с двумя вертикальными домино. Подсчет количества способов разбить прямоугольник довольно прост, но случай быстро становится неочевидным. Мы можем перечислить все возможные наклоны горизонтальной полосы высотой 3, склеив домино вместе, что быстро дает повторяющиеся шаблоны: $2 \times n$$3 \times n$

$$\begin{cases} U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\ V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\ \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\ \end{cases}$$ где забавные фигуры представляют элементарные композиции домино: - не домино, - вертикальное домино на вершине левой части горизонтального домино, - это вертикальное домино, выровненное по низу полосы высотой 3, - это горизонтальное домино, выровненное по верху полосы, плюс два горизонтальных домино под ним и один шаг вправо, и т. д. Здесь умножение представляет горизонтальную конкатенацию и не является коммутативным, но между элементарными образцами, которые образуют переменные в этом степенном ряду, существуют уравнения. Как и раньше с монетами, мы можем заменить для каждого домино и получить серию генерации для числа бросков$\mathsf{o}$$\mathsf{L}$$\substack{\strut\\\mathsf{I}}$$\substack{\:-\\=}$$X$$3 \times (2n/3)$Прямоугольник (т. Е. Коэффициент - это количество способов разбить прямоугольник площадью , который содержит домино и имеет ширину ). Эта серия также может использоваться более универсально; например, различая вертикальное и горизонтальное домино, мы можем подсчитать размеры мозаики с заданным количеством вертикальных и горизонтальных домино.$X^{3k}$$6k$$3k$$2k$

Снова, прочитайте Конкретную Математику для менее спешащего представления

¹ _{Я знаю , что мой список является неполным; предположим, что для математических примеров используется упрощенный метод США.}
² _{Кроме того, если это подходит, предположим, что сферические монеты.}
³ _{И лучше набрать текст.}

Я помню проблему, которую мне пришлось решить во время студенческого конкурса по программированию в 2001 году. Проблема была в следующем:

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

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

Если бы я не был высокомерным и самодостаточным в то время (и знал бы я и практиковал генерирование функций), я мог бы определить проблему с генерацией функций как таковую:

Определите как OGF для количества способов, которым вес может быть взвешен, учитывая набор масс.$f(x)$$n$

Какой вес на правой чашке я могу весить, учитывая одну массу 1?

Три возможности:

• Если я положу массу на левую сковороду, я могу весить 1.
• Если я положу массу на правильную сковороду, я могу весить -1.
• Если я не использую массу, я могу весить 0.

Таким образом, существует один способ взвешивания , один способ взвешивания и один способ взвешивания . Производящая функция для этой массы имеет вид , что соответствует:$-1$$0$$1$$x^{-1} + 1 + x$

$$\frac{1 - x^3}{x(1-x)}$$

Производящая функция для одной массы имеет вид , который равен:$m$$x^{-m} + 1 + x^m$

$$\frac{1 - x^{3m}}{x^m(1-x^m)}$$

Для заданного мультимножества масс выражается как произведение функций, генерирующих одну массу:$M$$f$

$$f(x) = \frac{\prod_{m \in M}(1 - x^{3m})}{x^{\sum_{m \in M}m}\prod_{m \in M}(1 - x^{m})}$$

Теперь, учитывая пакет, который может выполнять операции над полиномами, вам просто нужно:

• Рассчитайте оба продукта.
• Выполните разделение этих продуктов, начиная с самой низкой степени. (который заканчивается)
• Сдвиньте полином (евклидово деление на , сохраняя частное и сбрасывая остаток)$x^k$

И вы сделали. Теперь у вашего полинома есть множество способов взвешивания по индексу . Только вход является мультимножеством масс .$w \ge 0$$w$$M$

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

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

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

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

$$\ell \gamma^{(m)}_{\ell+1} = (2\ell-m) \gamma^{(m)}_\ell + (m - \ell + 1) \gamma^{(m)}_{\ell-1}, \quad \gamma^{(m)}_0 = 1, \quad \gamma^{(m)}_{m+1} = e.$$ $\gamma^{(m)}_\ell = m(\gamma^{(m-1)}_\ell - \gamma^{(m-1)}_{\ell-1})$$\gamma^{(0)}$$\gamma^{(m)}$

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