ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"

'''ขั้นตอนวิธีแบบสุ่ม''' (randomized algorithm) เป็น[[ขั้นตอนวิธี]]ที่ยอมให้มีการโยนเหรียญได้ ในทางปฏิบัติ เครื่องที่ใช้ทำงานขั้นตอนวิธีนี้ จะต้องใช้[[ตัวสร้างเลขสุ่มเทียม]] (pseudo-random number generator) ในการสร้าง[[ตัวเลขสุ่ม]]ขึ้นมา อัลกอรึทึมโดยทั่วๆไปมักใช้[[บิทสุ่ม]] (random bit) สำหรับเป็นอินพุตเสริม เพื่อชี้นำการกระทำของมันต่อไป โดยมีความหวังว่าจะช่วยให้มีประสิทธิภาพที่ดีใน "กรณีส่วนมาก(average case)" หรือหากพูดในทาง[[คณิตศาสตร์]]ก็คือ ประสิทธิภาพของขั้นตอนวิธีมีค่าเท่ากับ[[ตัวแปรสุ่ม]] (random variable) ซึ่งคำนวณจากบิทสุ่ม โดยหวังว่าจะมี[[ค่าคาดหวัง]] (expected value) ที่ดี กรณีที่แย่มากที่สุดมักจะมีโอกาสเกิดขึ้นน้อยมากจนแทบจะไม่ต้องสนใจ

 

หากลองพิจารณาการหาตัวอักษร a ใน[[อาร์เรย์]]ขนาด ''n'' เมื่อสมมุติว่าครึ่งหนึ่งในอาร์เรย์นี้เป็น a และอีกครึ่งหนึ่งเป็น b วิธีที่เห็นชัดวิธีหนึ่งคือการดูแต่ละตัวในอาร์เรย์ แต่วิธีนี้อาจทำให้ต้องดูถึง n/2 ตัวในกรณีที่แย่ที่สุด (นั่นคือครึ่งแรกของอาร์เรย์เป็น b ทั้งหมด) การพยายามแก้ไขเหตุการณ์นี้โดยเปลี่ยนลำดับการดู เช่น อ่านจากหลังมาหน้า หรืออ่านตัวเว้นตัว ก็ไม่ได้ช่วยให้อะไรดีขึ้นเลย ที่จริงแล้ว วิธีการใดก็ตามที่ลำดับของการตรวจสอบสมาชิกแต่ละตัวถูกกำหนดไว้ตายตัวแล้ว (นั่นคือ เป็นขั้นตอนวิธี''ดิเทอร์มินิสติก'') เราจะไม่สามารถรับประกันได้เลยว่าขั้นตอนวิธีจะทำงานสำเร็จอย่างรวดเร็ว ใน''ทุกๆอินพุทที่เป็นไปได้'' แต่ถ้าหากเราตรวจสอบสมาชิกในอาร์เรย์แบบสุ่ม(ไม่มีลำดับที่แน่นอน) ''มีความน่าจะเป็นสูง''ที่เราจะสามารถหา a พบในเวลาอันรวดเร็ว ''ไม่ว่าอินพุทจะเป็นเช่นไรก็ตาม''

 

ในตัวอย่างที่กล่าวมานี้ ขั้นตอนวิธีแบบสุ่มให้ผลลัพธ์ที่ถูกต้องเสมอ เพียงแต่ว่ามีความเป็นไปได้อยู่บ้าง ที่ขั้นตอนวิธีจะใช้เวลานานในการทำงาน บางครั้งเราอาจต้องการขั้นตอนวิธีที่ทำงานได้เร็วในทุกๆสถานการณ์ แต่เราก็ต้องแลกด้วย''โอกาสเกิดความผิดพลาด'' ขั้นตอนวิธีประเภทแรก(ถูกต้องเสมอ แต่อาจใช้เวลานาน)เรียกว่า[[ขั้นตอนวิธีลาสเวกัส]] และแบบหลัง(ต้องทำงานเร็ว แต่มีข้อผิดพลาดได้)เรียกว่า[[ขั้นตอนวิธีมอนติคาร์โล]] (ตามชื่อของ[[วิธีมอนติคาร์โล]]ที่ใช้ในการจำลอง (simulation)) สังเกตว่าขั้นตอนวิธีลาสเวกัสทุกอันสามารถแปลงเป็นขั้นตอนวิธีมอนติคาร์โลได้ โดยการตอบออกไปมั่วๆ หากไม่สามารถหาคำตอบได้ในเวลาที่กำหนด

 

[[ทฤษฎีความซับซ้อนในการคำนวณ]]ซึ่งเป็นการศึกษาเกี่ยวกับทรัพยากรทางการคำนวณที่ต้องใช้ในการแก้ปัญหาหนึ่งๆ ได้สร้างแบบจำลองของขั้นตอนวิธีแบบสุ่มให้เป็น''[[เครื่องจักรทัวริง]][[เครื่องจักรทัวริงเชิงความน่าจะเป็น|เชิงความน่าจะเป็น]]'' ทั้งขั้นตอนวิธีลาสเวกัสและมอนติคาร์โลได้ถูกนำมาพิจารณา รวมถึง "คลาสของความซับซ้อน" หลายๆคลาสก็ได้ถูกนำมาศึกษา คลาสของความซับซ้อนแบบสุ่มแบบที่เป็นพื้นฐานที่สุดคือแบบ[[อาร์พี]] ซึ่งเป็นคลาสของ[[ปัญหาการตัดสินใจ]]ที่มีขั้นตอนวิธีแบบสุ่ม (หรือเครื่องจักรทัวริงเชิงความน่าจะเป็น) ที่มีประสิทธิภาพ (ทำงานได้ได้ในเวลาโพลิโนเมียล) ที่สามารถตอบว่า "ไม่" ได้ถูกต้องเสมอ และสามารถตอบว่า "ใช่" ได้ โดยมีโอกาสถูกต้องอย่างน้อย 1/2 คลาสส่วนกลับ (complement) ได้แก่โค-อาร์พี และคลาสของปัญหาซึ่งทั้งคำตอบ "ใช่" และ "ไม่" สามารถมีค่าความน่าจะเป็นได้ทั้งคู่ (นั่นคือ ไม่ได้บังคับให้ต้องตอบถูกต้องเสมอ) เรียกว่า[[ซีพีพี]] (ZPP) สำหรับปัญหาซึ่ง (เชื่อกันว่า) อยู่นอกคลาสนี้ เช่นปัญหา[[เอ็นพีแบบยาก]] (ซึ่งแม้แต่ขั้นตอนวิธีแบบสุ่มก็ไม่สามารถแก้ได้) จำเป็นต้องแก้ด้วย[[ขั้นตอนวิธีแบบประมาณ]]

 

สมมุติว่าเราใช้วิธีเชิงสุ่ม แล้วมีความน่าจะเป็นที่จะเกิดความผิดพลาดเป็น 2⁻¹⁰⁰⁰ คำถามที่ตามมาคือ ตัวเลขนี้เกิดจาก[[การพิสูจน์ทางคณิตศาสตร์]]หรือไม่? ถึงแม้ว่าโอกาสผิดพลาดจะน้อยมากเมื่อเทียบกับโอกาสเกิดความผิดพลาดของฮาร์ดแวร์ที่ใช้ทำมัน หรือโอกาสที่คนตรวจบทพิสูจน์จะมองข้ามความผิดพลาดไป แต่จริงๆแล้วการบอกว่ามีความน่าจะเป็นน้อยนี้ ควรให้ความหมายว่าอย่างไรดี?

 

[[ควิกซอร์ต]] น่าจะเป็นขั้นตอนวิธีที่ใช้จริงที่เราคุ้นเคยที่สุดที่ใช้การสุ่มอย่างได้ผลดีมากๆ ขั้นตอนวิธีนี้ในแบบที่เป็นดิเทอร์มินิสติกต้องใช้เวลา ''[[สัญกรณ์ Big O|O]](n^2)'' ในการเรียงเลข ''n'' ตัว สำหรับอินพุทบางรูปแบบ เช่น อาร์เรย์ที่ถูกเรียงมาอยู่แล้ว อย่างไรก็ตาม ถ้าขั้นตอนวิธีสลับตัวในอาร์เรย์แบบสุ่มก่อนที่จะเริ่มทำงาน มันจะมีความน่าจะเป็นสูงที่จะทำงานเสร็จในเวลา ''O(n log n)'' สำหรับอินพุททุกรูปแบบ ความแตกต่างระหว่างสองแบบนี้จะมีความสำคัญมาก เมื่อเราต้องจัดเรียงข้อมูลจำนวนมากๆ

 

ตัวอย่างที่[[ซับซ้อน]]ขึ้นกว่าอีกหน่อย คือการใช้ขั้นตอนวิธีเชิงสุ่มแก้ปัญหาทางด้าน[[ทฤษฎีกราฟ]] นี่คือขั้นตอนวิธีสำหรับแก้ปัญหา [[การตัดให้น้อยที่สุด]](minimum cut)

 

# M. Mitzenmacher and E. Upfal. Probability and Computing : Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.

 

[[หมวดหมู่:ขั้นตอนวิธี]]