Java Dynamic Programming แก้ไขปัญหาระยะทาง

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

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

สำหรับลำดับ S และ T ระยะห่างระหว่างพวกเขาถูกกำหนดเป็น: การดำเนินการต่อไปนี้หลายครั้งในหนึ่งในสอง: 1 ลบตัวละคร; 2, แทรกตัวละคร; 3 เปลี่ยนตัวละคร ทุกครั้งที่มีการดำเนินการการนับจะเพิ่มขึ้น 1 การนับขั้นต่ำของการหมุน S และ T เป็นลำดับที่เท่ากันคือระยะการแก้ไข (แก้ไข) หรือความคล้ายคลึงกันระหว่างทั้งสอง โปรดให้อัลกอริทึมที่เกี่ยวข้องและการใช้งาน

วิเคราะห์:

สมมติว่าความยาวของลำดับ S และ T เป็น M และ N ตามลำดับและระยะการแก้ไขระหว่างพวกเขาจะแสดงเป็นการแก้ไข [M] [n] จากนั้นมีสถานการณ์ต่อไปนี้เมื่อดำเนินการตามลำดับ:

. เมื่ออักขระสุดท้ายของ S และ T เท่ากันไม่มีการดำเนินการนิยามข้างต้น (เช่น "แก้ไข") สำหรับอักขระสุดท้ายนั่นคือไม่จำเป็นต้องนับจำนวน เงื่อนไขเป็นที่พอใจ: แก้ไข [m] [n] = แก้ไข [M-1] [N-1]

ข. เมื่ออักขระสุดท้ายของ S และ T ไม่เท่ากันจุดจบของพวกเขาทั้งสองจะต้องได้รับการแก้ไขและจำนวนที่สอดคล้องกันจะเพิ่มขึ้น 1

B1, ปรับเปลี่ยนจุดสิ้นสุดของ S หรือ T เพื่อให้เท่ากับ t หรือ s จากนั้นแก้ไข [m] [n] = แก้ไข [M-1] [N-1] +1;

B2, ลบองค์ประกอบในตอนท้ายของ S เพื่อให้ S และ T เท่ากันจากนั้นแก้ไข [M] [n] = แก้ไข [M-1] [n] +1;

B3, ลบองค์ประกอบที่ส่วนท้ายของ t เพื่อให้ T และ S เท่ากันจากนั้นแก้ไข [M] [n] = แก้ไข [M] [N-1] +1;

B4 เพิ่มองค์ประกอบหางของ T ในตอนท้ายของ S เพื่อให้ S และ T เท่ากันจากนั้นความยาวของ S จะกลายเป็น M+1 แต่ในเวลานี้องค์ประกอบสิ้นสุดของ S และ T มีค่าเท่ากันแล้ว คุณจะต้องเปรียบเทียบองค์ประกอบ M แรกของ S กับองค์ประกอบ N-1 แรกของ T ดังนั้นจึงแก้ไข [M] [n] = แก้ไข [M] [N-1] +1;

B5 เพิ่มองค์ประกอบหางของ S ในตอนท้ายของ t เพื่อให้ T และ S เท่ากัน สถานการณ์ในเวลานี้เหมือนกับ B4 การแก้ไขที่น่าพอใจ [m] [n] = แก้ไข [M-1] [n] +1;

ค. กรณีพิเศษคือเมื่อ s ว่างเปล่าแก้ไข [0] [n] = n; และเมื่อ t ว่างเปล่าให้แก้ไข [m] [0] = m; นี่เป็นเรื่องง่ายที่จะเข้าใจ ตัวอย่างเช่นสำหรับลำดับ "" และ "ABC" การดำเนินการขั้นต่ำของทั้งสองคือ 3 นั่นคือลำดับ "" ดำเนินการ 3 การดำเนินการแทรกหรือลำดับ "ABC" ดำเนินการลบ 3 การดำเนินการ

ดังนั้นจึงไม่ใช่เรื่องยากสำหรับเราที่จะอนุมานสมการการเขียนโปรแกรมแบบไดนามิกของระยะการแก้ไขระยะทางด้านบน:

ดังนั้นการใช้งานซ้ำของอัลกอริทึมการเขียนโปรแกรมแบบไดนามิกสำหรับระยะการแก้ไขสตริงสามารถแสดงได้ในรหัส Java ต่อไปนี้:

 public Static int editdistance (String A, String B) {ถ้า (a == null || b == null) {return -1; } return editdistance (a, a.length () - 1, b, b.length () - 1); } public Static Int EditDistance (String A, int M, String B, int n) {ถ้า (M <0 || n <0) {return 1; } อื่นถ้า (A.Charat (M) == B.Charat (n)) {return editdistance (a, m - 1, b, n - 1); } else {return math.min (math.min (editdistance (a, m - 1, b, n) + 1, editdistance (a, m, b, n - 1) + 1), editdistance (a, m - 1, b, n - 1) + 1); -

อัปเดต:

ในเวลาเดียวกันจากสมการการเขียนโปรแกรมแบบไดนามิกของระยะทางแก้ไขเราสามารถเห็นได้ว่าการแก้ไข [m] [n] สามารถได้มาจากการแก้ไข [m - 1] [n - 1], แก้ไข [m - 1] [n], แก้ไข [m] [n - 1] นั่นคือเราสามารถสำรวจอาร์เรย์สองมิติจากนั้นคำนวณค่าปัจจุบันผ่านการย้อนกลับ

ตัวอย่างเช่นสำหรับสตริง s = "Sailn" และ t = "ล้มเหลว" อาร์เรย์สองมิติจะเริ่มต้นเป็น:

เพราะ s [0] = s, t [0] = f, จากนั้น s [0]! = t [0] จากนั้นสอดคล้องกับเมทริกซ์สองมิติข้างต้นแก้ไข [1] [1] = นาที (แก้ไข [0] [0], แก้ไข [0] [1], แก้ไข [1] [0] 1 = 1.

สำหรับ s [1] = a, t [1] = a, s [1] = t [1], มันสอดคล้องกับเมทริกซ์สองมิติ, แก้ไข [2] [2] = แก้ไข [1] [1] ดังนั้นแก้ไข [2] [2] = 1 ดังนั้นตามกฎนี้

ดังนั้นระยะทางแก้ไขระหว่างทั้งสองคือแก้ไข [m] [n] = แก้ไข [5] [7] = 3

ดังนั้นตามแนวคิดข้างต้นเวอร์ชัน Java ของโซลูชันการย้อนรอยของการเขียนโปรแกรมแบบไดนามิกสามารถทำได้ดังนี้:

 public Static int editdistance (String A, String B) {ถ้า (a == null || b == null) {return -1; } int [] [] matrix = new int [a.length () + 1] [b.length () + 1]; สำหรับ (int i = 0; i <a.length ()+1; i ++) {สำหรับ (int j = 0; j <b.length ()+1; j ++) {ถ้า (i == 0) {matrix [i] [j] = j; } อื่นถ้า (j == 0) {matrix [i] [j] = i; } else {if (a.charat (i - 1) == b.charat (j - 1)) {matrix [i] [j] = matrix [i - 1] [j - 1]; } else {matrix [i] [j] = 1 + math.min (math.min (matrix [i - 1] [j], matrix [i] [j - 1]), matrix [i - 1]); }}} ส่งคืนเมทริกซ์ [a.length ()] [b.length ()]; -

สรุป

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