ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล add links + formatting |
เพิ่มเติม |
||
บรรทัด 1:
{{โครง}}
{{shortcut|[[randomized algorithm]]}}
'''อัลกอริทึมแบบสุ่ม''' (randomized algorithm) เป็น[[อัลกอริทึม]]ที่ยอมให้มีการโยนเหรียญได้ ในทางปฏิบัติ เครื่องที่ใช้ทำงานอัลกอริทึมนี้ จะต้องใช้[[ตัวสร้างเลขสุ่มเทียม]] (pseudo-random number generator) ในการสร้าง[[ตัวเลขสุ่ม]]ขึ้นมา อัลกอรึทึมโดยทั่วๆไปมักใช้[[บิทสุ่ม]] (random bit) สำหรับเป็นอินพุตเสริม เพื่อชี้นำการกระทำของมันต่อไป โดยมีความหวังว่าจะช่วยให้มีประสิทธิภาพที่ดีใน "กรณีส่วนมาก(average case)" หรือหากพูดในทาง[[คณิตศาสตร์]]ก็คือ ประสิทธิภาพของอัลกอริทึมมีค่าเท่ากับ[[ตัวแปรสุ่ม]] (random variable) ซึ่งคำนวณจากบิทสุ่ม โดยหวังว่าจะมี[[ค่าคาดหวัง]] (expected value) ที่ดี กรณีที่แย่มากที่สุดมักจะมีโอกาสเกิดขึ้นน้อยมากจนแทบจะไม่ต้องสนใจ
เส้น 8 ⟶ 9:
ในตัวอย่างที่กล่าวมานี้ อัลกอริทึมแบบสุ่มให้ผลลัพธ์ที่ถูกต้องเสมอ เพียงแต่ว่ามีความเป็นไปได้อยู่บ้าง ที่อัลกอริทึมจะใช้เวลานานในการทำงาน บางครั้งเราอาจต้องการอัลกอริทึมที่ทำงานได้เร็วในทุกๆสถานการณ์ แต่เราก็ต้องแลกด้วย''โอกาสเกิดความผิดพลาด'' อัลกอริทึมประเภทแรก(ถูกต้องเสมอ แต่อาจใช้เวลานาน)เรียกว่า[[อัลกอริทึมลาสเวกัส]] และแบบหลัง(ต้องทำงานเร็ว แต่มีข้อผิดพลาดได้)เรียกว่า[[อัลกอริทึมมอนติคาร์โล]] (ตามชื่อของ[[วิธีมอนติคาร์โล]]ที่ใช้ในการจำลอง (simulation)) สังเกตว่าอัลกอริทึมลาสเวกัสทุกอันสามารถแปลงเป็นอัลกอริทึมมอนติคาร์โลได้ โดยการตอบออกไปมั่วๆ หากไม่สามารถหาคำตอบได้ในเวลาที่กำหนด
[[ทฤษฎีความซับซ้อนในการคำนวณ]]ซึ่งเป็นการศึกษาเกี่ยวกับทรัพยากรทางการคำนวณที่ต้องใช้ในการแก้ปัญหาหนึ่งๆ ได้สร้างแบบจำลองของอัลกอริทึมแบบสุ่มให้เป็น''[[เครื่องจักรทัวริง]][[เครื่องจักรทัวริงเชิงความน่าจะเป็น|เชิงความน่าจะเป็น]]'' ทั้งอัลกอริทึมลาสเวกัสและมอนติคาร์โลได้ถูกนำมาพิจารณา รวมถึง "คลาสของความซับซ้อน" หลายๆคลาสก็ได้ถูกนำมาศึกษา คลาสของความซับซ้อนแบบสุ่มแบบที่เป็นพื้นฐานที่สุดคือแบบ[[อาร์พี]] ซึ่งเป็นคลาสของ[[ปัญหาการตัดสินใจ]]ที่มีอัลกอริทึมแบบสุ่ม(หรือเครื่องจักรทัวริงเชิงความน่าจะเป็น)ที่มีประสิทธิภาพ(ทำงานได้ได้ในเวลาโพลิโนเมียล) ที่สามารถตอบว่า"ไม่"ได้ถูกต้องเสมอ และสามารถตอบว่า"ใช่"ได้ โดยมีโอกาสถูกต้องอย่างน้อย 1/2 คลาสส่วนกลับ(complement)ได้แก่โค-อาร์พี และคลาสของปัญหาซึ่งทั้งคำตอบ"ใช่"และ"ไม่" สามารถมีค่าความน่าจะเป็นได้ทั้งคู่ (นั่นคือ ไม่ได้บังคับให้ต้องตอบถูกต้องเสมอ) เรียกว่า[[ซีพีพี]](ZPP) สำหรับปัญหาซึ่ง(เชื่อกันว่า)อยู่นอกคลาสนี้ เช่นปัญหา[[เอ็นพีแบบยาก]] (ซึ่งแม้แต่อัลกอริทึมแบบสุ่มก็ไม่สามารถแก้ได้) จำเป็นต้องแก้ด้วย[[อัลกอริทึมแบบประมาณ]]
ในประวัตศาสตร์ อัลกอริทึมแบบสุ่มเริ่มเป็นที่รู้จัก จากการค้นพบของ[[การตรวจสอบการเป็นจำนวนเฉพาะมิลเลอร์-เรบิน|มิลเลอร์และเรบิน]]ในปี 1976 ว่า ปัญหา[[การตรวจสอบการเป็นจำนวนเฉพาะ]]ของตัวเลข สามารถแก้ได้อย่างมีประสิทธิภาพด้วยอัลกอริทึมแบบสุ่ม ในเวลานั้น ยังไม่มี[[อัลกอริทึมดิเทอร์มินิสติก]]สำหรับปัญหานี้เลย
==แหล่งอ้างอิง==
| |||