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