Η μεγαλύτερη κοινή υποακολουθία: Python, C++ Παράδειγμα

Ποια είναι η μεγαλύτερη κοινή υποακολουθία;

Η Μεγαλύτερη Κοινή Υποακολουθία (LCS) σημαίνει ότι θα σας δοθούν δύο συμβολοσειρές, μοτίβα ή ακολουθίες αντικειμένων. Μεταξύ αυτών των δύο ακολουθιών ή συμβολοσειρών, πρέπει να βρείτε τη μεγαλύτερη υποακολουθία στοιχείων με την ίδια σειρά που υπάρχει και στις δύο συμβολοσειρές ή τα μοτίβα.

Παράδειγμα

Για παράδειγμα, παρέχονται δύο συμβολοσειρές. Ας υποθέσουμε ότι:

Pattern_1 = "RGBGARGA"
Pattern_2 = "BGRARG"

• Από το pattern_1, μπορούν να παραχθούν ακολουθίες όπως "RGB", "RGGA", "RGAR". Για να δημιουργήσετε μια ακολουθία, πρέπει να διατηρήσετε τη σχετική θέση κάθε χαρακτήρα στη συμβολοσειρά.
• Από το pattern_2, μπορούμε να παράγουμε ακολουθίες όπως “BGR”, “BRAG”, “RARG”. Οι ακολουθίες μπορούν να παραχθούν εφόσον διατηρούν τη σχετική θέση της αρχικής συμβολοσειράς.

Ο όρος σχετική θέση σημαίνει τάξη.

Για παράδειγμα, το «BRG» είναι μια έγκυρη ακολουθία επειδή το «B» εμφανίστηκε πρώτο, μετά το «R» και μετά το «G» στην αρχική συμβολοσειρά pattern_2. Ωστόσο, εάν μια ακολουθία είναι «RBRG», δεν είναι έγκυρη, επειδή στην αρχική συμβολοσειρά (pattern_2), το «B» έρχεται πρώτο.

Έχουμε δύο επιλογές για να βρούμε τη μεγαλύτερη κοινή υποακολουθία από τις δύο δεδομένες ακολουθίες ή πίνακες.

• Αφελής μέθοδος
• Λύση δυναμικού προγραμματισμού: Η μεγαλύτερη κοινή υποακολουθία είναι επίσης γνωστή ως LCS.

Μια απλοϊκή λύση έχει μεγαλύτερη χρονική πολυπλοκότητα και δεν είναι η βέλτιστη λύση. Χρησιμοποιώντας τη Λύση Δυναμικού Προγραμματισμού (DP), ξεπερνάμε το πρόβλημα της πολυπλοκότητας.

Αφελή μέθοδος

Η απλοϊκή μέθοδος είναι μια απλή προσέγγιση στο πρόβλημα, ανεξάρτητα από την χρονική πολυπλοκότητα και άλλους παράγοντες βελτιστοποίησης. Αποτελείται από «ωμή βία», πολλαπλούς βρόχους και αναδρομικές κλήσεις στις περισσότερες περιπτώσεις. Ο όρος «ωμή βία» σημαίνει εξέταση όλων των πιθανών μοτίβων για ένα δεδομένο πρόβλημα.

Παράδειγμα

Από το παραπάνω παράδειγμα του σχεδίου1 και του μοτίβου2, ας υποθέσουμε ότι το σχέδιο1 έχει μήκος m και το σχέδιο2 έχει μήκος n. Για να ελέγξουμε κάθε πιθανή περίπτωση, πρέπει να αξιολογήσουμε κάθε πιθανή υποακολουθία του μοτίβου1 με το πρότυπο2.

Εδώ είναι μια απλή συμβολοσειρά 4 γραμμάτων "ABCD". Για παράδειγμα, πρέπει να δημιουργήσουμε μια ακολουθία από το "ABCD". Είτε μπορούμε να πάρουμε έναν χαρακτήρα είτε όχι. Αυτό σημαίνει ότι, για κάθε χαρακτήρα, έχουμε δύο επιλογές:

• Ο χαρακτήρας θα προστεθεί στη συνέχεια.
• Ο χαρακτήρας δεν θα προστεθεί στη συνέχεια.

Εδώ, οι εικόνες δείχνουν όλες τις ακολουθίες που μπορούμε να κάνουμε από τη συμβολοσειρά "ABCD".

Ακολουθία με 1 χαρακτήρα:

Ακολουθίες με 2 χαρακτήρες:

Ακολουθίες με 3 χαρακτήρες:

Από το παραπάνω διάγραμμα, υπάρχουν 14 ακολουθίες. Αν δεν πάρουμε κανένα γράμμα, ουσιαστικά μια κενή συμβολοσειρά, οι συνολικές ακολουθίες θα είναι 15. Επιπλέον, η ίδια η συμβολοσειρά «ABCD» είναι μια ακολουθία. Έτσι, οι συνολικές ακολουθίες είναι 16.

Έτσι, είναι δυνατό να δημιουργηθούν 2^4 ή 16 υποακολουθίες από το "ABCD". Στη συνέχεια, μια συμβολοσειρά με μήκος m θα έχει συνολική υποακολουθία 2^m.

Για κάθε υποακολουθία, πρέπει να την ελέγξουμε για ολόκληρο το μοτίβο2. Θα χρειαστεί χρόνος O(n). Το O(n) σημαίνει τη συνάρτηση πολυπλοκότητας που υπολογίζει τον χρόνο που απαιτείται για την εκτέλεση.

Έτσι, η συνολική χρονική πολυπλοκότητα γίνεται Ο(n*2^m). Για το παράδειγμα που είδαμε παραπάνω, η τιμή του m=8 και του n=5.

Ακολουθούν τα βήματα της αφελούς μεθόδου:

Βήμα 1) Πάρτε μια ακολουθία από το μοτίβο1.
Βήμα 2) Αντιστοιχίστε την ακολουθία από το βήμα 1 με το μοτίβο 2.
Βήμα 3) Εάν ταιριάζει, τότε αποθηκεύστε την δευτερεύουσα σειρά.
Βήμα 4) Εάν απομένουν περισσότερες ακολουθίες στο μοτίβο1, τότε προχωρήστε ξανά στο βήμα 1.
Βήμα 5) Εκτυπώστε τη μεγαλύτερη υποακολουθία.

Βέλτιστη Υποδομή

Ο όρος βέλτιστη υποδομή σημαίνει ότι μια βέλτιστη λύση μπορεί να βρεθεί λύνοντας τα υποπροβλήματα. Για παράδειγμα, στο παραπάνω παράδειγμα, έχουμε το μοτίβο1 και το μοτίβο2.

Βήμα 1) Πάρτε τους δύο πρώτους χαρακτήρες από κάθε μοτίβο.

Βήμα 2) Πάρτε τον τρίτο έως τον πέμπτο χαρακτήρες από κάθε μοτίβο.

Βήμα 3) Συνεχίστε παρόμοια με τους υπόλοιπους χαρακτήρες.

Αναδρομική Δομή του προβλήματος LCS

Βρίσκουμε το LCS στην υποσυμβολοσειρά (μια συμβολοσειρά που δημιουργείται από μια αρχική συμβολοσειρά). Στη συνέχεια, διατηρούμε το αρχείο του μήκους του LCS των υποσυμβολοσειρών.

Τώρα, εδώ είναι μια άλλη ενδιαφέρουσα ιδιοκτησία που είναι επικάλυψηping υποπροβλήματαΈνα πρόβλημα λέγεται ότι έχει επικάλυψηping υποπροβλήματα εάν η δήλωση προβλήματος μπορεί να χωριστεί σε μικρά υποπροβλήματα και να χρησιμοποιηθεί αρκετές φορές στο πρόγραμμα.

Το παρακάτω διάγραμμα δείχνει ότι ο αναδρομικός αλγόριθμος κάλεσε τη συνάρτηση με την ίδια παράμετρο πολλές φορές.

Για παράδειγμα, κοιτάξτε το δέντρο αναδρομής. Στο σκούρο πλαίσιο, μπορείτε να παρατηρήσετε επικάλυψη.ping Τα υποπροβλήματα (“RG”, “RA”), (“RG”, “R”) και άλλα καλούνται αρκετές φορές.

Για να βελτιστοποιήσουμε αυτό, έχουμε την προσέγγιση Δυναμικός προγραμματισμός (DP).

Αναδρομική Μέθοδος της Μεγαλύτερης Κοινής Υποακολουθίας

Το γράφημα που φαίνεται παραπάνω είναι η αναδρομική μέθοδος. Κάθε αναδρομική συνάρτηση έχει μια βασική περίπτωση για να διακόψει την αναδρομή ή να ξεκινήσει την επιστροφή από τη στοίβα της.

Για αυτήν την υλοποίηση, θα χρησιμοποιήσουμε μια βασική περίπτωση. Έτσι, το αλγόριθμος είναι σαν το εξής:

• Εάν όλα τα στοιχεία πριν από το τελευταίο στοιχείο ταιριάζουν, τότε αυξήστε το μήκος κατά ένα και επιστρέψτε.
• Μεταβιβάστε δύο μοτίβα στη συνάρτηση και λάβετε τη μέγιστη τιμή της επιστροφής.
• Αν ένα μοτίβο έχει μηδενικό μήκος, τότε δεν έχουμε καμία υποακολουθία για σύγκριση. Επιστρέψτε 0 σε αυτήν την περίπτωση. Αυτή είναι η βασική περίπτωση της αναδρομής.

Παρατσούκλι Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals 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))

Εφαρμογή στο 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;
}

Παραγωγή:

Length of LCS is: 5

Εφαρμογή στο 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("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Παραγωγή:

Length of LCS is:  5

Μέθοδος Δυναμικού Προγραμματισμού της Μεγαλύτερης Κοινής Υποακολουθίας (LCS)

Δυναμικός προγραμματισμός σημαίνει βελτιστοποίηση της απλής αναδρομικής μεθόδου. Για παράδειγμα, αν κοιτάξουμε το γράφημα αναδρομικής ή αφελούς προσέγγισης, μπορούμε να δούμε ότι υπάρχουν αρκετές πανομοιότυπες κλήσεις συναρτήσεων. Η μέθοδος Δυναμικού Προγραμματισμού καταγράφει όλους τους υπολογισμούς σε έναν πίνακα και τους επαναχρησιμοποιεί όταν χρειάζεται.

Θα χρησιμοποιήσουμε έναν δισδιάστατο πίνακα με διαστάσεις mxn, όπου m και n είναι τα μήκη των pattern1 και pattern2. Για ένα Τρισδιάστατος πίνακας, μπορούμε να χρησιμοποιήσουμε δομές δεδομένων λίστας σε Python ή δομές δεδομένων διανυσμάτων/πίνακων σε C++.

Παρατσούκλι Code για LCS χρησιμοποιώντας 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]

Εδώ είναι ο πίνακας LCS που χρησιμοποιείται ως δομή δεδομένων 2D πίνακα για την προσέγγιση δυναμικού προγραμματισμού.

Ας συζητήσουμε τη λογική που χρησιμοποιήσαμε εδώ. Τα βήματα είναι:

Βήμα 1) Αν το i ή το j είναι μηδέν, παίρνουμε μια κενή συμβολοσειρά από τις δύο δοσμένες συμβολοσειρές και προσπαθούμε να βρούμε τις κοινές υποακολουθίες. Ωστόσο, καθώς η υποσυμβολοσειρά που παίρνουμε είναι κενή, το μήκος της υποακολουθίας είναι 0.

Βήμα 2) Εάν δύο χαρακτήρες ταιριάζουν, θα αντιστοιχίσουμε την τιμή στον δείκτη (i,j) αυξάνοντας το προηγουμένως υπολογισμένο LCS, το οποίο υπάρχει στον δείκτη (i-1,j-1) (από την προηγούμενη σειρά).

Βήμα 3) Αν δεν ταιριάζει, τότε θα πάρουμε το μέγιστο LCS των δύο γειτονικών ευρετηρίων. Και με αυτόν τον τρόπο, πρέπει να συμπληρώσουμε όλες τις τιμές στον δισδιάστατο πίνακα.

Βήμα 4) Τέλος, θα επιστρέψουμε την τιμή του τελευταίου κελιού του πίνακα 2D.

Βασικά, όλες οι τιμές στον δισδιάστατο πίνακα περιέχουν το μήκος των κοινών υποακολουθιών. Μεταξύ αυτών, το τελευταίο κελί περιέχει το μήκος της μεγαλύτερης κοινής υποακολουθίας.

Εφαρμογή στο 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 < n + 1; i++) {
    for (int j = 0; j < 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;
}

Παραγωγή:

Length of LCS: 5

Εφαρμογή στο 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))

Παραγωγή:

Length of LCS: 5

Έτσι, και οι δύο χορδές έχουν τη μεγαλύτερη κοινή υποακολουθία μήκους 5.

Με λίγα λόγια, απλώς υπολογίζουμε κάθε εργασία μία φορά στη μέθοδο DP. Στην αναδρομική μέθοδο, μπορεί να έχουμε επικάλυψηping υποπροβλήματα.

Σε αυτόν τον αλγόριθμο δυναμικού προγραμματισμού, χρησιμοποιούμε μια μήτρα 2D. Θα δοθούν δύο συμβολοσειρές (υποθέστε ότι και οι δύο έχουν μήκος n). Τότε ο χώρος που χρειάζεται στον πίνακα είναι nx n. Εάν οι συμβολοσειρές είναι αρκετά μεγάλες, θα χρειαστούμε μια βελτιστοποιημένη για μνήμη έκδοση της λύσης DP.

Η απλοποιημένη λογική που ελήφθη στον κώδικα είναι:

• Δηλώστε έναν πίνακα 2D DP[m][n].
• Συμπληρώστε την πρώτη γραμμή και την πρώτη στήλη του πίνακα DP με 0.
• Πάρτε i και j για την επανάληψη.
• Αν το μοτίβο1[i] ισούται με το μοτίβο2[j], τότε η ενημέρωση γίνεται ως εξής: DP[i][j] = DP[i-1][j-1] + 1.
• Εάν το μοτίβο1[i] δεν ισούται με το μοτίβο2[j], τότε το DP[i][j] θα είναι η μέγιστη τιμή μεταξύ DP[i-1][j] και DP[i][j-1].
• Συνεχίστε μέχρι το i και το j να φτάσουμε στα m και n.
• Το τελευταίο στοιχείο, DP[m-1][n-1], θα περιέχει το μήκος.

Εδώ, αναφέρεται ως DP[m-1][n-1] επειδή ο δείκτης του πίνακα ξεκινά από το 0.

Συχνές Ερωτήσεις