ขั้นตอนวิธีของเฟรย์วัลส์
ขั้นตอนวิธีของเฟรย์วัลส์ (อังกฤษ: Freivalds' algorithm) เป็นขั้นตอนวิธีแบบสุ่ม (randomised algorithm) ที่รูซินส์ มาร์ตินส์ เฟรย์วัลส์ (Rusins Martins Freivalds) นักวิทยาศาสตร์ชาวลัตเวีย นำเสนอขึ้นสำหรับใช้ตรวจสอบความเท่ากันของผลคูณของเมทริกซ์กับเมทริกซ์ต้นแบบ[1]
แนวคิดเบื้องต้น
[แก้]ในบรรดาปัญหาทั้งหมดในเชิงคณิตศาสตร์ มีปัญหาจำนวนมากที่มีขั้นตอนที่สามารถตรวจคำตอบได้เร็วกว่าการหาคำตอบ เช่น ปัญหาเอ็นพี และมีปัญหาจำนวนมากมายที่ขั้นตอนวิธีแก้ปัญหาที่ใช้ขั้นตอนวิธีแบบสุ่มให้ประสิทธิภาพดีกว่าขั้นตอนวิธีที่ตรงไปตรงมา ขั้นตอนวิธีของเฟรย์วัลส์ เป็นขั้นตอนวิธีหนึ่งที่ใช้ขั้นตอนวิธีแบบสุ่ม เพื่อลดเวลาในการตรวจสอบคำตอบของการคูณเมทริกซ์ โดยให้เมทริกซ์ต้นฉบับ และผลคูณของเมทริกซ์ต้นฉบับเป็นข้อมูลนำเข้าของขั้นตอนวิธี ตัวขั้นตอนวิธีก็จะตรวจสอบความเท่ากันจากนั้นคืนค่าว่าเมทริกซ์ต้นฉบับ กับผลคูณของเมทริกซ์ต้นฉบับที่รับมาเป็นข้อมูลนำเข้ามีค่าเท่ากันหรือไม่ ทั้งนี้ขั้นตอนวิธีนี้ตั้งอยู่บนพื้นฐานของความน่าจะเป็น จึงทำให้มีความน่าจะเป็นที่ตัวขั้นตอนวิธีแบบสุ่มนี้จะตอบผิดไปจากความเป็นจริง เช่น ตอบว่า ใช่ ผลคูณของเมทริกซ์ต้นฉบับ เท่ากันกับเมทริกซ์ต้นฉบับที่ได้รับเป็นข้อมูลนำเข้า ทั้งที่จริงๆ แล้ว ผลคูณของเมทริกซ์ต้นฉบับอาจจะไม่เท่ากันกับข้อมูลนำเข้าก็ได้ ทำให้ขั้นตอนวิธีนี้ดูจะไร้ประโยชน์ เพราะดูไม่ต่างจากการเดาสุ่ม แต่ที่จริงแล้วขั้นตอนวิธีนี้สามารถลดความน่าจะเป็นในการตอบผิดได้โดยการทำซ้ำ ซึ่งจะทำให้ความน่าจะเป็นในการตอบผิดมีค่าน้อยกว่าการสุ่มมาก
ขั้นตอนวิธี
[แก้]ข้อมูลนำเข้า
[แก้]เมทริกซ์จตุรัส 3 เมทริกซ์ มีขนาด ได้แก่
ข้อมูลส่งออก
[แก้]ตอบ ใช่ ถ้า
ตอบ ไม่ใช่ ถ้า
วิธีการ
[แก้]- สุ่ม เวกเตอร์ ขนาด .
- คำนวณ .
- ตรวจสอบว่า เป็นเวกเตอร์ศูนย์หรือไม่ คืนค่า ใช่ ถ้า เป็นเวกเตอร์ศูนย์ คืนค่า ไม่ใช่ถ้า ไม่ได้เป็นเวกเตอร์ศูนย์
ความซับซ้อนเชิงเวลา
[แก้]ทำงานใน O(n2) [2] ซึ่งเร็วกว่าการคูณเมทริกซ์แล้วเปรียบเทียบทีละตัว (ทำงานใน O(n3) ) รวมถึงเร็วกว่า ขั้นตอนวิธีของ Coppersmith-Winograd ซึ่งเป็นขั้นตอนวิธีในการหาผลคูณของเมทริกซ์ที่เร็วที่สุดในปัจจุบัน (ทำงานใน O(n2.376)) มาก
วิเคราะห์ความผิดพลาด
[แก้]ขั้นตอนวิธีนี้รับประกันว่า ถ้า แล้วความน่าจะเป็นในการตอบผิดจะเป็น 0, ถ้า แล้วความน่าจะเป็นในการตอบผิดมีค่าไม่เกิน
- พิจารณากรณีที่
- สำหรับทุก ที่เป็นไปได้ดังนั้นความน่าจะเป็นในการตอบผิดเป็น 0
- พิจารณากรณีที่
- กำหนดให้ เนื่องจาก แสดงว่าจะมีค่า i,j บางค่าที่
- โดย กฎของเบย์ (Bayes' theorem)
-
- เพราะฉะนั้น
หมายเหตุ
[แก้]แม้ว่าขั้นตอนวิธีนี้อาจมีความผิดพลาดสูงได้ถึง แต่ในการใช้งานจริงสามารถลดความผิดพลาดได้ การทำงานขั้นตอนวิธีนี้ซ้ำหลาย ๆ ครั้งโดยใช้ ที่แตกต่างกัน จะช่วยลดความน่าจะเป็นในการตอบผิดลงไปได้
สมมุติว่าต้องการทำขั้นตอนวิธีนี้ซ้ำกัน ครั้ง พบว่าความน่าจะเป็นในการตอบผิดมีค่า ≤ ซึ่งมีค่าลดลงเป็นฟังก์ชันเลขชี้กำลังเมื่อเทียบกับค่า
เชิงอรรถ
[แก้]- ↑ "Professor Rusins Martins FREIVALDS's website". คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2009-01-05. สืบค้นเมื่อ 2011-09-08.
- ↑ Raghavan, Prabhakar (1997). "Randomized algorithms". ACM Computing Surveys (CSUR). 28. doi:10.1145/234313.234327. สืบค้นเมื่อ 2011-09-20.