უგრძესი საერთო ქვემიმდევრობის ამოცანა

უგრძესი საერთო ქვემიმდევრობის (უსქ) ამოცანა —  ამოცანა, რომელიც ეძებს მიმდევრობებს შორის უგრძეს საერთო ქვემიმდევრობას (ძირითადად ორ მიმდევრობაზე განიხილავენ).    

მაგალითად, განვიხილოთ ორი მიმდევრობა (ABCD) და (ACBAD). მათ 5 უსქ აქვთ, სიგრძით 2: (AB),(AC),(AD),(BD) და (CD); 2 უსქ, სიგრძით 3: (ABD) და (ACD); უფრო გრძელი კი არ გვაქვს. შესაბამისად, (ABC) და (ACD) არის უგრძესი საერთო ქვემიმდევრობა.     

 სირთულე 
ეს ამოცანა არის NP-რთული ამოცანა. ის დინამიური პროგრამირების პრინციპით პოლინომიურ დროში იხსნება.  

მოცემულია  სიგრძეების მიმდევრობები , სრული ძებნა შეამოწმებს თითოეულ მათგანის  ქვესიმრავლეს, რათა დაადგინოს, არიან თუ არა ისინი აგრეთვე დანარჩენი მიმდევრობების ქვემიმდევრობები; მოცემული ამოცანის დროის სირთულე იქნება 



n და m სიგრძის ორი მიმდევრობისთვის დროის სირთულე დინამიური პროგრამირებით იქნება O(n × m). ნებისმიერი რაოდენობის ქვემიმდევრობისთვის დინამიური პროგრამირების ამოხსნის დროის სირთულე იქნება  



 ამოხსნა ორი მიმდევრობისთვის 

 LCS ფუნქცია 
განვსაზღვროთ ორი მიმდევრობა შემდეგნაირად:  და  . -ის პრეფიქსები არიან  ; -ის კი   . -ით აღვნიშნოთ უგრძესი საერთო ქვემიმდევრობა პრეფიქსებისთვის  და  .   

რათა ვიპოვოთ LCS  და -თვის, შევადაროთ   და . თუ ისინი ტოლია, მაშინ ქვემიმდევრობა  -ზე ერთით მეტი იქნება . თუ ისინი ტოლი არ არიან, მაშინ  , და  შორის უგრძესის ტოლი გახდება.

იმპლემენტაცია C++-ზე
int dp[1000][1000];
int getLCS(vector<int>a,vector<int>b){
    int n=a.size();
    int m=b.size();
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=1+dp[i-1][j-1];
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }return dp[n][m];
}
რესურსები ინტერნეტში
 Dictionary of Algorithms and Data Structures: longest common subsequence
 A collection of implementations of the longest common subsequence in many programming languages
 Implementation of Longest Common Subsequence Algorithm in C Programming Language 

სქოლიო

კატეგორია:კომბინატორიკა
კატეგორია:პროგრამირება
კატეგორია:ალგორითმები