แนะนำและทำความรู้จักกับคำว่าอัลกอริทึมเชิงสุ่มว่าเป็นอย่างไร

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

อัลกอริทึมเชิงสุ่ม ต่างกับอัลกอริทึมทั่วไปคือการมีการนำ Random number generator เข้ามาร่วมใช้งานในอลกอริทึมด้วย ณ จุดใดจุดหนึ่งในการทำงาน ซึ่งอัลกอริทึมเชิงสุ่มก็ยังสามารถแบ่งได้เป็นสองประเภท นั่นคือ Monte Carlo และ Las Vegas

Monte Carlo

Monte Carlo เป็นอัลกอริทึมเชิงสุ่มที่มีคุณสมบัติดังต่อไปนี้

– ให้คำตอบเสมอ แต่คำตอบนั้นอาจจะผิด (โอกาสต่ำ)

– ทำงานเร็ว

ยกตัวอย่างอัลกอริทึมประเภทนี้ เช่น การหาจำนวนหมู่มากในกลุ่มข้อมูล ถ้าหากเราใช้วิธีปกติ ก็อาจจะต้องใช้เวลาถึง O(n²) แต่หากเราใช้อัลกอริทึมเชิงสุ่ม ซึ่งมีขั้นตอนดังต่อไปนี้

– สุ่มเลขสักตัวหนึ่งจากในกลุ่มข้อมูลที่มีอยู่ จากนั้นใช้เลขตัวนั้นเทียบกับเลขทั้งหมดในชุด

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

– ถ้าหากว่าเลขตัวนั้นไม่ใช่จำนวนหมู่มาก จะต้องทำซ้ำขั้นตอน 1 ใหม่อีกรอบ และทำซ้ำจนกว่าจะเจอจำนวนหมู่มากหรือจนกว่าแน่ใจ หากทำซ้ำถึงจุดที่แน่ใจแล้วว่าไม่มีจำนวนหมู่มากจริง ๆ ก็ตอบว่าไม่มีจำนวนหมู่มาก

– แล้วเราต้องวนกี่รอบในกรณีที่คำตอบคือไม่มีเลขหมู่มากถึงจะพอใจล่ะ? คำนวณง่าย ๆ คือถ้าจำนวนชุดนั้นมีจำนวนหมู่มากจริง ๆ โอกาสสุ่มเจอจำนวนนั้นคือ ½ อย่างที่ได้กล่าวไป ดังนั้นหากเราวนซ้ำสัก 40 รอบ จะได้ว่าโอกาสที่เราจะโชคร้ายสุ่มไม่เจอจำนวนหมู่มากนั้นมีแค่ 1/(2⁴⁰) เท่านั้น ซึ่งโอกาสตอบผิดน้อยกว่าโอกาสการทำงานผิดพลาดของฮาร์ดแวร์บนคอมพิวเตอร์เสียอีก

ทีนี้ก็มาดูกันดีกว่าว่า การที่เราแลกกับโอกาสที่จะตอบผิดเพียงแค่ 1/(2^k) จะได้ความเร็วมาเท่าไร คำตอบก็คือ O(kn) สมมติว่าเราตั้งการวนซ้ำไว้ที่ 40 รอบ ก็เท่ากับว่า Worst case ของเราคือ O(40n) ถ้าปัดเลขสวย ๆ ตามหลักการคำนวณ time complexity ที่ไม่นับค่าคงตัวแล้ว ก็จะเหลือเพียงแค่ O(n) เท่านั้น!

Las Vegas

ส่วนอัลกอริทึมเชิงสุ่มอีกแบบหนึ่งคือ Las Vegas ซึ่งมีคุณสมบัติดังต่อไปนี้

– คืนคำตอบที่ถูกต้องเสมอ แต่บางครั้งอาจจะไม่คืนคำตอบหรือยอมรับว่าหาคำตอบไม่ได้

– อาจทำงานช้า (โอกาสที่ต่ำ)

ตัวอย่างของอัลกอริทึมประเภทนี้คือ Randomized Quicksort ซึ่งเป็นการเรียงลำดับตัวเลขในชุดด้วยการใช้ pivot (ดูตัวอย่างวิธีการ Quicksort ได้ที่นี่ https://www.youtube.com/watch?v=PgBzjlCcFvc ) วิธีการ Quicksort ทั่วไปมีความเร็วการประมวลผลเฉลี่ยคือ O(n log n) แต่มี worst case คือถ้าเลือก pivot ที่ค่าสูงที่สุดหรือต่ำที่สุดตลอด ซึ่งเกิดขึ้นได้ในกรณีที่ข้อมูลถูก sort มาอยู่แล้วหรือถูก sort แบบกลับด้าน ทำให้การ sort แต่ละรอบนั้นสามารถเรียงตัวเลขได้เพียงทีละตัว ส่งผลให้มี time complexity เป็น O(n²) นั่นเอง

ทีนี้เรามาคิดกัน ว่าถ้าเราเลือก pivot แบบสุ่ม จะทำให้โอกาสที่จะสุ่มได้เลขที่มากสุดหรือน้อยสุดตลอดก็ยังคงมี แต่ถ้ามี input จำนวน k ตัว โอกาสที่จะสุ่มได้เลขมากสุดหรือน้อยสุดในแต่ละรอบก็มีแค่ 2/k และโอกาสที่จะโชคร้ายทุก ๆ รอบก็มีแค่ (2/k)^k เท่านั้นเอง

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

ผู้เขียน เธียรวิชญ์ สิริสาครสกุล

18 สิงหาคม 2564

อ้างอิง

https://www.youtube.com/watch?v=ydijUBj6Dlk&list=PL0ROnaCzUGB65_YkASLAEmcW_mtxFtq4m&index=92

https://www.geeksforgeeks.org/quick-sort/