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

მასალა ვიკიპედიიდან — თავისუფალი ენციკლოპედია
ნავიგაციაზე გადასვლა ძიებაზე გადასვლა

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

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

სირთულე[რედაქტირება | წყაროს რედაქტირება]

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

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

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

ამოხსნა ორი მიმდევრობისთვის[რედაქტირება | წყაროს რედაქტირება]

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];
}

რესურსები ინტერნეტში[რედაქტირება | წყაროს რედაქტირება]

სქოლიო[რედაქტირება | წყაროს რედაქტირება]

  1. David Maier (1978). „The Complexity of Some Problems on Subsequences and Supersequences“. J. ACM. ACM Press. 25 (2): 322–336. doi:10.1145/322063.322075.
  2. Wagner, Robert; Fischer, Michael (January 1974). „The string-to-string correction problem“ (PDF). Journal of the ACM. 21 (1): 168–173. doi:10.1145/321796.321811. ციტირების თარიღი: 2018-05-03.