ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 11:
การเชื่อมต่อระหว่าง[[ลำดับย่อยร่วมยาวสุด]] (Longest common subsequence (lcs)) และ[[ระยะทางที่ถูกแก้ไข]] (edit distance) สามารถแสดงในรูปสมการได้ดังนี้ d(''s1'',''s2'')=|''s1''|+|''s2''|-2lcs(''s1'',''s2'') ซึ่ง d(''s1'',''s2'') คือ[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ที่จะหาต้นทุนที่น้อยที่สุดในการแปลงสายอักขระหนึ่งไปเป็นอีกสายอักขระหนึ่ง โดยมีทั้งการแทรก การแทนที่ การลบ หรือ การกระทำที่ไม่มีผล เป็นต้น
[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]] (Hirschberg’s algorithm) สามารถอธิบายการทำงานได้หลายวิธี เช่น ใช้[[ขั้นตอนวิธีแวงเกอร์ – ฟิชเชอร์]] (Wanger – Fisher algorithm)<ref>[www.csci.agh.edu.pl/42
==ข้อมูลขั้นตอนวิธี==
| |||