ลำดับต่อมาที่ยาวที่สุด: Python, C++ ตัวอย่าง

ลำดับต่อมาที่ยาวที่สุดคืออะไร?

Longest Common Subsequence (LCS) หมายความว่าคุณจะได้รับสองสตริง/รูปแบบ/ลำดับของอ็อบเจ็กต์ ในลำดับ/สตริงทั้งสองนี้ คุณต้องค้นหาลำดับย่อยที่ยาวที่สุดขององค์ประกอบในลำดับเดียวกันที่ปรากฏทั้งในสตริงหรือรูปแบบ

ตัวอย่าง

ตัวอย่างเช่น มีสองสตริงที่ให้มา

สมมุติว่า

Pattern_1 = “RGBGARGA”
Pattern_2 = “BGRARG”

• จาก pattern_1 สามารถสร้างลำดับได้เช่น “RGB”, “RGGA”, ”RGAR” ในการสร้างลำดับ คุณต้องรักษาตำแหน่งสัมพัทธ์ของอักขระแต่ละตัวในสตริง
• จาก pattern_2 เราสามารถสร้างลำดับเช่น "BGR", "BRAG", "RARG" ลำดับสามารถสร้างได้ตราบใดที่ยังคงรักษาตำแหน่งสัมพัทธ์ของสตริงดั้งเดิม

คำว่าตำแหน่งสัมพัทธ์หมายถึงความเป็นระเบียบ

ตัวอย่างเช่น “BRG” เป็นลำดับที่ถูกต้องเนื่องจาก “B” ปรากฏก่อน จากนั้น “R” ตามด้วย “G” ในรูปแบบสตริงดั้งเดิม_2 อย่างไรก็ตาม หากลำดับเป็น “RBRG” ก็ถือว่าไม่ถูกต้อง เนื่องจากในสตริงดั้งเดิม (pattern_2) “B” มาก่อน

เรามีสองทางเลือกในการค้นหาลำดับย่อยร่วมที่ยาวที่สุดจากสองลำดับหรืออาร์เรย์ที่กำหนด

• วิธีการไร้เดียงสา
• โซลูชันการเขียนโปรแกรมแบบไดนามิก: ลำดับย่อยทั่วไปที่ยาวที่สุดเรียกอีกอย่างว่า LCS

โซลูชันแบบไร้เดียงสาจะมีความซับซ้อนของเวลาที่มากกว่าและไม่ใช่โซลูชันที่ดีที่สุด การใช้โซลูชันการเขียนโปรแกรมแบบไดนามิก (DP) ช่วยให้เราเอาชนะปัญหาความซับซ้อนได้

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

วิธีการที่ไร้เดียงสาเป็นแนวทางที่เรียบง่ายในการแก้ปัญหาโดยไม่คำนึงถึงความซับซ้อนของเวลาและปัจจัยการเพิ่มประสิทธิภาพอื่นๆ

วิธีไร้เดียงสาประกอบด้วย "Brute Force", หลายลูป, วิธีการเรียกซ้ำในกรณีส่วนใหญ่

คำว่ากำลังดุร้ายหมายถึงการผ่านรูปแบบที่เป็นไปได้ทั้งหมดสำหรับปัญหาที่กำหนด

ตัวอย่าง

จากตัวอย่างข้างต้นของ pattern1 และ pattern2 ให้เราถือว่า pattern1 มีความยาว m และ pattern2 มีความยาว n เพื่อตรวจสอบทุกกรณีที่เป็นไปได้ เราจำเป็นต้องประเมินทุกลำดับย่อยที่เป็นไปได้ของ pattern1 ด้วย pattern2

นี่คือสตริงตัวอักษร 4 ตัวง่ายๆ “ABCD” ตัวอย่างเช่น เราต้องสร้างลำดับจาก "ABCD" ไม่ว่าเราจะรับตัวละครหรือไม่ก็ตาม นั่นหมายความว่าสำหรับตัวละครแต่ละตัว เรามีสองทางเลือก

พวกเขาจะ:

• ตัวละครจะถูกเพิ่มเข้าไปในลำดับถัดไป
• อักขระจะไม่ถูกเพิ่มลงในลำดับถัดไป

ในที่นี้ รูปภาพจะแสดงลำดับทั้งหมดที่เราสามารถสร้างได้จากสตริง “ABCD”

ลำดับที่มี 1 ตัวอักษร:

ลำดับที่มี 2 ตัวอักษร:

ลำดับที่มี 3 ตัวอักษร:

จากแผนภาพด้านบน มี 14 ลำดับ หากเราไม่ใช้ตัวอักษร โดยพื้นฐานแล้วจะเป็นสตริงว่าง ลำดับทั้งหมดจะเป็น 15 นอกจากนี้ สตริง “ABCD” เองก็เป็นลำดับเช่นกัน ดังนั้นลำดับทั้งหมดคือ 16

ดังนั้นจึงเป็นไปได้ที่จะสร้าง 2⁴ หรือ 16 ลำดับจาก “ABCD” จากนั้นเป็นสตริงที่มีความยาว m จะต้องเป็นผลรวมของลำดับที่ 2^m.

สำหรับแต่ละลำดับย่อย เราจำเป็นต้องตรวจสอบรูปแบบทั้งหมด2 ซึ่งจะใช้เวลา 0(n) 0(n) หมายถึงฟังก์ชันความซับซ้อนที่คำนวณเวลาที่ใช้ในการดำเนินการ

ดังนั้นความซับซ้อนของเวลาทั้งหมดจึงกลายเป็น โอ(น*2^m). ตัวอย่างเช่น เราได้เห็นค่าเหนือค่า m=8 และ n=5

ต่อไปนี้เป็นขั้นตอนของวิธีไร้เดียงสา:

ขั้นตอน 1) หาลำดับจากรูปแบบที่ 1
ขั้นตอน 2) จับคู่ลำดับจากขั้นตอนที่ 1 กับรูปแบบที่ 2
ขั้นตอน 3) หากตรงกัน ให้บันทึกลำดับถัดไป
ขั้นตอน 4) หากมีลำดับเหลืออยู่ใน pattern1 ให้ไปที่ขั้นตอนที่ 1 อีกครั้ง
ขั้นตอน 5) พิมพ์ลำดับที่ยาวที่สุด

โครงสร้างพื้นฐานที่เหมาะสมที่สุด

คำว่าโครงสร้างย่อยที่เหมาะสมที่สุดหมายถึงวิธีแก้ปัญหาที่ดีที่สุด (แบบง่าย) สามารถพบได้โดยการแก้ปัญหาย่อย ตัวอย่างเช่น ในตัวอย่างข้างต้น เรามี pattern1 และ pattern2

ขั้นตอน 1) นำอักขระสองตัวแรกจากแต่ละรูปแบบ

ขั้นตอน 2) ใช้อักขระตัวที่สามถึงห้าจากแต่ละรูปแบบ

ขั้นตอน 3) ดำเนินการต่อในทำนองเดียวกันกับอักขระที่เหลือ

เราค้นหา LCS บนสตริงย่อย (สตริงที่สร้างจากสตริงดั้งเดิม) จากนั้นเราจะเก็บบันทึกความยาวของ LCS ของสตริงย่อย

นี่ก็เป็นอีกหนึ่งทรัพย์สินที่น่าสนใจนั่นก็คือ ปัญหาย่อยที่ทับซ้อนกัน- กล่าวกันว่าปัญหามีปัญหาย่อยที่ทับซ้อนกัน หากคำชี้แจงปัญหาสามารถแบ่งออกเป็นปัญหาย่อยเล็กๆ และนำไปใช้หลายครั้งในโปรแกรม

แผนภาพด้านล่างแสดงให้เห็นว่าอัลกอริธึมแบบเรียกซ้ำเรียกใช้ฟังก์ชันที่มีพารามิเตอร์เดียวกันหลายครั้ง

ตัวอย่างเช่น ลองดูแผนผังการเรียกซ้ำ

ในกล่องสีเข้ม คุณจะสังเกตเห็นปัญหาที่ทับซ้อนกันได้ (“RG”, “RA”), (“RG”,”R”) และอื่นๆ จะถูกเรียกหลายครั้ง

เพื่อเพิ่มประสิทธิภาพนี้ เรามีแนวทางของ การเขียนโปรแกรมแบบไดนามิก (ดีพี).

วิธีการเรียกซ้ำของลำดับการสื่อสารที่ยาวที่สุด

กราฟที่แสดงด้านบนเป็นวิธีการเรียกซ้ำ แต่ละฟังก์ชันแบบเรียกซ้ำมีกรณีพื้นฐานที่จะแยกการเรียกซ้ำหรือเริ่มส่งคืนจากสแต็ก

สำหรับการนำไปใช้นี้ เราจะใช้กรณีพื้นฐาน ดังนั้น ขั้นตอนวิธี เป็นเหมือนกับต่อไปนี้:

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

รหัสหลอก:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
if len_1 or len_2 is zero:
    then
return 0
if pattern_1[len_1 - 1] equals pattern_2[len_2 - 1]
then
return 1 + lcs(pattern_1, pattern_2,
    len_1 - 1, len_2 - 1)
else
    max of lcs(pattern_1, pattern_2, len_1 - 1, len_2),
    lcs(pattern_1, pattern_2, len_1, len_2 - 1)

การนำไปปฏิบัติใน C++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int lcs(string pattern_1, string pattern_2, int len_1, int len_2) {
  if (len_1 == 0 || len_2 == 0)
    return 0;
  if (pattern_1[len_1 - 1] == pattern_2[len_2 - 1]) {
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1);
  } else {
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1));
  }
}
int main() {
  string pattern_1, pattern_2;
  pattern_1 = "RGBGARGA";
  pattern_2 = "BGRARG";
  cout<<"Length of LCS is: "<<lcs(pattern_1, pattern_2, pattern_1.size(), pattern_2.size())<<endl;
}

Output:

Length of LCS is: 5

การใช้งานในหลาม

def lcs(pattern_1, pattern_2, len_1, len_2):
    if len_1 == 0 or len_2 == 0:
    return 0
if pattern_1[len_1 - 1] == pattern_2[len_2 - 1]:
    return 1 + lcs(pattern_1, pattern_2, len_1 - 1, len_2 - 1)
else :
    return max(lcs(pattern_1, pattern_2, len_1 - 1, len_2), lcs(pattern_1, pattern_2, len_1, len_2 - 1))
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Lenght of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Output:

Lenght of LCS is:  5

วิธีการโปรแกรมแบบไดนามิกของลำดับที่ยาวที่สุดร่วม (LCS)

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

เราจะใช้อาร์เรย์ 2 มิติที่มีขนาด mxn โดยที่ m และ n คือความยาวของ pattern1 และ pattern2

สำหรับ อาร์เรย์ 2 มิติเราสามารถใช้โครงสร้างข้อมูลแบบรายการใน Python หรือโครงสร้างข้อมูลแบบเวกเตอร์/อาร์เรย์ได้ C++.

รหัสหลอกสำหรับ LCS โดยใช้ DP:

LCS(pattern_1, pattern_2):
    m = length of pattern_1 + 1
n = length of pattern_2 + 1
dp[n][m]
for i in range 0 to n + 1:
    for j in range 0 to m + 1:
    if i or j equals to 0:
    dp[i][j] = 0
else if pattern_1[i] == pattern_2[j]:
    dp[i]][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]

นี่คือตาราง LCS ที่ใช้เป็นโครงสร้างข้อมูลอาร์เรย์ 2 มิติสำหรับวิธีการเขียนโปรแกรมแบบไดนามิก

เรามาหารือเกี่ยวกับตรรกะที่เราใช้ที่นี่ ขั้นตอนคือ:

ขั้นตอน 1) ถ้า i หรือ j เป็นศูนย์ เรากำลังนำสตริงว่างจากสองสตริงที่กำหนดและพยายามค้นหาลำดับย่อยร่วม อย่างไรก็ตาม เนื่องจากสตริงย่อยที่เรากำลังหาว่างเปล่า ความยาวของลำดับถัดไปจึงเป็น 0

ขั้นตอน 2) หากอักขระสองตัวตรงกัน เราจะกำหนดค่าให้กับดัชนี (i,j) โดยการเพิ่ม LCS ที่คำนวณไว้ก่อนหน้านี้ ซึ่งมีอยู่ในดัชนี (i-1,j-1) (จากแถวก่อนหน้า)

ขั้นตอน 3) หากไม่ตรงกัน เราจะใช้ LCS สูงสุดของดัชนีสองตัวที่อยู่ติดกัน ด้วยวิธีนี้ เราจำเป็นต้องกรอกค่าทั้งหมดในอาร์เรย์ 2 มิติ

ขั้นตอน 4) สุดท้ายนี้ เราจะคืนค่าของเซลล์สุดท้ายของอาร์เรย์ 2D

โดยพื้นฐานแล้ว ค่าทั้งหมดในอาร์เรย์ 2 มิติประกอบด้วยความยาวของลำดับย่อยทั่วไป ในจำนวนนี้ เซลล์สุดท้ายประกอบด้วยความยาวของลำดับย่อยร่วมที่ยาวที่สุด

การนำไปปฏิบัติใน C++

#include<iostream>
using namespace std;
int lcs(string pattern_1, string pattern_2) {
  int m = pattern_1.size();
  int n = pattern_2.size();
  // dp will store solutions as the iteration goes on
  int dp[n + 1][m + 1];
  for (int i = 0; i & lt; n + 1; i++) {
    for (int j = 0; j & lt; m + 1; j++) {
      if (i == 0 || j == 0) {
        dp[i][j] = 0;
      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[n][m];
}
int main() {
  string pattern_1 = "RGBGARGA";
  string pattern_2 = "BGRARG";
  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;
}

Output:

Length of LCS: 5

การนำไปปฏิบัติใน Python

def lcs(pattern_1, pattern_2):
    m = len(pattern_1)
n = len(pattern_2)
# dp will store solutions as the iteration goes on
dp = [
    [None] * (n + 1) for item in range(m + 1)
]
for i in range(m + 1):
    for j in range(n + 1):
    if i == 0 or j == 0:
    dp[i][j] = 0
elif pattern_1[i - 1] == pattern_2[j - 1]:
    dp[i][j] = dp[i - 1][j - 1] + 1
else :
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
pattern_1 = "RGBGARGA"
pattern_2 = "BGRARG"
print("Length of LCS: ", lcs(pattern_1, pattern_2))

Output:

Length of LCS: 5

ดังนั้น สตริงทั้งสองมีลำดับย่อยร่วมที่ยาวที่สุดที่มีความยาว 5

โดยสรุป เราเพียงแต่คำนวณแต่ละงานเพียงครั้งเดียวในวิธี DP ในวิธี DP ในวิธีการเรียกซ้ำ เราอาจมีปัญหาย่อยที่ทับซ้อนกัน

ในอัลกอริทึมการเขียนโปรแกรมแบบไดนามิกนี้ เรากำลังใช้เมทริกซ์ 2 มิติ จะมีการกำหนดไว้สองสาย (สมมติว่าทั้งสองมีความยาว n) ดังนั้นพื้นที่ที่ต้องการในอาร์เรย์คือ nx n หากสตริงมีขนาดใหญ่เพียงพอ เราจะต้องมีเวอร์ชันเพิ่มประสิทธิภาพหน่วยความจำของโซลูชัน DP

ตรรกะแบบง่ายที่ใช้ในโค้ดคือ:

• ประกาศอาร์เรย์ 2 มิติ DP[m][n]
• เติมแถวแรกและคอลัมน์แรกของอาร์เรย์ DP ด้วย 0
• เอา i และ j สำหรับการวนซ้ำ
• หาก pattern1[i] เท่ากับ pattern2[j] ให้อัปเดต DP[i][j] = DP[i-1][j-1] + 1
• หาก pattern1[i] ไม่เท่ากับรูปแบบ2[j] ดังนั้น DP[i][j] จะเป็นค่าสูงสุดระหว่าง DP[i-1][j] และ DP[i][j-1]
• ทำต่อไปจนกระทั่ง i และ j ถึง m และ n
• องค์ประกอบสุดท้ายหรือ DP[m-1][n-1] จะมีความยาว

ในที่นี้จะระบุเป็น DP[m-1][n-1] เนื่องจากดัชนีอาร์เรย์เริ่มต้นจาก 0

สรุป

• วิธี DP มีความซับซ้อนของเวลาต่ำกว่า คือ O(mn) โดยที่ m และ n คือความยาวของสตริงอินพุตหรืออาร์เรย์
• DP เป็นวิธีการที่เร็วกว่าแบบเรียกซ้ำ โดยมีความซับซ้อนของเวลา โอ(น*2^m).
• การเขียนโปรแกรมแบบไดนามิก (DP) ไม่ได้รับการปรับให้เหมาะสมกับหน่วยความจำ เราใช้อาร์เรย์ 2 มิติที่มีความยาว m*n ดังนั้นความซับซ้อนของพื้นที่คือ (m*n)
• ในกรณีที่เลวร้ายที่สุด วิธีการเรียกซ้ำ ในกรณีที่เลวร้ายที่สุด หน่วยความจำสูงสุดที่จะครอบครองคือ m+n โดยทั่วไปคือความยาวรวมของสตริงที่ป้อน
• คอมพิวเตอร์สมัยใหม่ในปัจจุบันเพียงพอที่จะรองรับหน่วยความจำจำนวนนี้ได้