DAA - ผลที่ตามมาโดยทั่วไปที่ยาวที่สุด

ปัญหาลำดับต่อมาที่ยาวที่สุดคือการค้นหาลำดับที่ยาวที่สุดซึ่งมีอยู่ทั้งในสตริงที่กำหนด

ต่อมา

ให้เราพิจารณาลำดับ S = <s 1 , s 2 , s 3 , s 4 , …, s n >

ลำดับ Z = <z 1 , z 2 , z 3 , z 4 , …, z m > ส่วน S เรียกว่าลำดับต่อมาของ S ถ้าได้มาจากการลบ S ของบางองค์ประกอบเท่านั้น

ผลที่ตามมาทั่วไป

สมมติ, X และ Yเป็นสองลำดับเหนือชุดองค์ประกอบที่ จำกัด เราสามารถพูดได้ว่าZ เป็นผลสืบเนื่องมาจาก X และ Y, ถ้า Z เป็นผลมาจากทั้งสองอย่าง X และ Y.

ลำดับต่อมาที่ยาวที่สุด

หากมีการกำหนดชุดของลำดับปัญหาต่อมาที่พบบ่อยที่สุดคือการค้นหาลำดับต่อมาทั่วไปของลำดับทั้งหมดที่มีความยาวสูงสุด

ปัญหาต่อมาที่พบบ่อยที่สุดคือปัญหาทางวิทยาศาสตร์คอมพิวเตอร์แบบคลาสสิกซึ่งเป็นพื้นฐานของโปรแกรมเปรียบเทียบข้อมูลเช่นโปรแกรมอรรถประโยชน์ที่แตกต่างและมีการใช้งานด้านชีวสารสนเทศศาสตร์ นอกจากนี้ยังใช้กันอย่างแพร่หลายโดยระบบควบคุมการแก้ไขเช่น SVN และ Git สำหรับการกระทบยอดการเปลี่ยนแปลงหลายรายการกับคอลเล็กชันไฟล์ที่ควบคุมการแก้ไข

วิธีไร้เดียงสา

ปล่อย X เป็นลำดับความยาว m และ Y ลำดับความยาว n. ตรวจสอบทุกครั้งที่มาของX ไม่ว่าจะเป็นผลพวงของ Yและส่งคืนค่าต่อมาที่พบบ่อยที่สุดที่พบ

มี 2m ลำดับต่อมาของ X. ลำดับการทดสอบว่าเป็นลำดับต่อมาของหรือไม่Y ใช้เวลา O(n)เวลา. ดังนั้นอัลกอริทึมไร้เดียงสาจะใช้O(n2m) เวลา.

การเขียนโปรแกรมแบบไดนามิก

ให้X = <x 1 , x 2 , x 3 , …, x m > และY = <y 1 , y 2 , y 3 , …, y n >เป็นลำดับ ในการคำนวณความยาวขององค์ประกอบจะใช้อัลกอริทึมต่อไปนี้

ในขั้นตอนนี้ตาราง C[m, n] คำนวณตามลำดับหลักของแถวและอีกตารางหนึ่ง B[m,n] คำนวณเพื่อสร้างโซลูชันที่เหมาะสมที่สุด

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B
Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

อัลกอริทึมนี้จะพิมพ์ลำดับต่อมาที่ยาวที่สุดของ X และ Y.

การวิเคราะห์

ในการเติมข้อมูลตารางด้านนอก for วนซ้ำ m ครั้งและภายใน for วนซ้ำ nครั้ง. ดังนั้นความซับซ้อนของอัลกอริทึมคือO (m, n)โดยที่m และ n คือความยาวของสองสาย

ตัวอย่าง

ในตัวอย่างนี้เรามีสองสาย X = BACDB และ Y = BDCB เพื่อค้นหาลำดับต่อมาที่ยาวที่สุด

ตามอัลกอริทึม LCS-Length-Table-Formulation (ตามที่ระบุไว้ข้างต้น) เราได้คำนวณตาราง C (แสดงทางด้านซ้ายมือ) และตาราง B (แสดงทางด้านขวามือ)

ในตาราง B แทนที่จะเป็น 'D', 'L' และ 'U' เราใช้ลูกศรทแยงมุมลูกศรซ้ายและลูกศรขึ้นตามลำดับ หลังจากสร้างตาราง B แล้ว LCS จะถูกกำหนดโดยฟังก์ชัน LCS-Print ผลลัพธ์คือ BCB