บทความนี้อธิบายถึงปัญหาต่อมาที่ยาวนานที่สุด (LCs) ของอัลกอริทึม Java แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
คำอธิบายปัญหา: ลำดับของลำดับที่กำหนดคือลำดับที่ได้รับหลังจากองค์ประกอบหลายอย่างถูกลบออกจากลำดับ เพื่อให้แม่นยำหากได้รับลำดับ x = {x1, x2, …, xm} ดังนั้นอีกลำดับ z = {z1, z2, …, zk} เป็นลำดับของ x หมายถึงการดำรงอยู่ของลำดับตัวห้อยที่เพิ่มขึ้นอย่างเคร่งครัด {i1, i2, …, ik} ตัวอย่างเช่นลำดับ z = {b, c, d, b} เป็นลำดับของลำดับ x = {a, b, c, b, d, a, b} และลำดับการย่อยที่เพิ่มขึ้นที่สอดคล้องกันคือ {2,3,5,7} ให้สองลำดับ x และ y เมื่อลำดับอื่น ๆ z เป็นทั้งลำดับของ x และ y, z เรียกว่าลำดับที่พบบ่อยของลำดับ x และ y ตัวอย่างเช่นถ้า x = {a, b, c, b, d, a, b} และ y = {b, d, c, a, b, a A} ยังเป็นลำดับที่พบบ่อยของ X และ Y ยิ่งไปกว่านั้นหลังเป็นหนึ่งในลำดับที่ยาวที่สุดที่ยาวที่สุดของ X และ Y เนื่องจาก X และ Y ไม่มีความยาวทั่วไปมากกว่า 4 ได้รับสองลำดับ x = {x1, x2, …, xm} และ y = {y1, y2, …, yn}
การวิเคราะห์ปัญหา: ให้ x = {a, b, c, b, d, a, b}, y = {b, d, c, a, b, a} วิธีที่ง่ายที่สุดในการค้นหาลำดับที่ยาวที่สุดของ X และ Y คือวิธีที่ครบถ้วนสมบูรณ์ สำหรับหลายลำดับของ x ตรวจสอบว่ามันเป็นลำดับของ y หรือไม่ดังนั้นจึงพิจารณาว่ามันเป็นลำดับที่พบบ่อยของ X และ Y จากคุณสมบัติของชุดชุดที่มีองค์ประกอบ m มีทั้งหมด 2^m ที่แตกต่างกัน การย่อยสลายเพิ่มเติมลักษณะปัญหาปัญหาที่ตามมาทั่วไปที่ยาวนานที่สุดจริง ๆ แล้วมีคุณสมบัติพื้นฐานที่ดีที่สุด
สมมติว่าลำดับที่ยาวที่สุดของลำดับ x = {x1, x2, ... xm} และ y = {y1, y2, ... yn} คือ z = {z1, z2, ... zk} แล้วก็มี:
(1) ถ้า xm = yn ดังนั้น zk = xm = yn และ zk-1 เป็นลำดับที่ยาวที่สุดที่ยาวที่สุดของ XM-1 และ YN-1
(2) ถ้า xm! = yn และ zk! = xm ดังนั้น z จะเป็นลำดับที่ยาวที่สุดของ XM-1 และ Y
(3) ถ้า xm! = yn และ zk! = yn ดังนั้น z เป็นลำดับที่ยาวที่สุดของ x และ yn-1
ที่ไหน, xm-1 = {x1, x2 … xm-1}, yn-1 = {y1, y2 … yn-1}, zk-1 = {z1, z2 … zk-1}
ความสัมพันธ์แบบเรียกซ้ำ: ใช้ c [i] [j] เพื่อบันทึกความยาวของลำดับที่ยาวที่สุดของลำดับ XI และ YJ ที่ไหน, xi = {x1, x2 … xi}, yj = {y1, y2 … yj} เมื่อ i = 0 หรือ j = 0 ลำดับที่ว่างเปล่าเป็นลำดับที่ยาวที่สุดของ XI และ YJ ในเวลานี้ c [i] [j] = 0; เมื่อฉัน, j> 0, xi = yj, c [i] [j] = c [i-1] [j-1] +1; เมื่อฉัน, j> 0, xi! = yj,
c [i] [j] = สูงสุด {c [i] [j-1], c [i-1] [j]} ดังนั้นจึงสร้างความสัมพันธ์แบบเรียกซ้ำได้ดังนี้:
สร้างวิธีแก้ปัญหาที่ดีที่สุด: จากการวิเคราะห์ข้างต้นเราจะเห็นว่าเพื่อค้นหาลำดับที่ยาวที่สุดของ x = {x1, x2, ... xm} และ y = {y1, y2, ... yn} คุณสามารถดำเนินการอีกครั้งในทางต่อไป Y. เมื่อ xm! = yn ต้องแก้ไขปัญหาย่อยสองข้อนั่นคือเพื่อค้นหาหนึ่งในลำดับย่อยที่ยาวที่สุดของ XM-1 และ Y และหนึ่งในลำดับย่อยที่ยาวที่สุดของ X และ YN-1 อีกต่อไปของการเรียงลำดับทั่วไปทั้งสองนี้คือลำดับที่ยาวที่สุดของ X และ Y สมมติว่าอาร์เรย์ B [i] [j] บันทึกค่าของ C [i] [j] ซึ่งได้รับปัญหาย่อย เริ่มต้นจาก b [m] [n] ค้นหาในอาร์เรย์ B ตามค่าของมัน เมื่อ b [i] [j] = 1 การต่อมาที่ยาวที่สุดของ Xi และ YJ คือลำดับที่ได้จากการเพิ่ม XI ลงในหางของ XI-1 และ YJ-1 เมื่อ b [i] [j] = 2 หมายความว่าการต่อมาที่ยาวที่สุดของ XI และ YJ นั้นเหมือนกับการต่อเนื่องที่ยาวที่สุดของ XI-1 และ YJ-1 เมื่อ b [i] [j] = 3 การต่อมาที่ยาวที่สุดของ XI และ YJ นั้นเหมือนกับการต่อมาที่ยาวที่สุดของ XI และ YJ-1
รหัสมีดังนี้:
แพ็คเกจ lcs; คลาสสาธารณะ LCS {สาธารณะคงที่ int [] [] lcslength (สตริง [] x, สตริง [] y) {int m = x.length; int n = y.length; int [] [] b = new int [x.length] [y.length]; int [] [] c = new int [x.length] [y.length]; สำหรับ (int i = 1; i <m; i ++) {c [i] [0] = 0; } สำหรับ (int i = 1; i <n; i ++) {c [0] [i] = 0; } สำหรับ (int i = 1; i <m; i ++) {สำหรับ (int j = 1; j <n; j ++) {ถ้า (x [i] == y [j]) {c [i] [j] = c [i-1] [j-1]+1; b [i] [j] = 1; } อื่นถ้า (c [i-1] [j]> = c [i] [j-1]) {c [i] [j] = c [i-1] [j]; b [i] [j] = 2; } else {c [i] [j] = c [i] [j-1]; b [i] [j] = 3; }}} return b; } โมฆะคงที่สาธารณะ LCS (int [] [] b, string [] x, int i, int j) {ถ้า (i == 0 || j == 0) return; if (b [i] [j] == 1) {lcs (b, x, i - 1, j - 1); System.out.print (x [i] + ""); } อื่นถ้า (b [i] [j] == 2) {lcs (b, x, i - 1, j); } else lcs (b, x, i, j-1); } โมฆะคงที่สาธารณะหลัก (สตริง args []) {system.out.println ("ผลการทดสอบ wulin.com:"); String [] x = {"", "A", "B", "C", "B", "D", "A", "B"}; String [] y = {"", "B", "D", "C", "A", "B", "A"}; int [] [] b = lcslength (x, y); System.out.println ("ลำดับที่ยาวที่สุดของ X และ Y คือ:"); LCS (B, X, X.Length - 1, Y.Length - 1); -ผลการทำงาน:
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน