ในบทความนี้ ผมจะวิเคราะห์โดยละเอียดว่าปัญหาเส้นผ่านศูนย์กลางของต้นไม้สามารถแก้ไขได้อย่างไรด้วยการสำรวจตามความกว้างก่อน (BFS) สองครั้ง เหตุผลหนึ่งว่าทำไมโซลูชันนี้จึงน่าสนใจก็คือ แม้ว่าจะใช้งานง่าย แต่ก็ยังไม่สบายใจที่จะอธิบายว่าทำไมมันถึงใช้งานได้จริง! อีกเหตุผลหนึ่งก็คือ การเข้าใจสิ่งนี้ทำให้เราเข้าใจ "การพิสูจน์โดยความขัดแย้ง" มากขึ้น
ขั้นแรก ก่อนที่จะดำเนินการแก้ไขปัญหา ฉันขอทบทวนอย่างรวดเร็วว่าปัญหาเส้นผ่านศูนย์กลางของต้นไม้คืออะไร และแนวคิดที่จำเป็นที่ต้องได้รับการแก้ไข
กราฟคือชุดของจุดยอด (หรือที่เรียกว่าโหนด) และขอบที่เชื่อมโยงจุดยอด
ต้นไม้เป็นกราฟประเภทหนึ่งโดยเฉพาะ ลักษณะหลักของประเภทนี้คือไม่มีรอบ (ซึ่งหมายความว่าเป็นไปไม่ได้ที่จะเยี่ยมชมโหนดมากกว่าหนึ่งครั้งในเส้นทางเดียว นอกจากนี้ยังหมายความว่ามีเส้นทางมากที่สุดหนึ่งเส้นทางระหว่างสองโหนดใดๆ)
เส้นผ่านศูนย์กลางของต้นไม้คือการค้นหาเส้นทางที่ยาวที่สุดในต้นไม้ มีวิธีแก้ไขปัญหาเวลาเชิงเส้นยอดนิยมสองวิธีสำหรับปัญหานี้ อันแรกจะขึ้นอยู่กับการเขียนโปรแกรมแบบไดนามิก ("รายละเอียดเพิ่มเติม") และอันที่สองขึ้นอยู่กับอัลกอริธึม "การค้นหาแบบกว้างก่อน" (BFS) BFS คืออัลกอริธึมการเคลื่อนที่ของกราฟที่ทำงานโดยการเคลื่อนที่ของกราฟในลักษณะระดับต่อระดับ สังเกตลำดับที่ทุกโหนดถูกเยี่ยมชมที่นี่:
อัลกอริธึม BFS เส้นผ่านศูนย์กลางต้นไม้
อัลกอริทึมนี้ใช้ BFS ดังต่อไปนี้:
- เลือกโหนดสุ่มใดก็ได้ (เรียกว่า X)
- สร้างการแวะผ่าน BFS จากโหนดนี้
- เลือกโหนดที่ไกลที่สุดจาก X (ขอเรียกโหนดนี้ว่า A)
- เรียกใช้ BFS อีกครั้ง แต่จากโหนด A
- เลือกโหนดที่ไกลที่สุดจาก A (ขอเรียกโหนดนี้ว่า B)
- ส่งกลับ A และ B เป็นจุดสิ้นสุดของเส้นผ่านศูนย์กลางของต้นไม้
ฉันพนันได้เลยว่าคุณรู้สึกว่าอัลกอริทึมฟังดูเข้าใจง่าย แต่น่าเสียดายที่มันไม่ชัดเจนว่าทำไมมันถึงใช้งานได้ ก่อนที่จะอธิบายเหตุผล เรามาระบุสิ่งที่เราจะใช้เป็นพื้นฐานความเข้าใจของเราก่อน
- เมื่อพิจารณาว่า A และ B เป็นจุดสิ้นสุดของเส้นผ่านศูนย์กลาง เราก็รู้ด้วยว่ามีเพียงเส้นทางเดียวระหว่าง A และ B ซึ่งเป็นเพราะคุณลักษณะของกราฟต้นไม้ที่เราพูดถึงก่อนหน้านี้
- เพื่อให้เข้าใจง่าย เราจะถือว่ากราฟมีเส้นผ่านศูนย์กลางของต้นไม้เพียงเส้นผ่านศูนย์กลางเดียว ซึ่งช่วยให้เรามุ่งความสนใจไปที่ปัญหาหลัก แทนที่จะมุ่งความสนใจไปที่กรณีมุม (การขยายให้รวมเส้นผ่านศูนย์กลางที่มีขนาดเดียวกันหลายรายการไม่ได้ แต่ท้าทาย)
- หากเรามีจุดสิ้นสุดจุดหนึ่ง (A หรือ B) ก็ควรจะไปถึงจุดสิ้นสุดอีกจุดหนึ่งได้ง่ายพอสมควร เราเพียงแค่ต้องค้นหาเส้นทางที่ยาวที่สุดจากจุดสิ้นสุดนี้ (เรียกใช้ BFS) ซึ่งควรจะส่งเราไปยังจุดสิ้นสุดอื่น ทำไมเรื่องนี้ถึงเป็นความจริง? เพราะไม่เช่นนั้นเราจะมีเส้นทางที่ยาวกว่า (เช่น ยาวกว่า A ถึง B หรือเส้นผ่านศูนย์กลางของต้นไม้) ซึ่งขัดแย้งกัน
จากจุดสุดท้าย เราสามารถลดปัญหาของเราลงเป็น:
ค้นหาจุดสิ้นสุดใดๆ ของเส้นผ่านศูนย์กลาง
เพื่อแก้ปัญหาที่ลดลงนี้ เราต้องพิสูจน์ว่าการใช้ BFS จากโหนดใดๆ ก็เพียงพอแล้วในการค้นหาจุดสิ้นสุดที่มีเส้นผ่านศูนย์กลางใดๆ เพื่อตรวจสอบแนวทางนี้ เราต้องพิจารณาสองสถานการณ์:
สถานการณ์ที่ 1: โหนดเริ่มต้น X อยู่ภายในเส้นทางเส้นผ่านศูนย์กลาง (ระหว่าง A และ B)
ในสถานการณ์นี้ ถ้าเรารัน BFS จากโหนด X นี้ คุณคิดว่าโหนดที่ไกลที่สุดจะเป็นเท่าใด
โหนดที่ไกลที่สุดจะต้องเป็นหนึ่งในจุดสิ้นสุดที่มีเส้นผ่านศูนย์กลาง เนื่องจากเราสามารถดูสถานการณ์นี้ราวกับว่าเราแบ่งเส้นผ่านศูนย์กลางของต้นไม้ออกเป็นสองเส้นทาง A ถึง X และ X ถึง B (ดังแสดงในตัวอย่างด้านล่าง)
และถ้าโหนดที่ไกลที่สุดไม่ใช่จุดสิ้นสุดที่มีเส้นผ่านศูนย์กลาง (เช่น A*)
จากนั้นเราก็สามารถขยายเส้นทาง " X ไปยัง A " ไปยัง " X ไปยัง A* " ได้ ซึ่งหมายความว่าเราสามารถหาเส้นผ่านศูนย์กลางที่ยาวกว่า " B ถึง A* " ได้ (ซึ่งขัดแย้งกัน)
สถานการณ์ที่ 2: โหนดเริ่มต้น X อยู่นอกเส้นทางเส้นผ่านศูนย์กลาง (ระหว่าง A และ B)
สถานการณ์นี้มี 2 กรณีที่น่าสนใจ:
กรณีที่ 1: เส้นทางที่ยาวที่สุดจาก X สัมผัสกับเส้นผ่านศูนย์กลางของต้นไม้
ทันทีที่เส้นทางที่ยาวที่สุดแตะเส้นผ่านศูนย์กลางของต้นไม้ (ที่โหนด T) เราสามารถทำซ้ำสถานการณ์ที่ 1 ได้โดยสมมติว่าจุดเริ่มต้นของเราคือ T หลังจากนั้น โหนดที่ยาวที่สุดจาก X ควรเป็นไปตามสมการนี้:
จากการสนทนาของเราในสถานการณ์สมมติที่ 1 โหนดที่ไกลที่สุดจาก T จะเป็นจุดสิ้นสุดของเส้นผ่านศูนย์กลาง
กรณีที่ 2: เส้นทางที่ยาวที่สุดจาก X ไม่ได้สัมผัสกับเส้นผ่านศูนย์กลางของต้นไม้
ซึ่งหมายความว่าเรามีเส้นทางยาวสองเส้นทางที่ไม่ตัดกันบนต้นไม้ เส้นทางหนึ่งคือเส้นผ่านศูนย์กลางของต้นไม้ “A ถึง B” และอีกเส้นทางหนึ่งคือ “X ถึง Y”
ที่นี่เราแนะนำโหนดใหม่สองโหนด i และ j ซึ่งเป็นโหนดที่จะเชื่อมต่อทั้งสองเส้นทางในที่สุด (จะต้องมีโหนดดังกล่าวเนื่องจากต้นไม้จะต้องเชื่อมต่อกัน)
ในกราฟนี้ สมมติว่าระยะทางจาก X ถึง j คือ ≤ ระยะห่างจาก j ถึง Y เราสามารถสรุปได้อย่างปลอดภัยเพราะไม่เช่นนั้นเราสามารถสลับการตั้งชื่อของ X และ Y เพื่อให้ทำงานได้ นอกจากนี้ เนื่องจากไม่สำคัญว่าจุดสิ้นสุดเส้นผ่านศูนย์กลางใดจะอยู่ห่างจากโหนด i มากที่สุด สมมติว่ามันจะเป็นโหนด A
จนถึงตอนนี้ เมื่อพิจารณาจากกราฟด้านบน เราก็สามารถสรุปได้ดังนี้
- โหนดที่ไกลที่สุดจากโหนด i ในขณะนี้คือ A (ขึ้นอยู่กับสถานการณ์ที่ 1)
- โหนดที่ไกลที่สุดจากโหนด j คือ Y มิฉะนั้น X จะไม่เลือก Y เป็นโหนดที่ไกลที่สุด
เนื่องจาก “j ถึง Y” › “j ถึง A” ดังนั้นโหนดฉันสามารถดำเนินการขั้นตอนเพิ่มเติมเพื่อไปถึง Y มากกว่า A เพราะมันสามารถย้ายไปยัง j และเรารู้อยู่แล้วว่าโหนดที่ไกลที่สุดจาก j คือ Y สิ่งนี้นำเราไปสู่ ขัดแย้งกันเพราะโหนดที่ไกลที่สุดจาก i ควรเป็น A ไม่ใช่ Y
ฉันหวังว่าภาพต่อไปนี้จะแสดงให้เห็นถึงความขัดแย้งนี้:
ฉันหวังว่าการวิเคราะห์นี้จะเพียงพอที่จะให้หลักฐานที่ไม่เป็นทางการที่ดีพอที่จะโน้มน้าวคุณว่าทำไมโซลูชัน two-BFS จึงใช้งานได้ โปรดแจ้งให้เราทราบในความคิดเห็นความคิดของคุณและหากมีส่วนใดที่ไม่ชัดเจน
