หนึ่งในปัญหาแรกๆที่ผมได้เรียนจากวิชาอัลกอริทึมสมัยปริญญาตรีคือปัญหาการโยนไข่จากตึก (เวอร์ชั่นที่ผมเรียนเป็นโยนแจกันจากบันได ในหนังสือ Algorithm Design ของ Jon Kleinberg and Éva Tardos)

โดย Ted-ed เคยเอาไปทำเป็น video riddle ด้วย

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

ถ้าไข่ไม่แตกเราสามารถเอาไข่ใบเดิมไปโยนใหม่ได้ หากโจทย์ตั้งเงื่อนไขเพิ่มเติมว่าเราอยากขึ้นลิฟต์ด้วยจำนวนครั้งให้น้อยที่สุด เราควรวางกลยุทธ์การโยนไข่อย่างไร

ปัญหานี้หากคิดในกรณีทั่วไปอาจจะยากสักหน่อย งั้นเราลองเริ่มคิดในกรณีที่เจาะจงขึ้นกันดีกว่า

กรณีที่ K = 1

ถ้าหากมีไข่แค่ใบเดียว เราคงคิดได้ไม่ยากนักว่าเราไม่มีวิธีอื่นนอกจากการทดลองโยนไข่ตั้งแต่ชั้นหนึ่ง แล้วถ้าหากไข่ไม่แตกก็นำไข่ใบเดิมขึ้นไปทดลองโยนบนชั้นสอง ชั้นสาม ชั้นสี่ … ไปเรื่อยๆ

จนเมื่อไข่แตกที่ชั้นที่ i เราก็ได้คำตอบว่า ไข่ทนแรงกระแทกได้ที่ i-1 ชั้น

ด้วยกลยุทธ์นี้เรารับประกันว่าเราจะได้คำตอบที่ถูกต้องแน่นอน แต่ถ้าหากไข่นั้นแข็งแรงมาก เราอาจจะต้องโยนไข่จากทุกชั้น นั่นคือเรามีโอกาสที่จะต้องขึ้นตึกไปโยนไข่ทั้งหมดถึง N ครั้ง

แปลว่า Big-O ของจำนวนครั้งในการเดินขึ้นตึกคือ $ O(N) $

ทำให้ดีกว่านี้ได้ไหม?

ในกรณีไข่ใบเดียว ถ้าเราพยายามขึ้นตึกให้น้อยครั้งลง เช่น ข้ามชั้นบางชั้นไปโดยไม่ทดลองโยน เราจะไม่สามารถรับประกันได้ว่าจะได้คำตอบที่ถูกต้องทุกครั้ง

เช่นถ้าหากเราโยนจากชั้นหนึ่งแล้วไข่ไม่แตก แล้วครั้งต่อไปเราลองโยนที่ชั้นสาม ถ้าไม่แตกก็โชคดีไป แต่ถ้าไข่แตกขึ้นมา เราจะไม่สามารถหาคำตอบได้เลยว่าไข่ทนแรงกระแทกจากชั้นสองได้โดยไม่แตกหรือเปล่า

กรณีที่ K = 2

ถ้าเรามีไข่เพิ่มขึ้นอีกใบ เราจะทำให้ดีขึ้นได้มากแค่ไหน? แน่นอนว่าด้วยไข่ใบแรกเราสามารถข้ามการทดลองโยนไข่จากชั้นบางชั้นได้

ถ้าหากเราโยนชั้นเว้นชั้น นั่นคือโยนไข่จากชั้น 2,4,6,... จนกระทั่งไข่แตกที่ชั้นที่ i เราจึงนำไข่ใบที่สองมาทดลองโยนที่ชั้นที่ i-1 เพื่อดูว่าไข่ทนแรงกระแทกที่ชั้น i-1 ได้หรือเปล่า

ด้วยกลยุทธ์นี้เราจะต้องขึ้นตึกเป็นจำนวนครั้งเพียงแค่ไม่เกิน $ \frac{N}{2} + 1 $ ครั้งเท่านั้น ซึ่งก็ดูเป็นวิธีที่ดี แต่ถ้าหากเราวิเคราะห์ Big-O จะพบว่าจำนวนครั้งในการเดินขึ้นตึกก็ยังคงเป็น $ O(N) $ อยู่ดี

หากเราลองพยายามทำให้ดีขึ้น เช่นข้ามการโยนทีละสองชั้น นั่นคือโยนไข่ใบแรกที่ชั้น 3,6,9,... จนกระทั่งไข่แตกที่ชั้นที่ i เราจึงนำไข่ใบที่สองมาทดลองโยนที่ชั้นที่ i-2 และ i-1 เพื่อดูว่าไข่ทนแรงกระแทกที่ชั้น i-2 หรือ i-1 ได้หรือเปล่า

จะเห็นว่าจำนวนครั้งมากที่สุดเหลือเพียง $ \frac{N}{3} + 2 $ ซึ่งแม้ว่า Big-O จะไม่ดีขึ้นแต่จำนวนครั้งก็ลดลงอย่างเห็นได้ชัด เนื่องจากด้วยการที่เพิ่มจำนวนครั้งการโยนไข่ใบที่สองเพียงหนึ่งครั้ง เราสามารถลดจำนวนครั้งการโยนไข่ใบแรกจาก $ \frac{N}{2} $ เหลือเพียง $ \frac{N}{3} $

เมื่อคิดได้แบบนี้ เราก็สามารถทำการลดจำนวนครั้งที่ต้องโยนไข่ใบแรกลงให้เหลือเพียงแค่จำนวนคงที่ได้ นั่นคือแทนที่จะข้ามชั้นเป็นค่าคงที่ เราก็ข้ามชั้นด้วยจำนวนที่ขึ้นกับค่า N เช่น หากเราเลือกข้ามทีละ $ \frac{N}{2} $ ชั้น แปลว่าเราจะโยนไข่ใบแรกแค่ 2 ครั้งเท่านั้น

แต่ปรากฎว่า เมื่อไข่ใบแรกแตกไป เราจะเหลือไข่เพียงแค่หนึ่งใบกับจำนวนช่วงของชั้นที่ต้องโยนทดสอบอีก $ \frac{N}{2} $ ชั้น และเราก็ไม่มีวิธีโยนที่ดีไปกว่าการไล่โยนทีละชั้น ทำให้จำนวนครั้งที่ต้องโยนอาจจะมากถึง

\[\begin{align} \frac{N}{\frac{N}{2}} + \frac{N}{2} = 2 + \frac{N}{2} \end{align}\]

จะเห็นได้ว่าเมื่อเราพยายามลดจำนวนครั้งของการโยนไข่ใบใดใบหนึ่ง จำนวนครั้งของอีกใบก็จะเพิ่มขึ้นเสมอ และการคำนวณ Big-O ก็ขึ้นกับจำนวนครั้งการโยนของไข่ใบที่ต้องโยนมากกว่า

นั่นคือด้วยไข่ใบแรกหากเราจะข้ามการโยนเป็นจำนวน s ชั้น นั่นคือโยนไข่ที่ชั้น s,2s,3s,... เป็นจำนวนไม่เกิน $ \frac{N}{s} $ ครั้ง เมื่อไข่ใบแรกแตก เราจะต้องโยนไข่ใบที่สองอีกเป็นจำนวน s ครั้ง

ดังนั้นเราจึงควรจะทำให้จำนวนครั้งการโยนของไข่ทั้งสองใบนั้นเท่ากัน เพื่อให้ได้ Big-O ดีที่สุด นั่นคือ

\[\begin{align} s &= \frac{N}{s} \\ s^2 &= N \\ s &= \sqrt{N} \end{align}\]

นั่นคือหากตึกมีจำนวน N ชั้นเราจะข้ามจำนวนชั้นเท่ากับรากที่สองของ N เช่นหากตึกมีจำนวน 100 ชั้น ด้วยไข่ใบแรกเราจะโยนไข่ที่ชั้น 10,20,30,... ซึ่งจะโยนไม่เกิน 10 ครั้งและด้วยไข่ใบที่สอง เราก็จะเหลือจำนวนชั้นให้ไล่โยนไม่เกิน 10 ครั้งเช่นกัน

และเมื่อเราวิเคราะห์ Big-O ก็จะได้ว่าจำนวนครั้งการโยนไม่เกิน

\[\begin{align} \frac{N}{s} + s &= \frac{N}{\sqrt{N}} + \sqrt{N} \\ &= \sqrt{N} + \sqrt{N} \\ &= 2\sqrt{N} \\ &= O(\sqrt{N}) \\ \end{align}\]

ทำให้ดีกว่านี้ได้ไหม?

ทั้งหมดที่เรากล่าวมา เราตั้งเงื่อนไขโดยไม่รู้ตัวว่าจำนวนชั้นที่เราข้ามการโยนด้วยไข่ใบแรกนั้นเท่ากันทุกครั้ง แต่ถ้าหากเรากระโดดข้ามด้วยจำนวนชั้นที่ไม่เท่ากัน เราจะทำให้ Big-O ดีขึ้นได้ไหม?

การจะตอบคำถามนี้เราจะใช้ข้อเท็จจริงที่เรารู้แล้วว่า

• ถ้าหากเหลือไข่เพียงใบเดียว เราไม่มีวิธีอื่นที่ดีไปกว่าการไล่โยนทุกชั้น
• Big-O จะขึ้นกับจำนวนครั้งการโยนของไข่ใบที่โยนมากครั้งกว่า

จากความจริงทั้งสองข้อ แปลว่าถ้าหากเราต้องการทำให้ดีกว่า $ O(\sqrt{N}) $ จำนวนชั้นของช่วงที่เหลือจากการแบ่ง(ข้ามการโยน)ด้วยไข่ใบแรกนั้น ต้องไม่เกิน $ O(\sqrt{N}) $

ซึ่งการที่เราจะแบ่ง N ออกเป็นช่วงๆ โดยที่แต่ละช่าวงนั้นไม่เกิน $ O(\sqrt{N}) $ แปลว่าเราจะได้จำนวนช่วง “อย่างน้อย” $ O(\sqrt{N}) $ ช่วง

และการจะแบ่งเพื่อเพิ่มจำนวนช่วงนั้น เราจำเป็นต้องโยนไข่อย่างน้อยหนึ่งครั้ง ต่อการเพิ่มช่วงหนึ่งช่วง

หมายความว่าหากจะให้โยนไข่ใบที่สองไม่เกิน $ O(\sqrt{N}) $ ครั้ง เราจะต้องโยนไข่ใบแรกอย่างน้อย $ O(\sqrt{N}) $ ครั้ง

ด้วยเหตุผลคล้ายๆกันหากจะให้โยนไข่ใบแรกไม่เกิน $ O(\sqrt{N}) $ ครั้ง เราจะต้องโยนไข่ใบที่สองอย่างน้อย $ O(\sqrt{N}) $ ครั้งเช่นกัน

หมายความว่าสำหรับไข่สองใบนั้น $ O(\sqrt{N}) $ เป็น Big-O ที่ดีที่สุดแล้ว

สำหรับตอนหน้าเราจะตอบคำถามต่อไปนี้

• กรณีไข่ K ใบใดๆจะมีกลยุทธ์การโยนอย่างไร และ Big-O เป็นอย่างไร
• การเพิ่มจำนวนไข่นั้นจะทำให้ Big-O ลดลงเสมอไปหรือไม่
• หากเรามีไข่ไม่จำกัด จะมีกลยุทธ์การโยนอย่างไร

To be continued… อ่านต่อ