Вступление
Очень распространенная проблема в компьютерном программировании — найти самую длинную увеличивающуюся (убывающую) подпоследовательность в последовательности чисел (обычно целых чисел). На самом деле это типичная проблема динамического программирования.
Динамическое программирование можно описать как огромную область проблем информатики, которые можно классифицировать по способу их решения. В отличие от «разделяй и властвуй», где нам удавалось объединить достаточно равные подрешения для получения единственного решения проблемы, в динамическом программировании мы обычно стараемся найти оптимальное подрешение и затем вырастить его.
Как только у нас есть оптимальное вспомогательное решение на каждом этапе, мы пытаемся обновить его, чтобы охватить всю проблему. Таким образом, типичный член класса динамического программирования находит самую длинную подпоследовательность.
Однако эта проблема интересна тем, что может быть связана с теорией графов. Давайте узнаем, как.
обзор
Мы уже знаем различные способы вычисления кратчайших путей в графе. Действительно, поиск кратчайшего пути из одного источника является типичной проблемой графа. Для моделирования такого рода решений нам определенно нужен график, представленный в нашем решении.
Однако кратчайший путь из одного источника не является прямой проблемой. Это зависит от многих факторов. Таким образом, для положительных ребер алгоритм Эдсгера Дейкстры может быть идеальным решением, но когда граф содержит отрицательные ребра, его алгоритм больше не нужен.
При наличии отрицательных краев алгоритм Дейкстры не работает, и нам лучше использовать алгоритм Беллмана-Форда . Интересно отметить, что именно Ричард Беллман впервые ввел термин «динамическое программирование» в 1940-х годах.
Фактически алгоритм Беллмана-Форда был в состоянии обнаружить отрицательные циклы. Это слишком важно, потому что при наличии отрицательных циклов проблема кратчайшего пути более не определена.
С другой стороны, когда мы говорим о кратчайших путях в DAG (Направленный ациклический граф), мы можем найти более быстрое (линейное) решение. Это потому, что мы уверены, что циклов нет (даже отрицательных циклов)!
Нахождение кратчайших путей в DAG тесно связано с топологической сортировкой DAG. Это дает нам линейное представление вершин DAG, и мы можем четко рассчитать расстояния от начального узла до всех других узлов. Обратите внимание, что в группе обеспечения доступности баз данных у нас есть один или несколько узлов, которые можно рассматривать как начальные узлы — это означает, что у них нет предшественников (входящих ребер).
Следуя вышеприведенным словам, довольно сложно найти, что все эти алгоритмы графов имеют отношение к нахождению максимально увеличивающейся (убывающей) подпоследовательности. На самом деле эта проблема очень тесно связана с топологическим видом DAG и проблемой поиска кратчайших путей в DAG.
Это потому, что мы можем представить нашу последовательность как DAG. Единственное, о чем мы должны заботиться, это «соединить» направленными ребрами те элементы, которые образуют возрастающую (убывающую) пару.
Таким образом, последовательность из нашего примера [1, 8, 2, 7, 3, 4, 1, 6] будет выглядеть следующим образом.
Еще одна важная вещь, которую стоит отметить, это то, что мы ищем не самый короткий, а самый длинный путь, поскольку наша задача — найти самую длинную подпоследовательность.
Псевдокод
Наш псевдокод для поиска кратчайших путей в DAG был чем-то вроде этого.
1. Get the toplogically sorted list L of the DAG;
2. The starting node is s;
3. The distance to s equals to 0;
4. All other distances are initialized to ∞
5. For each node (v) in L\{s} do:
5.1. If dist(v) > dist(u) + w(u, v) then
5.1.1. dist(v) := dist(u) + w(u, v)
В приведенном выше псевдокоде «u» — каждый предшественник «v»!
Теперь мы должны «перевернуть» вышеприведенное решение, чтобы найти самую длинную возрастающую подпоследовательность. Обратите внимание, что нас больше не заботит вес ребер, поэтому мы можем просто заменить их на 1.
1. Get the sequence (L) as a toplogically sorted DAG; 2. For each (i) in L do: 2.1. S(i) := 1 + max(S(j), where (i, j) is an edge from the DAG);
заявка
Найти самую длинную увеличивающуюся подпоследовательность может быть очень полезно не только в интервью Google / Yahoo / Facebook, но также и в различных областях статистики.