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

120

C# и .NET Framework --- Оптимизация приложений .NET Framework --- Мемоизация и динамическое программирование

Мемоизация - это прием сохранения промежуточных результатов, которые могут еще раз понадобиться в ближайшее время, чтобы избежать их повторного вычисления. Этот прием можно рассматривать как разновидность кеширования. Классическим примером применения мемоизации является вычисление последовательности чисел Фибоначчи, которое часто служит первым примером при изучении рекурсии:

public static ulong FibonacciNumber(uint which)
{
    if (which == 1 || which == 2) 
        return 1;
        
    return FibonacciNumber(which - 2) + FibonacciNumber(which - 1);
}

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

Одна из причин такой неэффективности состоит в том, что промежуточные результаты вычисляются более одного раза. Например, FibonacciNumber(10) вычисляется рекурсивно при попытке вычислить FibonacciNumber (11) и FibonacciNumber (12), и затем при попытке вычислить FibonacciNumber(12) и FibonacciNumber(13), и так далее. Сохраняя промежуточные результаты в массиве можно существенно повысить производительность этого метода:

public static ulong FibonacciNumberMemoization(uint which)
{
    if (which == 1 || which == 2) 
        return 1;

    ulong[] array = new ulong[which];
    array[0] = 1; 
    array[1] = 1;

    return FibonacciNumberMemoization(which, array);
}

private static ulong FibonacciNumberMemoization(uint which, ulong[] array)
{
    if (array[which - 3] == 0)
    {
        array[which - 3] = FibonacciNumberMemoization(which - 2, array);
    }

    if (array[which - 2] == 0)
    {
        array[which - 2] = FibonacciNumberMemoization(which - 1, array);
    }

    array[which - 1] = array[which - 3] + array[which - 2];
    return array[which - 1];
}

Эта версия находит 10 000-е число Фибоначчи за доли секунды и имеет линейную сложность. Кстати говоря, эту реализацию можно упростить еще больше, сохраняя только два последних вычисленных числа:

public static ulong FibonacciNumberIteration(ulong which)
{
    if (which == 1 || which == 2)
        return 1;

    ulong a = 1, b = 1;

    for (ulong i = 2; i < which; ++i)
    {
        ulong c = a + b;
        a = b;
        b = c;
    }
    return b;
}

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

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

Расстояние Левенштейна

Расстояние Левенштейна между двумя строками - это количество операций с символами (удаление, вставка и замена), которое требуется выполнить, чтобы преобразовать одну строку в другую. Например, расстояние Левенштейна между строками «cat» и «hat» равно 1 (достаточно заменить «c» на «h»), а расстояние Левенштейна между «cat» и «groat» равно 3 (вставить «g», вставить «r», заменить «c» на «o»). Эффективный поиск расстояния Левенштейна между двумя строками играет важную роль во многих ситуациях, таких как правка ошибок и проверка правописания с предложением строк для замены.

Ключом к эффективности алгоритма является разбиение большой задачи на множество маленьких. Например, если известно, что расстояние Левенштейна между «cat» и «hat» равно 1, следовательно расстояние Левенштейна между «cats» и «hat» будет равно 2 - мы воспользовались результатом уже решенной подзадачи, чтобы найти решение более крупной задачи. Применять этот прием на практике следует с большой осторожностью. Для двух строк, представленных в виде массивов, s[1...m] и t[1...n], выполняются следующие правила:

расстояние Левенштейна между пустой строкой и строкой t равно n, а расстояние между строкой s и пустой строкой равно m (количество добавлений или удалений всех символов);
если s[i] = t[j] и расстояние между s[1...i-1] и [1...j-1] равно k, мы можем сохранить i-й символ и принять расстояние между s[1...i] и t[1...j] как равное k;
если s[i] != t[j], расстояние между s[1...i] и t[1...j] будет не меньше, чем:
1. расстояние между s[1...i] и t[1...j-1], +1 для вставки t[j];
2. расстояние между s[1...i-1] и t[1...j], +1 для удаления s[i];
3. расстояние между s[1...i-1] и t[1...j-1], +1 для замены s[i] на t[j]

Следующий метод на C# находит расстояние Левенштейна между двумя строками путем конструирования таблицы расстояний для каждой подстроки, и возвращает расстояние из итоговой ячейки таблицы:

public static int EditDistance(string s, string t)
{
    int m = s.Length, n = t.Length;
    int[,] ed = new int[m, n];
	
    for (int i = 0; i < m; ++i)
    {
        ed[i, 0] = i + 1;
    }
	
    for (int j = 0; j < n; ++j)
    {
        ed[0, j] = j + 1;
    }
	
    for (int j = 1; j < n; ++j)
    {
        for (int i = 1; i < m; ++i)
        {
            if (s[i] == t[j])
            {
                // Операция не требуется
                ed[i, j] = ed[i - 1, j - 1];
            }
            else
            { 
                // Минимум между удалением, вставкой и заменой
                ed[i, j] = Math.Min(ed[i - 1, j] + 1, 
                    Math.Min(ed[i, j - 1] + 1, ed[i - 1, j - 1] + 1));
            }
        }
    }
	
    return ed[m - 1, n - 1];
}

Алгоритм заполняет таблицу расстояний по столбцам, то есть никогда не пытается использовать еще не вычисленные данные. На рисунке ниже показана таблица расстояний, построенная алгоритмом для строк "stutter" и "glutton":

Заполненная таблица расстояний Левенштейна

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

Кратчайший путь между всеми парами вершин

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

Мы реализовали службу управления несколькими физическими устройствами резервного копирования. Имеется несколько пересекающихся конвейеров и роботизированных манипуляторов для захвата кассет с резервными копиями. Служба принимает запросы вида: «переместить самую свежую ленту X из устройства 13 в устройство 89, гарантировав попутное прохождение ленты через станцию форматирования C или D».
На запуске система вычисляет кратчайшие пути между всеми парами устройств, включая специальные требования, такие как обязательное прохождение через определенный компьютер. Эта информация хранится в огромной хеш-таблице с описаниями маршрутов в качестве индексов и маршрутами в качестве значений.
Запуск системы для 1000 узлов и 250 пересечений занимает более 30 минут, а объем потребляемой памяти при этом достигает 5 Гбайт. Это совершенно неприемлемо.

Прежде всего мы обратили внимание, что ограничение «гарантировав попутное прохождение ленты через станцию форматирования C или D» не является серьезной дополнительной задачей. Кратчайший путь из точки A в точку B через точку C есть кратчайший путь из точки A в точку C плюс кратчайший путь из точки C в точку B (доказать это элементарно просто).

Алгоритм Флойда-Уоршелла (Floyd-Warshall) находит кратчайшие пути между всеми парами вершин в графе и использует прием разделения большой задачи на несколько более мелких подзадач, подобно тому, как это делалось выше. На этот раз рекурсивная формула использует то же наблюдение, сделанное выше: кратчайший путь из точки A в точку B лежит через некоторую вершину V. Тогда, чтобы найти кратчайший путь из A в B, необходимо сначала найти кратчайший путь из A в V, потом кратчайший путь из V в B и, наконец, объединить их. Так как заранее неизвестно, какое устройство будет играть роль вершины V, нам нужно рассмотреть все возможные промежуточные устройства. Для этого мы можем пронумеровать их от 1 до n.

Теперь длина кратчайшего пути (Shortest Path, SP) из вершины i в вершину j через одну из обязательных вершин 1, ..., k определяется следующей рекурсивной формулой, предполагающей отсутствие ребра, связывающего вершины i и j:

SP(i, j, k) = min { 
                SP(i, j, k-1), 
                SP(i, k, k-1) + SP(k, j, k-1) }

Чтобы разобраться в ней, рассмотрим вершину k. Кратчайший путь из i в j либо лежит через эту вершину, либо нет. Если путь через вершину k не является кратчайшим, мы не должны использовать его и следует попытаться найти более короткий путь через одну из вершин 1,...,k-1. Если путь через вершину k является кратчайшим, мы приходим к необходимости разделения задачи - кратчайший путь можно получить путем объединения кратчайшего пути из i в k (использующего только вершины 1,...,k-1) и кратчайшего пути из k в j (использующего только вершины 1,...,k-1). Пример приводится на рисунке ниже:

Вверху показан кратчайший путь из i в j (через вершины 2 и 5). Так как путь через вершину k не является кратчайшим, мы можем ограничить поиск кратчайшего пути вершинами 1,...,k-1. Внизу показан кратчайший путь из i в j, лежащий через вершину k. Этот путь из i в j можно составить из кратчайших путей из i в k и из k в j.

Чтобы избавиться от рекурсивных вызовов, будем использовать мемоизацию - на этот раз нам предстоит заполнить трехмерную таблицу, и, после поиска значений SP для всех пар вершин и всех значений k, мы получим решение задачи о кратчайшем пути между всеми парами вершин.

Мы можем еще больше уменьшить объем используемой памяти, так как для каждой пары вершин i и j нам достаточно запомнить лишь значение k, дающее кратчайший путь. В результате таблица становится двумерной, занимающей объем памяти O(n²). Однако сложность алгоритма остается равной O(n³) - слишком высокой, учитывая, что нам требуется найти кратчайшие пути между всеми вершинами в графе.

Наконец, при заполнении таблицы, в процессе поиска кратчайшего пути между каждой парой вершин i и j нам необходимо запоминать, какую следующую вершину x следует обработать. Опираясь на последнее наблюдение, эти идеи легко воплотить в код на C#:

static short[,] costs;
static short[,] next;

public static void AllPairsShortestPaths(short[] vertices, bool[,] hasEdge)
{
    int N = vertices.Length;
    costs = new short[N, N];
    next = new short[N, N];

    for (short i = 0; i < N; ++i)
    {
        for (short j = 0; j < N; ++j)
        {
            costs[i, j] = hasEdge[i, j] ? (short)1 : short.MaxValue;
            if (costs[i, j] == 1)
                // Пометить направленное ребро
                next[i, j] = -1; 
        }
    }

    for (short k = 0; k < N; ++k)
    {
        for (short i = 0; i < N; ++i)
        {
            for (short j = 0; j < N; ++j)
            {
                if (costs[i, k] + costs[k, j] < costs[i, j])
                {
                    costs[i, j] = (short)(costs[i, k] + costs[k, j]);
                    next[i, j] = k;
                }
            }
        }
    }
}
		
public string GetPath(short src, short dst)
{
    if (costs[src, dst] == short.MaxValue) 
        return " < no path > ";

    short intermediate = next[src, dst];

    if (intermediate == -1)
        return "- > "; // Прямой путь

    return GetPath(src, intermediate) + intermediate 
        + GetPath(intermediate, dst);
}

Этот простой алгоритм значительно увеличивает производительность приложения. Для случая с 300 узлами, когда из каждого узла в среднем выходит три ребра, создание полного набора путей занимает 3 секунды, а обработка 100 000 запросов на получение кратчайшего пути занимает 120 миллисекунд, при этом используется всего 600 Кбайт памяти.