ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีแบบสุ่ม"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
เริ่มต้น |
เพิ่มเติม |
||
บรรทัด 1:
{{โครง}}
{{shortcut|[[Randomized algorithm]]}}
อัลกอริทึมแบบสุ่ม เป็น[[อัลกอริทึม]]ที่ยอมให้มีการโยนเหรียญได้ ในทางปฏิบัติ เครื่องที่ใช้ทำงานอัลกอริทึมนี้ จะต้องใช้[[ตัวสร้างเลขสุ่มเทียม]]ในการสร้างตัวเลขสุ่มขึ้นมา อัลกอรึทึมโดยทั่วๆไปมักใช้บิทสุ่ม(random bit)สำหรับเป็นอินพุตเสริม เพื่อชี้นำการกระทำของมันต่อไป โดยมีความหวังว่าจะช่วยให้มีประสิทธิภาพที่ดีใน"กรณีส่วนมาก(average case)" หรือหากพูดในทางคณิตศาสตร์ก็คือ ประสิทธิภาพของอัลกอริทึม
ตัวอย่าง ลองพิจารณาการหาตัวอักษร a ใน[[อาร์เรย์]]ขนาด ''n'' เมื่อสมมุติว่าครึ่งหนึ่งในอาร์เรย์นี้เป็น a และอีกครึ่งหนึ่งเป็น b วิธีที่เห็นชัดวิธีหนึ่งคือการดูแต่ละตัวในอาร์เรย์ แต่วิธีนี้อาจทำให้ต้องดูถึง n/2 ตัวในกรณีที่แย่ที่สุด (นั่นคือครึ่งแรกของอาร์เรย์เป็น b ทั้งหมด) การพยายามแก้ไขเหตุการณ์นี้โดยเปลี่ยนลำดับการดู เช่น อ่านจากหลังมาหน้า หรืออ่านตัวเว้นตัว ก็ไม่ได้ช่วยให้อะไรดีขึ้นเลย ที่จริงแล้ว วิธีการใดก็ตามที่ลำดับของการตรวจสอบสมาชิกแต่ละตัวถูกกำหนดไว้ตายตัวแล้ว (นั่นคือ เป็นอัลกอริทึม''ดิเทอร์มินิสติก'') เราจะไม่สามารถรับประกันได้เลยว่าอัลกอริทึมจะทำงานสำเร็จอย่างรวดเร็ว ใน''ทุกๆอินพุทที่เป็นไปได้'' แต่ถ้าหากเราตรวจสอบสมาชิกในอาร์เรย์แบบสุ่ม(ไม่มีลำดับที่แน่นอน) ''มีความน่าจะเป็นสูง''ที่เราจะสามารถหา a พบในเวลาอันรวดเร็ว ''ไม่ว่าอินพุทจะเป็นเช่นไรก็ตาม''
==แหล่งอ้างอิง==
# R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
[[Category:อัลกอริทึม]]
[[en:randomized algorithm]]
[[de:randomisierter Algorithmus]]
[[he:אלגוריתם אקראי]]
[[zh:随机化算法]]
| |||