უგრძესი საერთო ქვემიმდევრობის ამოცანა
უგრძესი საერთო ქვემიმდევრობის (უსქ) ამოცანა — ამოცანა, რომელიც ეძებს მიმდევრობებს შორის უგრძეს საერთო ქვემიმდევრობას (ძირითადად ორ მიმდევრობაზე განიხილავენ).
მაგალითად, განვიხილოთ ორი მიმდევრობა (ABCD) და (ACBAD). მათ 5 უსქ აქვთ, სიგრძით 2: (AB),(AC),(AD),(BD) და (CD); 2 უსქ, სიგრძით 3: (ABD) და (ACD); უფრო გრძელი კი არ გვაქვს. შესაბამისად, (ABC) და (ACD) არის უგრძესი საერთო ქვემიმდევრობა.
სირთულე[რედაქტირება | წყაროს რედაქტირება]
ეს ამოცანა არის NP-რთული ამოცანა. ის დინამიური პროგრამირების პრინციპით პოლინომიურ დროში იხსნება.[1]
მოცემულია სიგრძეების მიმდევრობები , სრული ძებნა შეამოწმებს თითოეულ მათგანის ქვესიმრავლეს, რათა დაადგინოს, არიან თუ არა ისინი აგრეთვე დანარჩენი მიმდევრობების ქვემიმდევრობები; მოცემული ამოცანის დროის სირთულე იქნება
n და m სიგრძის ორი მიმდევრობისთვის დროის სირთულე დინამიური პროგრამირებით იქნება O(n × m).[2] ნებისმიერი რაოდენობის ქვემიმდევრობისთვის დინამიური პროგრამირების ამოხსნის დროის სირთულე იქნება
ამოხსნა ორი მიმდევრობისთვის[რედაქტირება | წყაროს რედაქტირება]
![]() |
ამ სტატიაში არ არის მითითებული სანდო და გადამოწმებადი წყარო. ენციკლოპედიური სტატია უნდა იყოს გამყარებული სანდო და გადამოწმებადი წყაროებით - გთხოვთ გამართოთ ეს სტატია შესაბამისი წყაროების მითითებით. მასალა გადამოწმებადი წყაროების გარეშე ითვლება საეჭვოდ და შეიძლება წაიშალოს. იმ შემთხვევაში, თუ არ იცით, როგორ ჩასვათ წყარო, იხ. დახმარების გვერდი. სასურველია ამის შესახებ აცნობოთ იმ მომხმარებლებსაც, რომელთაც მნიშვნელოვანი წვლილი მიუძღვით სტატიის შექმნაში. გამოიყენეთ: {{subst:წყაროს მითითება|უგრძესი საერთო ქვემიმდევრობის ამოცანა}} |
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
სქოლიო[რედაქტირება | წყაროს რედაქტირება]
- ↑ 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.
- ↑ 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.