Dãy số chung dài nhất: Python, C++ Ví dụ

Dãy số chung dài nhất là gì?

Chuỗi chung dài nhất (LCS) có nghĩa là bạn sẽ được cung cấp hai chuỗi/mẫu/chuỗi đối tượng. Trong số hai chuỗi/chuỗi này, bạn cần tìm chuỗi phần tử dài nhất theo cùng thứ tự có trong cả hai chuỗi hoặc mẫu.

Ví dụ

Ví dụ: có hai chuỗi được cung cấp.

Hãy giả sử rằng,

Mẫu_1 = “RGBGARGA”
Mẫu_2 = “BGRARG”

Từ mẫu_1, các chuỗi có thể được tạo ra như “RGB”, “RGGA”, “RGAR”. Để tạo chuỗi, bạn cần duy trì vị trí tương đối của từng ký tự trong chuỗi.
Từ mẫu_2, chúng ta có thể tạo ra các chuỗi như “BGR”, ”BRAG”, “RARG”. Các chuỗi có thể được tạo ra miễn là chúng duy trì được vị trí tương đối của chuỗi ban đầu.

Thuật ngữ vị trí tương đối có nghĩa là trật tự.

Ví dụ: “BRG” là một chuỗi hợp lệ vì “B” xuất hiện đầu tiên, sau đó là “R” và sau đó là “G” trong mẫu chuỗi ban đầu_2. Tuy nhiên, nếu một chuỗi là “RBRG” thì nó không hợp lệ. Bởi vì trong chuỗi gốc (mẫu_2), “B” đứng đầu.

Chúng ta có hai lựa chọn để tìm Dãy con chung dài nhất từ hai dãy hoặc mảng đã cho.

Phương pháp ngây thơ
Giải pháp lập trình động: Chuỗi chung dài nhất còn được gọi là LCS.

Giải pháp ngây thơ có độ phức tạp thời gian lớn hơn và không phải là giải pháp tối ưu. Sử dụng Giải pháp lập trình động (DP), chúng tôi khắc phục được vấn đề phức tạp.

Phương pháp ngây thơ

Phương pháp ngây thơ là cách tiếp cận vấn đề đơn giản mà không quan tâm đến độ phức tạp về thời gian và các yếu tố tối ưu hóa khác.

Phương pháp Naive bao gồm “Brute Force”, nhiều vòng lặp, phương pháp đệ quy trong hầu hết các trường hợp.

Thuật ngữ vũ lực có nghĩa là xem xét tất cả các mô hình có thể có cho một vấn đề nhất định.

Ví dụ

Từ ví dụ trên về mẫu1 và mẫu2, chúng ta giả sử mẫu1 có chiều dài m và mẫu2 có chiều dài n. Để kiểm tra mọi trường hợp có thể xảy ra, chúng ta cần đánh giá mọi dãy con có thể có của mẫu 1 bằng mẫu 2.

Đây là một chuỗi 4 chữ cái đơn giản “ABCD”. Ví dụ: chúng ta cần tạo một chuỗi từ “ABCD”. Hoặc chúng ta có thể lấy một nhân vật hoặc không. Điều đó có nghĩa là, với mỗi nhân vật, chúng ta có hai lựa chọn.

Đó là:

Ký tự sẽ được thêm vào phần tiếp theo.
Ký tự sẽ không được thêm vào dãy sau.

Ở đây, hình ảnh hiển thị tất cả các chuỗi mà chúng ta có thể tạo từ chuỗi “ABCD”.

Chuỗi có 1 ký tự:

Chuỗi có 2 ký tự:

Chuỗi có 3 ký tự:

Từ sơ đồ trên, có 14 trình tự. Nếu chúng ta không lấy các chữ cái, về cơ bản là một chuỗi trống thì tổng số chuỗi sẽ là 15. Hơn nữa, bản thân chuỗi “ABCD” cũng là một chuỗi. Vì vậy, tổng số chuỗi là 16.

Vì vậy có thể tạo ra 2⁴ hoặc 16 dãy con từ “ABCD”. Khi đó, một sợi dây có độ dài m sẽ có tổng dãy con là 2^m.

Đối với mỗi chuỗi con, chúng ta cần kiểm tra toàn bộ mẫu2. Sẽ mất 0(n) thời gian. 0(n) nghĩa là hàm độ phức tạp tính toán thời gian thực hiện.

Vì vậy, độ phức tạp thời gian tổng thể trở thành O(n*2^m). Trong ví dụ, chúng ta đã thấy ở trên giá trị của m=8 và n=5.

Dưới đây là các bước của Phương pháp Naive:

Bước 1) Lấy một chuỗi từ mẫu1.
Bước 2) Nối trình tự từ bước 1 với mẫu 2.
Bước 3) Nếu trùng khớp thì lưu chuỗi tiếp theo.
Bước 4) Nếu còn lại nhiều trình tự hơn trong mẫu 1 thì hãy quay lại bước 1.
Bước 5) In dãy con dài nhất.

Cấu trúc tối ưu

Thuật ngữ cấu trúc con tối ưu có nghĩa là một giải pháp tối ưu (đơn giản) có thể được tìm thấy bằng cách giải các bài toán con. Ví dụ, trong ví dụ trên, chúng ta có mẫu1 và mẫu2.

Bước 1) Lấy hai ký tự đầu tiên từ mỗi mẫu

Bước 2) Lấy ký tự thứ ba đến thứ năm từ mỗi mẫu.

Bước 3) Tiếp tục tương tự với các ký tự còn lại.

Cấu trúc tối ưu — Cấu trúc đệ quy của bài toán LCS

Chúng tôi tìm thấy LCS trên chuỗi con (chuỗi được tạo từ chuỗi gốc). Sau đó, chúng tôi lưu giữ bản ghi về độ dài LCS của chuỗi con.

Bây giờ, đây là một tính chất thú vị khác đó là các vấn đề phụ chồng chéo. Một bài toán được cho là có các bài toán con chồng chéo nếu phát biểu bài toán có thể được chia thành các bài toán con nhỏ và được sử dụng nhiều lần trong chương trình.

Sơ đồ dưới đây cho thấy thuật toán đệ quy đã gọi hàm có cùng tham số nhiều lần.

Ví dụ, chúng ta hãy xem cây đệ quy.

Trong hộp màu tối, bạn có thể nhận thấy các bài toán phụ chồng chéo nhau. (“RG”, “RA”), (“RG”,”R”) và các bài toán khác được gọi nhiều lần.

Để tối ưu hóa điều này, chúng ta có phương pháp Lập trình năng động (ĐP).

Phương pháp đệ quy của chuỗi Comm dài nhất

Đồ thị được hiển thị ở trên là phương pháp đệ quy. Mỗi hàm đệ quy có một trường hợp cơ sở để phá vỡ đệ quy hoặc bắt đầu quay trở lại từ ngăn xếp của nó.

Để thực hiện việc này, chúng tôi sẽ sử dụng trường hợp cơ bản. Nên thuật toán giống như sau:

Nếu tất cả các phần tử trước phần tử cuối cùng khớp nhau thì hãy tăng độ dài lên một và trả về
Truyền hai mẫu cho hàm và lấy giá trị trả về tối đa
Nếu một mẫu có độ dài bằng 0 thì chúng ta không có chuỗi con nào để so sánh. Trả về XNUMX trong trường hợp này. Đây là trường hợp cơ bản của đệ quy.

Mã giả:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
    lcs(pattern_1, pattern_2, len_1, len_2 - 1)

Triển khai tại C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Đầu ra:

Length of LCS is: 5

Triển khai trong python

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
    return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Đầu ra:

Lenght of LCS is:  5

Phương pháp lập trình động của chuỗi con chung dài nhất (LCS)

Lập trình động có nghĩa là tối ưu hóa phương pháp đệ quy đơn giản. Ví dụ: nếu chúng ta thấy biểu đồ cách tiếp cận đệ quy hoặc đơn giản, chúng ta có thể thấy rằng có một số lệnh gọi hàm giống nhau. Phương pháp Lập trình động ghi lại tất cả các phép tính trong một mảng và sử dụng nó khi cần.

Chúng ta sẽ sử dụng mảng 2D có kích thước mxn, trong đó m và n là độ dài của mẫu1 và mẫu2.

Trong cáp mảng 2D, chúng ta có thể sử dụng cấu trúc dữ liệu List trong python hoặc cấu trúc dữ liệu vector/mảng trong C++.

Mã giả cho LCS sử dụng DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
    for j in range 0 to m + 1:
    if i or j equals to 0:
    dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
    dp[i]][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

Đây là bảng LCS được sử dụng làm cấu trúc dữ liệu mảng 2D cho phương pháp lập trình động.

Hãy thảo luận về logic chúng tôi đã sử dụng ở đây. Các bước là:

Bước 1) Nếu i hoặc j bằng 0 thì chúng ta đang lấy một chuỗi rỗng từ hai chuỗi đã cho và cố gắng tìm các dãy con chung. Tuy nhiên, vì chuỗi con chúng ta đang lấy trống nên độ dài chuỗi con là XNUMX.

Bước 2) Nếu hai ký tự khớp nhau, chúng tôi sẽ gán giá trị cho chỉ mục (i,j) bằng cách tăng LCS đã tính toán trước đó, LCS này có trong chỉ mục (i-1,j-1) (từ hàng trước đó).

Bước 3) Nếu không khớp thì chúng ta sẽ lấy LCS tối đa của hai chỉ số liền kề. Và theo cách này, chúng ta cần điền tất cả các giá trị trong mảng 2D.

Bước 4) Cuối cùng, chúng ta sẽ trả về giá trị của ô cuối cùng của mảng 2D.

Về cơ bản, tất cả giá trị trong mảng 2D đều chứa độ dài của các chuỗi con chung. Trong số này, ô cuối cùng chứa độ dài của dãy con chung dài nhất.

Triển khai tại C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i & lt; n + 1; i++) {
    for (int j = 0; j & lt; m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Đầu ra:

Length of LCS: 5

Triển khai tại Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
    [None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
    for j in range(n + 1):
    if i == 0 or j == 0:
    dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Đầu ra:

Length of LCS: 5

Vì vậy, cả hai chuỗi đều có dãy con chung dài nhất có độ dài 5.

Tóm lại, chúng ta chỉ đơn giản tính toán từng nhiệm vụ một lần trong phương thức DP trong phương thức DP. Trong phương pháp đệ quy, chúng ta có thể có các bài toán con chồng chéo.

Trong Thuật toán lập trình động này, chúng tôi đang sử dụng ma trận 2D. Sẽ có hai chuỗi cho trước (giả sử cả hai đều có độ dài n). Khi đó không gian cần thiết trong mảng là nx n. Nếu chuỗi đủ lớn, chúng ta sẽ cần phiên bản giải pháp DP được tối ưu hóa bộ nhớ.

Logic đơn giản hóa được thực hiện trong mã là:

Khai báo mảng 2D DP[m][n].
Điền vào hàng đầu tiên và cột đầu tiên của mảng DP bằng 0.
Lấy i và j cho lần lặp.
Nếu mẫu1[i] bằng mẫu2[j] thì cập nhật DP[i][j] = DP[i-1][j-1] + 1
Nếu mẫu1[i] không bằng mẫu2[j] thì DP[i][j] sẽ là giá trị tối đa giữa DP[i-1][j] và DP[i][j-1].
Tiếp tục cho đến khi i và j đạt tới m và n.
Phần tử cuối cùng hoặc DP[m-1][n-1], sẽ chứa độ dài.

Ở đây, nó được đánh địa chỉ là DP[m-1][n-1], vì chỉ mục mảng bắt đầu từ 0.

Tổng kết

Phương pháp DP có độ phức tạp thời gian thấp hơn; đó là O(mn), trong đó m và n là độ dài của chuỗi hoặc mảng đầu vào.
DP là một cách tiếp cận nhanh hơn so với cách tiếp cận đệ quy, với độ phức tạp về thời gian là O(n*2^m).
Lập trình động (DP) không được tối ưu hóa bộ nhớ. Chúng tôi đã sử dụng một mảng 2 chiều có độ dài là m*n. Vì vậy, độ phức tạp không gian là (m*n).
Phương pháp đệ quy, trong trường hợp xấu nhất, bộ nhớ cao nhất mà nó chiếm sẽ là m+n, về cơ bản là tổng chiều dài của chuỗi được nhập vào.
Máy tính hiện đại ngày nay có đủ khả năng xử lý lượng bộ nhớ này.

Bạn có thể thích:

Dãy số chung dài nhất là gì?

Ví dụ

Phương pháp ngây thơ

Ví dụ

Cấu trúc tối ưu

NHỮNG BÀI VIẾT LIÊN QUAN

Phương pháp đệ quy của chuỗi Comm dài nhất

Triển khai tại C++

Triển khai trong python

Phương pháp lập trình động của chuỗi con chung dài nhất (LCS)

Triển khai tại C++

Triển khai tại Python

Tổng kết