ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของเฮิร์ชเบิร์ก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
บรรทัด 1:
{{ลิงก์ไปภาษาอื่น}}
{{issues|ปรับภาษา=yes|จัดรูปแบบ=yes|ต้องการอ้างอิง=yes}}
'''[[ขั้นตอนวิธีของเฮิร์ชเบิร์ก]]''' เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้น [[แดน เฮิร์ชเบิร์ก]] (Dan Hirschberg) ซึ่งขั้นตอนวิธีนี้เป็น[[ขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต]] (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหา[[ลำดับย่อยร่วมยาวสุด]] (Longest common subsequence) โดยขั้นตอนวิธีนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้[[ปริภูมิเชิงเส้น]] (Linear space) เพื่อหา[[ระยะทางที่ถูกแก้ไขของราเวนสตีน]] (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย
เส้น 27 ⟶ 28:
== รหัสเทียม ==
คำอธิบายระดับสูงของโปรแกรม
<source lang="text" line>
Forwards[x,y] is
เส้น 89 ⟶ 90:
ประโยชน์สำคัญอันหนึ่งของขั้นตอนวิธีนี้ คือ การหาการลำดับเรียงตัวของสาย DNA และสายโปรตีน ซึ่งมันเป็นวิธีที่มีประสิทธิภาพในการคำนวณ[[ลำดับย่อยร่วมยาวสุด]] (Longest cummon subsequence) ระหว่างกลุ่มข้อมูล 2 กลุ่มที่แตกต่างกัน
== ดู
* [[:en:Needleman-Wunsch algorithm]]
* [[:en:Smith Waterman algorithm]]
| |||