ขั้นตอนวิธีของเบรนท์
ขั้นตอนวิธีของเบรนท์ (อังกฤษ: Brent's algorithm) เรียกอีกชื่อหนึ่งว่า "The Teleporting Turtle Algorithm" ได้รับการคิดค้นขึ้นโดย Richard Peirce Brent ในปี 1980 เพื่อใช้ในการตรวจสอบการมีวงรอบ (cycle) ในปัญหาที่มีลักษณะเป็นรายการโยงเดี่ยว ตัวอย่างเช่น ฟังก์ชันวนซ้ำ การแยกตัวประกอบ ตัวสร้างเลขสุ่มเทียม และปัญหาอื่นๆ อีกมากมาย
ขั้นตอนวิธีของเบรนท์ มีหลักการทำงานคล้ายๆ กับขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's Tortoise and the Hare algorithm) ข้อได้เปรียบของขั้นตอนวิธีของเบรนท์คือจะใช้เวลาการทำงานน้อยกว่าและสามารถหาความยาวของวงรอบได้โดยตรง ไม่จำเป็นต้องไล่ค้นหาในลำดับย่อยอีกครั้ง
ตัวอย่างการใช้งาน
จากรูป หากเริ่มเดินจากจุด 2 จะมีเส้นทางการเดินดังนี้ 2 → 0 → 6 → 3 → 1 → 6 → 3 → ... พบว่าการวนซ้ำนี้มีวงรอบ เนื่องจากมีการเดินทางซ้ำในเส้นทางเดิม คือ 6 → 3 → 1 ซึ่งขั้นตอนวิธีของเบรนท์มีความสามารถในการตรวจสอบการมีวงจรเช่นนี้ได้นั่นเอง
การอธิบายขั้นตอนวิธี
การทำงานของขั้นตอนวิธีของเบรนท์ เริ่มต้นโดยการกำหนดตัววนซ้ำ 2 ตัวคือ กระต่าย และ เต่า ยืนอยู่ที่จุดเริ่มต้น หลังจากนั้นให้ กระต่าย เดินไปทีละก้าวตามเส้นทาง และจะทำการเคลื่อนย้าย เต่า มาตำแหน่งเดียวกับ กระต่าย เมื่อถึงเวลาที่กำหนด
- โดยหาก กระต่าย เดินไปได้ถึงจุดจบของรายการโยง นั่นแสดงว่า ไม่มีวงรอบ
- แต่หาก กระต่าย เดินไปเจอ เต่า แสดงว่า มีวงรอบ
Flow Chart :
รหัสเทียมแสดงการทำงาน
tortoise = begin_point hare = begin_point steps_count = 0 steps_limit = 2 loop forever: if hare == end_point: return 'No Cycle Found' hare = hare.next steps_count += 1 if hare == tortoise: return 'Cycle Found' if steps_count == steps_limit: steps_count = 0 steps_limit *= 2 // Teleport the tortoise to hare's position tortoise = hare การวิเคราะห์ความซับซ้อนเชิงเวลา
สำหรับขั้นตอนวิธีของเบรนท์นั้น จะมีประสิทธิภาพในการทำงานเท่ากับขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's Tortoise and the Hare algorithm) คือ O(λ+μ) โดย μ คือ ความยาวของทางเดินจากจุดเริ่มต้น ไปยังวงรอบ (Cycle) ที่มี λ จุดยอด แต่ในความเป็นจริงแล้ว ขั้นตอนวิธีตรวจสอบการมีวงรอบของเบรนท์ ใช้เวลาในการทำงานเฉลี่ยเร็วกว่าขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ประมาณ 36% ซึ่งมีผลทำให้ประสิทธิภาพการทำงานของ "ขั้นตอนวิธีโรห์ของพอลลาร์ด" (Pollard rho algorithm) เพิ่มขึ้นประมาณ 24% อีกด้วย
ขั้นตอนวิธีที่เกี่ยวข้อง
- ขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's cycle-finding algorithm)
- ขั้นตอนวิธีโรห์ของพอลลาร์ด (Pollard rho algorithm)
อ้างอิง
- Brent's cycle detection algorithm: Algorithmic cryptanalysis, Antoine Joux, Chapman & Hall/CRC Taylor & Francis Group, 2009, P.266
- http://lab.iisec.ac.jp/labs/tanaka/publications/pdf/conference/conference-86-02.pdf
- Brent, R. P. (1980), "An improved Monte Carlo factorization algorithm" (PDF), BIT, 20 (2): 176–184, doi:10.1007/BF01933190.