ขั้นตอนวิธีของเฮิร์ชเบิร์ก

ขั้นตอนวิธีของเฮิร์ชเบิร์ก เป็นขั้นตอนวิธีสำหรับการเปรียบเทียบของสายอักขระ มีชื่อมาจากผู้คิดค้น แดน เฮิร์ชเบิร์ก (Dan Hirschberg) ซึ่งขั้นตอนวิธีนี้เป็นขั้นตอนวิธีการเขียนโปรแกรมแบบพลวัต (Dynamic programming algorithm) ที่ถูกออกแบบมาเพื่อแก้ปัญหาลำดับย่อยร่วมยาวสุด (Longest common subsequence) โดยขั้นตอนวิธีนี้จะแก้ปัญหาการเปรียบเทียบสายอักขระโดยใช้ปริภูมิเชิงเส้น (Linear space) เพื่อหาระยะทางที่ถูกแก้ไขของราเวนสตีน (Levenshtein edit distance) ของสายอักขระ 2 สายที่เปรียบเทียบกันรวมทั้งหาการเรียงตัวของสายอักขระทั้งสองด้วย

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด k ตัว ขั้นตอนวิธีของฟลอยด์-วอร์แชล ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ ขั้นตอนวิธี ขั้นตอนวิธีเชิงพันธุกรรม ขั้นตอนวิธีฮังกาเรียน ขั้นตอนวิธีของชอร์ ขั้นตอนวิธีโบรน-เคอร์โบสท์ ขั้นตอนวิธีของเบลแมน-ฟอร์ด