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

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Octahedron80 (คุย | ส่วนร่วม)
Octahedron80 (คุย | ส่วนร่วม)
แทนที่ "อัลกอริทึมแบบสุ่ม" → "ขั้นตอนวิธีแบบสุ่ม" +แทนที่ "อัลกอริทึม" → "ขั้นตอนวิธี"ด้วย[[WP:iScript
บรรทัด 1:
{{ช่วยดูหน่อย}}
{{shortcut|[[randomized algorithm]]}}
'''อัลกอริทึมขั้นตอนวิธีแบบสุ่ม''' (randomized algorithm) เป็น[[อัลกอริทึมขั้นตอนวิธี]]ที่ยอมให้มีการโยนเหรียญได้ ในทางปฏิบัติ เครื่องที่ใช้ทำงานอัลกอริทึมขั้นตอนวิธีนี้ จะต้องใช้[[ตัวสร้างเลขสุ่มเทียม]] (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)<sup>100</sup> ซึ่งในทางปฏิบัติแล้ววิธีนี้ก็เป็นการทดสอบการเป็นจำนวนเฉพาะที่ใช้ได้วิธีหนึ่ง และอาจจะไม่มีวิธีใดเลยที่ใช้ได้ดีในทางปฏิบัติเมื่อ ''n'' มีขนาดใหญ่มาก เราสามารถลดความน่าจะเป็นที่จะเกิดความผิดพลาดให้เหลือเท่าใดก็ได้ โดยการเพิ่มรอบการทำงานให้มากพอ
 
ดังนั้น ในทางปฏิบัติแล้ว จึงมักไม่ค่อยมีใครสนใจกับโอกาสเกิดความผิดพลาดที่มีเล็กน้อยนี้สักเท่าไร เพราะเราสามารถทำให้มันน้อยลงเท่าไรก็ได้ตามใจปรารถนา ที่จริงแล้ว ถึงแม้ว่าเราจะ[[การทดสอบการเป็นจำนวนเฉพาะของ AKS|มี]]อัลกอริทึมขั้นตอนวิธีในการตรวจสอบการเป็นจำนวนเฉพาะแบบดิเทอร์มินิสติกที่สามารถทำงานได้ในเวลาโพลิโนเมียลแล้ว มันก็ยังไม่ได้ถูกนำไปใช้แทนวิธีเชิงความน่าจะเป็นแบบเดิมใน[[ซอฟต์แวร์]][[วิทยาการเข้ารหัสลับ|ด้านการเข้ารหัสลับ]] และก็ยังไม่มีใครคิดว่าจะเป็นเช่นนั้นได้ในอนาคตอันใกล้นี้ด้วย
 
สมมุติว่าเราใช้วิธีเชิงสุ่ม แล้วมีความน่าจะเป็นที่จะเกิดความผิดพลาดเป็น 2<sup>−1000</sup> คำถามที่ตามมาคือ ตัวเลขนี้เกิดจาก[[การพิสูจน์ทางคณิตศาสตร์]]หรือไม่? ถึงแม้ว่าโอกาสผิดพลาดจะน้อยมากเมื่อเทียบกับโอกาสเกิดความผิดพลาดของฮาร์ดแวร์ที่ใช้ทำมัน หรือโอกาสที่คนตรวจบทพิสูจน์จะมองข้ามความผิดพลาดไป แต่จริงๆแล้วการบอกว่ามีความน่าจะเป็นน้อยนี้ ควรให้ความหมายว่าอย่างไรดี?
 
[[ควิกซอร์ต]] น่าจะเป็นอัลกอริทึมขั้นตอนวิธีที่ใช้จริงที่เราคุ้นเคยที่สุดที่ใช้การสุ่มอย่างได้ผลดีมากๆ อัลกอริทึมขั้นตอนวิธีนี้ในแบบที่เป็นดิเทอร์มินิสติกต้องใช้เวลา ''[[สัญกรณ์ Big O|O]](n^2)'' ในการเรียงเลข ''n'' ตัว สำหรับอินพุทบางรูปแบบ เช่น อาร์เรย์ที่ถูกเรียงมาอยู่แล้ว อย่างไรก็ตาม ถ้าอัลกอริทึมขั้นตอนวิธีสลับตัวในอาร์เรย์แบบสุ่มก่อนที่จะเริ่มทำงาน มันจะมีความน่าจะเป็นสูงที่จะทำงานเสร็จในเวลา ''O(n log n)'' สำหรับอินพุททุกรูปแบบ ความแตกต่างระหว่างสองแบบนี้จะมีความสำคัญมาก เมื่อเราต้องจัดเรียงข้อมูลจำนวนมากๆ
 
ตัวอย่างที่[[ซับซ้อน]]ขึ้นกว่าอีกหน่อย คือการใช้อัลกอริทึมขั้นตอนวิธีเชิงสุ่มแก้ปัญหาทางด้าน[[ทฤษฎีกราฟ]] นี่คืออัลกอริทึมขั้นตอนวิธีสำหรับแก้ปัญหา [[การตัดให้น้อยที่สุด]](minimum cut)
 
หาการตัดน้อยสุด(กราฟไม่มีทิศทาง G) {
บรรทัด 42:
 
ให้ ''n = |V[G]|''
สามารถแสดงได้ว่า อัลกอริทึมขั้นตอนวิธีนี้ให้ผลเป็นการตัดที่น้อยที่สุด ด้วยความน่าจะเป็นอย่างน้อย ''n<sup>-2</sup>''
ดังนั้นหากเราให้มันทำงาน ''n<sup>2</sup>log(n)'' รอบ และเลือกผลลัพธ์ที่มีค่าน้อยที่สุด
เราก็จะสามารถหาการตัดที่น้อยที่สุดได้ด้วยความน่าจะเป็นสูง