Самая длинная общая задача последовательности

C (Си) — язык программирования (не только) для системного программирования Изучение
На чтение 10 мин Просмотров 61 Опубликовано

Самая длинная общая подпоследовательность (LCS) — классическая задача в информатике. Подходы к решению проблемы LCS часто появляются на собеседованиях по программированию и курсах по алгоритмам.

Содержание
  1. Какова самая длинная общая задача последовательности?
  2. Каков практический пример проблемы LCS?
  3. Как работают подходы к решению самой длинной общей задачи последовательности?
  4. Рекурсивно определить самую длинную общую подпоследовательность
  5. Оптимизация рекурсивного подхода с помощью мемоизации
  6. Динамическое программирование для самой длинной общей подпоследовательности

Какова самая длинная общая задача последовательности?

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

последовательность X последовательность Y LCS(X, Y)
FATHER VATER ATER
MOTHER MUTTER MTER
DAVID DANIEL DAI

Каков практический пример проблемы LCS?

Проблема самой длинной общей подпоследовательности важна во всех областях, где используются последовательности, производные друг от друга. Подходы к поиску ЛСК используются, например, для проверки текстов на сходства и различия — так можно отследить плагиат. Известная diffутилита, показывающая изменения в файлах исходного кода, также основана на проблеме LCS.

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

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

Как работают подходы к решению самой длинной общей задачи последовательности?

Во-первых, проблема LCS может быть решена с помощью «наивного» подхода. Это очевидный подход без какой-либо оптимизации или специального подхода. Один определяет все подпоследовательности двух последовательностей и находит самую длинную подпоследовательность, которая является общей для обеих последовательностей. К сожалению, этот подход неэффективен и поэтому подходит только для коротких последовательностей.

Ниже мы покажем три эффективных подхода к решению проблемы LCS:

  1. Рекурсивный подход
  2. Оптимизация с помощью мемоизации
  3. Динамическое программирование

Общим для всех подходов является то, что они различают три случая в отношении двух последовательностей:

  • Последнее письмо такое же.
  • Последнее письмо не то.
  • Длина одной из последовательностей равна нулю.
Читайте также:  Полное руководство по параметрам функций в PHP для начинающих

Подходы различаются по временной сложности (асимптотическое время выполнения) и пространственной сложности (требования к памяти):

Подход Продолжительность Требования к памяти
Наивный подход O(n * n²) O(n)
Рекурсивный подход O(n²) O(1)
Оптимизация с помощью мемоизации O(n * m) O(n * m)
Динамическое программирование O(n * m) O(n * m)

Рекурсивно определить самую длинную общую подпоследовательность

Взгляд на проблему LCS показывает, что она имеет «оптимальную подструктуру». Это означает, что проблема может быть сведена к подзадачам. Для решения этой проблемы можно использовать рекурсивный подход. Мы показываем реализацию алгоритма на трех популярных языках программирования.

Python

def lcs(X, Y, m, n):
  # Base case
  if m == 0 or n == 0:
    return 0
  # Last elements are equal
  elif X[m-1] == Y[n-1]:
    return 1 + lcs(X, Y, m-1, n-1)
  # Last elements differ
  else:
    return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n))

# Let's test
X, Y = "DANIEL", "DAVID"
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")

Java

import java.io.*;

class LCS {
  public static int lcs(String A, String B, int m, int n)
  {
    // Base case
    if (m == 0 || n == 0)
      return 0;
    // Last elements are equal
    if (A.charAt(m - 1) == B.charAt(n - 1))
      return 1 + lcs(A, B, m - 1, n - 1);
    // Last elements differ
    else
      return Math.max(lcs(A, B, m, n - 1),
       lcs(A, B, m - 1, n));
  }
  
  // Let's test
  public static void main(String[] args)
    {
      String X = "DAVID";
      String Y = "DANIEL";
      int lcsLength = LCS.lcs(X, Y, X.length(), Y.length());
      System.out.println("Length of LCS is: " + lcsLength);
    }
}

С++

#include <iostream>
using namespace std;

int lcs(string X, string Y, int m, int n)
{
  // Base case
  if (m == 0 || n == 0) {
    return 0;
  }
  // Last elements are equal
  if (X[m - 1] == Y[n - 1]) {
    return 1 + lcs(X, Y, m - 1, n - 1);
  }
  // Last elements differ
  else {
    return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
  }
}

// Let's test
int main()
{
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, X.size(), Y.size());

  return 0;
}

Оптимизация рекурсивного подхода с помощью мемоизации

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

Python

def lcs(X, Y, m, n, table):
  
  # Base case
  if (m == 0 or n == 0):
    return 0
  # Already computed value at given position
  if (table[m][n] != -1):
    return table[m][n]
  # Last elements are equal
  if X[m - 1] == Y[n - 1]:
    table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table)
  # Last elements differ
  else:
    table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table))
  return table[m][n]

# Let's test
X = "DAVID"
Y = "DANIEL"
m, n = len(X), len(Y)
# Initialize table fields to `-1`
table = [[-1 for i in range(n + 1)] for j in range(m + 1)]
// Compute and output length of LCS
print(f"Length of LCS is: {lcs(X, Y, m, n, table)}")

Java

import java.io.*;

class LCS {

  public static int lcs(String X, String Y, int m, int n, int[][] table) {
    // Base case
    if (m == 0 || n == 0) {
      return 0;
    }
    // Already computed value at given position
    if (table[m][n] != -1) {
      return table[m][n];
    }
    // Last elements are equal
    if(X.charAt(m - 1) == Y.charAt(n - 1)) {
      table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
      return table[m][n];
    }
    // Last elements differ
    else {
      table[m][n] = Math.max(lcs(X, Y, m, n - 1, table),lcs(X, Y, m - 1, n, table));
      return table[m][n];
    }
  }

  // Let's test
  public static void main(String args[]){

    // Initialize variables
    String X = "DAVID";
    String Y = "DANIEL";
    int m = X.length();
    int n = Y.length();
    int[][] table = new int[m + 1][n + 1];
    
    // Initialize table fields to `-1`
    for(int i=0; i < m + 1; i++) {
      for(int j=0; j < n + 1; j++) {
        table[i][j] = -1;
      }
    }

    // Compute and output length of LCS
    int lcsLength = lcs(X, Y, m, n, table);
    System.out.println("Length of LCS is: " + lcsLength);
  }
}

С++

#include <bits/stdc++.h>
using namespace std;

int lcs(char* X, char* Y, int m, int n, vector<vector<int>>& table)
{
  // Base case
  if (m == 0 || n == 0)
    return 0;
  // Already computed value at given position
  if (table[m][n] != -1) {
    return table[m][n];
  }
  // Last elements are equal
  if (X[m - 1] == Y[n - 1]) {
    table[m][n] = 1 + lcs(X, Y, m - 1, n - 1, table);
    return table[m][n];
  }
  // Last elements differ
  else { 
    table[m][n] = max(lcs(X, Y, m, n - 1, table), lcs(X, Y, m - 1, n, table));
    return table;
  }
}

// Let's test
int main()
{
  // Initialize variables
  char X[] = "DAVID";
  char Y[] = "DANIEL";
  int m = strlen(X);
  int n = strlen(Y);

  // Initialize table with `-1`
  vector<vector<int>> table(m + 1, vector<int>(n + 1, -1));
  
  // Compute and output length of LCS
  cout << "Length of LCS is: " << lcs(X, Y, m, n, table);

  return 0;
}

Динамическое программирование для самой длинной общей подпоследовательности

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

Читайте также:  Что такое файл hosts и как его изменить?

Python

def lcs(X , Y, m, n): 
  
  # Initialize dynamic programming table fields to `None`
  table = [[None] * (n + 1) for _ in range(m + 1)]
  
  # Compute table values
  for i in range(m + 1):
    for j in range(n + 1):
      # Base case
      if i == 0 or j == 0 :
        table[i][j] = 0
      # Last elements are equal
      elif X[i - 1] == Y[j - 1]:
        table[i][j] = table[i - 1][j - 1]+ 1
      # Last elements differ
      else:
        table[i][j] = max(table[i - 1][j] , table[i][j - 1])
  
  return table[m][n]

# Let's test
X = "DAVID"
Y = "DANIEL"

# Compute and output length of LCS
lcs_len = lcs(X, Y, len(X), len(Y))
print(f"Length of LCS is: {lcs_len}")

Java

import java.io.*;

class LCS {

  public static int lcs(String X, String Y, int m, int n)
  {
    // Initialize dynamic programming table fields
    int table[][] = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        // Base case
        if (i == 0 || j == 0)
          table[i][j] = 0;
        // Last elements are equal
        else if (X.charAt(i - 1) == Y.charAt(j - 1))
          table[i][j] = table[i - 1][j - 1] + 1;
        // Last elements differ
        else
          table[i][j] = Math.max(table[i - 1][j], table[i][j - 1]);
      }
    }
    return table[m][n];
  }

  // Let's test
  public static void main(String args[]){

    // Initialize variables
    String X = "DAVID";
    String Y = "DANIEL";
    int m = X.length();
    int n = Y.length();

    // Compute and output length of LCS
    int lcsLength = lcs(X, Y, m, n);
    System.out.println("Length of LCS is: " + lcsLength);
  }
}

С++

#include <bits/stdc++.h>
using namespace std;

int lcs(string X, string Y, int m, int n) {
	// Initialize dynamic programming table
	int table[m + 1][n + 1];

	// Compute table values
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			// Base case
			if (i == 0 || j == 0)
				table[i][j] = 0;
			// Last elements are equal
			else if (X[i - 1] == Y[j - 1])
				table[i][j] = table[i - 1][j - 1] + 1;
			// Last elements differ
			else
				table[i][j] = max(table[i - 1][j], table[i][j - 1]);
		}
	}

	return table[m][n];
}

// Let's test
int main() {
  // Initialize variables
  string X = "DAVID";
  string Y = "DANIEL";
  int m = X.size();
  int n = Y.size();

  // Compute and output length of LCS
  cout << "Length of LCS is " << lcs(X, Y, m, n);

  return 0;
}

Оцените статью
Блог о программировании
Добавить комментарий

© 2026 Блог о программировании
Этот сайт использует cookie для хранения данных. Продолжая использовать сайт, Вы даете свое согласие на работу с этими файлами.