ต้นไม้ลำเอียงที่เหมาะสมที่สุดในโครงสร้างข้อมูล

ปัญหาในการค้นหาโค้ดที่ไม่มีส่วนนำหน้าที่เหมาะสมที่สุดสำหรับต้นทุนตัวอักษรที่ไม่เท่ากันประกอบด้วยการคำนวณโค้ดที่ไม่มีส่วนนำหน้าต้นทุนขั้นต่ำ ซึ่งตัวอักษรสำหรับเข้ารหัสประกอบด้วยตัวอักษรต้นทุน (ความยาว) ที่ไม่เท่ากัน มีความยาว α และ β โดยที่ α ≤ β เราจำกัดตัวเองไว้ที่ไบนารีทรี

รหัสนี้แสดงด้วยต้นไม้ไม่สมมาตร เช่นเดียวกับต้นไม้ Huffman แทนวิธีแก้ปัญหาของปัญหาการเข้ารหัส Huffman แม้จะมีความคล้ายคลึงกัน แต่กรณีของต้นทุนจดหมายไม่เท่ากันนั้นยากกว่าปัญหาดั้งเดิมของฮัฟฟ์แมนมาก ไม่มีอัลกอริธึมเวลาพหุนามใดเป็นที่รู้จักหรือมีให้สำหรับต้นทุนตัวอักษรทั่วไป แม้ว่าจะมีบทความมากมายเกี่ยวกับปัญหาก็ตาม

อย่างไรก็ตาม มีอัลกอริธึมเวลาพหุนามที่ใช้ได้ α และ β เป็นค่าคงที่จำนวนเต็ม

ปัญหาของการคำนวณต้นไม้ที่มีต้นทุนน้อยที่สุดในกรณีนี้ได้รับการศึกษาครั้งแรกโดย Karp ในปี 1961 ซึ่งแก้ปัญหาด้วยการลดลงเป็นโปรแกรมเชิงเส้นตรงจำนวนเต็ม สร้างอัลกอริทึมแบบเอ็กซ์โพเนนเชียลในทั้ง n และ β ตั้งแต่นั้นมาก็มีงานด้านปัญหาต่างๆ มากมาย เช่น กำหนดราคาต้นไม้ที่เหมาะสมที่สุด ข้อจำกัดเป็นกรณีพิเศษเมื่อน้ำหนักเท่ากันทุกประการ

แม้จะมีความพยายามทั้งหมดนี้ ก็ยังไม่ทราบแน่ชัดว่าปัญหาพื้นฐานนั้นแก้ได้เวลาพหุนามหรือใน NP -complete

Golin และ Rote อธิบายอัลกอริทึมการเขียนโปรแกรมแบบไดนามิก O(nβ+2)-time ที่สร้างแผนผังจากบนลงล่าง

สิ่งนี้ได้รับการปรับปรุงโดยใช้วิธีการที่แตกต่างกัน (แนวคิดโมโนโทน-เมทริกซ์ เช่น คุณสมบัติ Monge และอัลกอริทึม SMAWK

ทฤษฎีบท 1:ต้นไม้ต้นไม่เรียบที่เหมาะสมที่สุดสามารถสร้างได้ในเวลา O(nβ )

นี่เป็นอัลกอริธึมที่รู้จักมีประสิทธิภาพมากที่สุดสำหรับกรณีที่มีค่า β เล็กน้อย ในทางปฏิบัติ ค่าใช้จ่ายของจดหมายมักจะน้อย (เช่น รหัสมอร์ส)

เมื่อเร็ว ๆ นี้ได้มีการจัดทำโครงร่างของอัลกอริทึมการประมาณที่มีประสิทธิภาพ

ทฤษฎีบท 2

มีรูปแบบการประมาณเวลาแบบพหุนามสำหรับต้นไม้ทรงโค้งที่เหมาะสมที่สุด