ปัญหาระดับบรรพบุรุษ

ในทฤษฎีกราฟ ปัญหาระดับบรรพบุรุษ  เป็นปัญหาในการนำต้นไม้ "T" มาคำนวณล่วงหน้าเพื่อตอบคำถามว่า จุดยอดที่มีความลึกระดับ "d" จากราก และทิศทางมุ่งสู่จุดยอด "v" คือจุดยอดอะไร เขียนฟังก์ชันแทนปัญหานี้ได้ว่า LA("v","d") โดยความลึกของจุดยอด "v" คือจำนวนเส้นเชื่อมจากรากถึงจุดยอดดังกล่าวบนวิถีสั้นสุดจากรากถึงจุดยอดนั้น
ปัญหาระดับบรรพบุรุษ.
ปัญหาระดับบรรพบุรุษเป็นปัญหาพื้นฐานบนกราฟต้นไม้อย่างหนึ่ง มีจุดประสงค์คือต้องการหาจุดยอดที่มีความลึก "d" จากจุดยอดราก "r" และมีทิศทางมุ่งเข้าสู่จุดยอด "v" ปัญหานี้มีความสัมพันธ์กับปัญหาบรรพบุรุษร่วมต่ำสุดซึ่งถามเกี่ยวกับจุดยอดที่เป็นบรรพบุรุษร่วมของจุดยอด 2 จุดและมีความลึกมากที่สุด และจะเห็นได้ว่าแนวคิดของปัญหาระดับบรรพบุรุษหลาย ๆ อย่างก็ได้นำไปใช้ในการแก้ไขปัญหาบรรพบุรุษร่วมต่ำสุดด้วย
ในการแก้ไขปัญหาระดับบรรพบุรุษนี้ วิธีเรียบง่ายสุดก็คือให้เริ่มที่จุดยอด "v" และค่อย ๆ กระโดดขึ้นทีละหนึ่งระดับไปเรื่อย ๆ จนเมื่อถึงระดับ "d" แล้วก็จะได้คำตอบ วิธีนี้ไม่ต้องมีการคำนวณล่วงหน้าเลย แต่กรณีเลวร้ายสุดคือต้องใช้เวลาถึง O("n") ซึ่งเสียเวลาเป็นอย่างมาก
เพื่อที่จะลดเวลาการตอบคำถามลง จึงอาจสร้างแถวลำดับ 2 มิติ และเก็บคำตอบทั้งหมดไว้ในตาราง ด้วยวิธีนี้การตอบคำถามก็จะเป็นเพียงการเรียกข้อมูลจากแถวลำดับมาตอบเท่านั้นซึ่งใช้เวลา O("1") อย่างไรก็ตามในการที่จะสร้างตารางคำตอบขึ้นมาก็ต้องใช้เวลาถึง O("n""2")
มีขั้นตอนวิธีมากมายที่คิดขึ้นมาเพื่อให้แก้ไขปัญหาระดับบรรพบุรุษได้โดยมีประสิทธิภาพดียิ่งขึ้น ตารางด้านล่างนี้แสดงถึงขั้นตอนวิธีที่มีประสิทธิภาพแตกต่างกันออกไปในการแก้ปัญหาระดับบรรพบุรุษ
ขั้นตอนวิธีตัวชี้กระโดด.
ขั้นตอนวิธีตัวชี้กระโดด (Jump pointer algorithm) เป็นขั้นตอนวิธีแบบกำหนดการพลวัต อาศัยการคำนวณล่วงหน้าโดยการสร้างแถวลำดับ 2 มิติ ชื่อ "dp" ขนาด "n" × log "n" โดย "dp"["v"]["p"] จะชี้ไปยังจุดยอดที่อยู่สูงขึ้นไปจากจุดยอด "v" เป็นจำนวน "2""p" ขั้น อาศัยความสัมพันธ์ว่า "dp"["v"]["p"] = "dp"["dp"["v"]["p" - "1"]]["p" - "1"] และกรณีฐานว่า dp["v"]["0"] คือพ่อของจุดยอด "v" ก็จะสามารถเติมตาราง "dp" ได้ในเวลา O("n" log "n")
ในการหาคำตอบ ให้เริ่มต้นจากจุดยอด "v" และกระโดดโดยใช้ตัวชี้จาก "dp" ไปให้สูงที่สุดแต่ไม่ไปไกลเกินจุดยอดเป้าหมาย และกระโดดต่อจากจุดยอดนั้นไปเรื่อย ๆ จนกว่าจะเจอจุดยอดเป้าหมาย เนื่องจากการหาตัวชี้ที่จะใช้นั้นสามารถทำได้ใน O("1") จากสูตร <math>\lfloor\log_2((\operatorname{depth}(v) - d)\rfloor</math> และการกระโดดแต่ละครั้งจะเหลือระยะห่างน้อยลงไป 2 เท่า จึงทำให้ใช้เวลา O(log "n") ในการกระโดด
ขั้นตอนวิธีบันได.
ขั้นตอนวิธีบันได (Ladder algorithm) ใช้แนวคิดที่ว่าปัญหาระดับบรรพบุรุษสามารถแก้ได้อย่างง่ายดายหากกราฟต้นไม้ที่จะประมวลผลเป็นกราฟวิถี เนื่องจากสามารถเปลี่ยนวิถีดังกล่าวไปเป็นแถวลำดับได้ และในการตอบคำถามก็เป็นเพียงการเรียกข้อมูลจากแถวลำดับโดยตรง อย่างไรก็ตามแนวคิดนี้ใช้ไม่ได้กับกราฟต้นไม้ทั่วไปที่มีกิ่งแตกออกมามากมาย จึงใช้วิธีแบ่งต้นไม้ออกเป็นหลาย ๆ วิถี และเก็บข้อมูลของวิถีต่าง ๆ ไว้ในแถวลำดับ และดำเนินการด้วยแนวคิดดังที่กล่าวมา สังเกตว่าด้วยวิธีนี้แล้วการกระโดดเพื่อหาคำตอบปัญหาระดับบรรพบุรุษแต่ละครั้งสามารถกระโดดข้ามไปเป็นวิถีได้เลย
การแยกส่วนของวิถียาวสุด.
การแยกส่วนของวิถียาวสุด (Longest path decomposition) เป็นการหาวิถียาวสุดจากรากของต้นไม้ไปถึงใบทั้งหลาย หลังจากหาได้แล้วก็จะนำจุดยอดในวิถียาวสุดไปเรียงเก็บไว้ในแถวลำดับ 'LP' จากรูป 1. ก็จะได้ว่าวิถียาวสุดคือวิถีจาก "r" → "v" ดังนั้น LP ของ "r" ก็จะมีข้อมูล LP["r"][0] = "r", LP["r"][1] = "a", ..., LP["r"][5] = "v" หลังจากเก็บข้อมูลวิถีเสร็จแล้วก็จะทำการลบวิถีนี้ออกจากต้นไม้ ทำให้ต้นไม้ถูกแยกออกเป็นหลายส่วน ก็ให้เริ่มต้นขั้นตอนดังกล่าวอีกรอบโดยพิจารณาต้นไม้ย่อยทั้งหลายที่เหลือเป็นต้นไม้ใหม่ เมื่อดำเนินการไปเรื่อย ๆ ก็จะไม่เหลือจุดยอดในต้นไม้อีก และแต่ละจุดยอดก็จะเก็บอยู่ในแถวลำดับเพียงแค่ครั้งเดียวเท่านั้น
ในการดำเนินการดังกล่าว สามารถกระทำได้โดยทำการค้นหาในแนวลึก ซึ่งใช้เวลาในการดำเนินการ O("n") ส่วนในการหาคำตอบปัญหาระดับบรรพบุรุษ LA("v", "d") ก็ให้เริ่มจากจุดยอด "v" และหาว่า "v" อยู่ใน LP ชุดไหน จากนั้นก็กระโดดไปยังต้นของ LP และกระโดดขึ้นหนึ่งขั้น และดำเนินการแบบนี้ซ้ำไปเรื่อย ๆ จนกว่าจะกระโดดไปเจอต้นของ LP ที่มีความลึกน้อยกว่า "d" ซึ่งแสดงให้เห็นว่า LP ชุดนั้นมีจุดยอดคำตอบอยู่ ก็สามารถคำนวณหาตำแหน่งของจุดยอดนั้นและตอบได้ภายในเวลา O("1") เลย
อย่างไรก็ตาม ในกรณีเลวร้ายมากสุด (รูป 2.) จะต้องใช้เวลาในการกระโดดระหว่างวิถีต่าง ๆ มากถึง Θ("√n") ซึ่งค่านี้สามารถลดได้จากการใช้การแยกส่วนของบันไดซึ่งเป็นหัวข้อถัดไป
การแยกส่วนของบันได.
การแยกส่วนของบันได (Ladder decomposition) ใช้แถวลำดับ 'Ladder' มีลักษณะขั้นตอนวิธีแทบจะเหมือนกับการแยกส่วนของวิถียาวสุดทุกประการ แต่แตกต่างตรงที่แถวลำดับ Ladder นอกจากจะเก็บข้อมูลของลูกหลานของรากต้นไม้ย่อยแล้ว ยังเก็บข้อมูลบรรพบุรุษเป็นจำนวนข้อมูลเท่ากับจำนวนลูกหลานที่เก็บไว้ด้วย กล่าวคือหาก LP มีขนาด size(LP) แล้ว จะได้ว่า size(Ladder) เท่ากับ 2 × size(LP) ยกเว้นในกรณีที่บรรพบุรุษขึ้นไปถึงรากของต้นไม้ ซึ่งในกรณีนั้นจะมีสมาชิกน้อยกว่า 2 × size(LP)
จากการเก็บข้อมูลแบบนี้ สังเกตว่าหากเริ่มต้นที่จุดยอด "v" ซึ่ง Ladder ของ "v" มีขนาดดั้งเดิม "h" เมื่อผ่านการเพิ่มจุดยอดบรรพบุรุษแล้วก็จะมีขนาด 2"h" แทน กรณีเลวร้ายมากสุดในการกระโดดก็คือขณะนี้กำลังอยู่ที่รากของต้นไม้ย่อย ซึ่งจะทำให้กระโดดได้เพียง "h" ขั้น ในรอบที่สอง แน่นอนว่า Ladder ของจุดยอดที่กำลังอยู่ต้องมีขนาดดั้งเดิมมากกว่าหรือเท่ากับ 2"h" แน่นอน เมื่อเพิ่มจุดยอดบรรพบุรุษเข้าไปแล้วก็จะทำให้มีขนาดเป็น 4"h" เช่นเดียวกันกับรอบที่แล้ว กรณีเลวร้ายมากที่สุดก็คือขึ้นไปได้เพียง 2"h" และในรอบต่อ ๆ ไปอย่างเลวร้ายที่สุดก็จะขึ้นได้ 4"h" 8"h" 16"h" ไปเรื่อย ๆ และจากที่ "h" มีค่าน้อยสุดคือ 1 จึงทำให้สรุปได้ว่าการกระโดดโดยรวมจะใช้เวลาเพียง O(log "n")
ขั้นตอนวิธีบันได.
ขั้นตอนวิธีนี้รวม 'ขั้นตอนวิธีตัวชี้กระโดด' และ 'การแยกส่วนของบันได' เข้าด้วยกัน โดยสังเกตว่าจากการกระโดดหนึ่งครั้งของ 'ขั้นตอนวิธีตัวชี้กระโดด' ไปที่จุดยอด "z" ไป 2"p" ขั้น จะเหลือการกระโดดอีกไม่ถึง 2"p" ขั้นเช่นกันเพื่อที่จะไปถึงจุดยอดเป้าหมาย และจากการที่เพิ่งกระโดดขึ้นมา 2"p" ขั้น Ladder ของ "z" ก็จะมีขนาดมากกว่าหรือเท่ากับ 2"p" ทำให้ Ladder ของ "z" นี้เก็บข้อมูลของจุดยอดปลายทางกับจุดยอด "z" ไว้ในแถวลำดับเดียวกันอย่างแน่นอน ดังนั้นจึงสามารถตอบคำถามนี้ได้ในเวลา O("1")