ขั้นตอนวิธีแบบสุ่ม

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

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

ลองจินตนาการว่าเราจะต้องเผชิญหน้ากับ ผู้ประสงค์ร้ายที่เก่งกาจ กล่าวคือคน ๆ นั้นสามารถล่วงรู้วิธีการในการจัดการกับปัญหาของขั้นตอนวิธีและสามารถหาอินพุทที่แย่ที่สุดมาทำให้ขั้นตอนวิธีทำงานได้ประสิทธิภาพไม่ดีได้เสมอ (ดูที่การวิเคราะห์เชิงแข่งขัน) อย่างไรก็ตามผู้ประสงค์ร้ายคนนี้จะสามารถทำร้ายขั้นตอนวิธีของเราได้น้อยลง หากขั้นตอนวิธีไม่ได้มีพฤติกรรมที่แน่นอน ทำให้ผู้ประสงค์ร้ายไม่สามารถเดาได้ถูก ด้วยเหตุผลเดียวกันนี้ที่ทำให้ การสุ่ม เป็นที่แพร่หลายในวิทยาการเข้ารหัสลับ ในงานประยุกต์ทางด้านการเข้ารหัสลับนั้น ตัวเลขสุ่มเทียมไม่สามารถนำมาใช้ได้ เนื่องจากผู้ประสงค์ร้ายสามารถทายเลขนี้ได้ ทำให้ขั้นตอนวิธีมีลักษณะเป็นแบบดิเทอร์มินิสติก ดังนั้นจึงจำเป็นต้องมีแหล่งกำเนิดที่สามารถสร้างเลขสุ่มจริงได้ หรือไม่ก็ต้องมีตัวสร้างตัวเลขสุ่มเทียมที่มีความปลอดภัยในการเข้ารหัสลับ อีกศาสตร์หนึ่งที่การสุ่มได้หยั่งรากฝังลึกเข้าไปคือคอมพิวเตอร์ควอนตัม (quantum computer)

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

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

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

การตรวจสอบการเป็นจำนวนเฉพาะมิลเลอร์-ราบินนั้น มีหลักการพื้นฐานอยู่บนความสัมพันธ์ทวิภาค ระหว่างจำนวนเต็มบวกสองตัว k และ n ใด ๆ ที่สามารถบอกได้ว่า *k* "เป็นตัวยืนยันการเป็นจำนวนประกอบของ" *n* สามารถแสดงได้ว่า
* ถ้ามีตัวยืนยันการเป็นจำนวนประกอบของ *n* แล้ว *n* เป็นจำนวนประกอบ (หมายความว่า *n* ไม่เป็นจำนวนเฉพาะ) และ
* ถ้า *n* เป็นจำนวนประกอบแล้ว มีอย่างน้อยสามในสี่ของจำนวนนับที่มีค่าน้อยกว่า *n* ที่เป็นตัวยืนยันการเป็นจำนวนประกอบของ *n* ได้ และ
* มีขั้นตอนวิธีที่ทำงานได้รวดเร็วพอ ที่เมื่อให้ค่า *k* และค่า *n* ขั้นตอนวิธีสามารถบอกได้ว่า *k* เป็นตัวยืนยันการเป็นจำนวนประกอบของ *n* หรือไม่
สังเกตว่าข้อเท็จจริงเหล่านี้ทำให้สรุปได้ว่าปัญหาการทดสอบการเป็นจำนวนเฉพาะอยู่ในโค-อาร์พี
สมมุติ *n* เป็นจำนวนประกอบ ถ้าเราเลือกตัวเลขที่น้อยกว่า *n* มี 100 ตัว ความน่าจะเป็นที่จะหา "ตัวยืนยัน" ดังกล่าวไม่เจอจะเป็น (1/4) 100 ซึ่งในทางปฏิบัติแล้ววิธีนี้ก็เป็นการทดสอบการเป็นจำนวนเฉพาะที่ใช้ได้วิธีหนึ่ง และอาจจะไม่มีวิธีใดเลยที่ใช้ได้ดีในทางปฏิบัติเมื่อ *n* มีขนาดใหญ่มาก เราสามารถลดความน่าจะเป็นที่จะเกิดความผิดพลาดให้เหลือเท่าใดก็ได้ โดยการเพิ่มรอบการทำงานให้มากพอ

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

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

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

    หาการตัดน้อยสุด (กราฟไม่มีทิศทาง G) {
        ตราบใดที่ G ยังมีโหนดมากกว่า 2 โหนด ให้ทำ{
            สุ่มเลือกเส้นเชื่อม (u,v) จาก G
            หด (contract) เส้นเชื่อม โดยให้รักษาการมีเส้นเชื่อมหลายเส้น (multi-edge) เอาไว้
            ลบลูปทั้งหมดออก
        }
        ให้เส้นเชื่อมที่เหลืออยู่เป็นเอาต์พุต
    }

ในที่นี้ การหดเส้นเชื่อม (u,v) หมายความถึงการเพิ่มโหนดขึ้นใหม่ (ให้ชื่อ w)
แล้วให้แทนทุกเส้นเชื่อม (u,x) และ (v,x) ด้วย (w,x) แล้วลบโหนด u และ v
ออกจาก G

ให้ *n = |V[G]|*
แสดงได้ว่าขั้นตอนวิธีนี้ให้ผลเป็นการตัดที่น้อยที่สุดด้วยความน่าจะเป็นอย่างน้อย *n<sup>-2</sup>*
ดังนั้นหากให้ทำงาน *n<sup>2</sup>log (n) * รอบและเลือกผลลัพธ์ที่มีค่าน้อยที่สุด
ก็จะสามารถหาการตัดที่น้อยที่สุดได้ด้วยความน่าจะเป็นสูง

## อ้างอิง

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

ส
หมวดหมู่:ขั้นตอนวิธีแบบสุ่ม