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