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

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

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

ตัวอย่าง

ตัวอย่างเช่น มีข้อความสองข้อความให้มา สมมติว่า:

Pattern_1 = “RGBGARGA”
Pattern_2 = “BGRARG”

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

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

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

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

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

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

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

วิธีการแบบง่าย (Naive method) เป็นวิธีการแก้ปัญหาที่เรียบง่าย โดยไม่คำนึงถึงความซับซ้อนของเวลาและปัจจัยการปรับให้เหมาะสมอื่นๆ วิธีการนี้ประกอบด้วย "การใช้กำลังทั้งหมด" (brute force) การวนลูปหลายครั้ง และการเรียกซ้ำในกรณีส่วนใหญ่ คำว่า "การใช้กำลังทั้งหมด" หมายถึงการลองทุกรูปแบบที่เป็นไปได้สำหรับปัญหาที่กำหนด

ตัวอย่าง

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

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

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

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

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

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

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

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

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

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

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

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

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

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

คำว่าโครงสร้างย่อยที่เหมาะสมที่สุด หมายความว่าสามารถหาคำตอบที่เหมาะสมที่สุดได้โดยการแก้ปัญหาย่อย ตัวอย่างเช่น ในตัวอย่างข้างต้น เรามีรูปแบบที่ 1 และรูปแบบที่ 2

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

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

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

โครงสร้างแบบเรียกซ้ำของปัญหา LCS

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

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

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

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

เพื่อให้ได้ผลลัพธ์ที่ดีที่สุด เราจึงมีแนวทางดังนี้ การเขียนโปรแกรมแบบไดนามิก (ดีพี).

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

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

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

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

ชื่อเล่น Code:

def lcs:
    input: pattern_1, pattern_2, len_1, len_2
    if len_1 or len_2 is zero:
        return 0
    if pattern_1[len_1 - 1] equals 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))

การนำไปปฏิบัติใน 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

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

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("Length of LCS is: ", lcs(pattern_1, pattern_2, len(pattern_1), len(pattern_2)))

Output:

Length of LCS is:  5

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

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

เราจะใช้อาร์เรย์ 2 มิติที่มีขนาด m x n โดยที่ m และ n คือความยาวของแพทเทิร์น 1 และแพทเทิร์น 2 ตามลำดับ สำหรับ a อาร์เรย์ 2 มิติเราสามารถใช้โครงสร้างข้อมูลแบบลิสต์ได้ใน Python หรือโครงสร้างข้อมูลเวกเตอร์/อาร์เรย์ใน C++.

ชื่อเล่น Code สำหรับ 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 < n + 1; i++) {
    for (int j = 0; j < 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 เราจะคำนวณแต่ละงานเพียงครั้งเดียวเท่านั้น ในขณะที่วิธีการเรียกซ้ำอาจเกิดการทับซ้อนกันได้ping ปัญหาย่อย

ในอัลกอริทึมการเขียนโปรแกรมแบบไดนามิกนี้ เรากำลังใช้เมทริกซ์ 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] ไม่เท่ากับ pattern2[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

คำถามที่พบบ่อย