ขั้นตอนวิธีของเบรนท์

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีของเบรนท์[1] (อังกฤษ: Brent's algorithm) เรียกอีกชื่อหนึ่งว่า "The Teleporting Turtle Algorithm" ได้รับการคิดค้นขึ้นโดย Richard Peirce Brent ในปี 1980 เพื่อใช้ในการตรวจสอบการมีวงรอบ[2] (cycle) ในปัญหาที่มีลักษณะเป็นรายการโยงเดี่ยว ตัวอย่างเช่น ฟังก์ชันวนซ้ำ การแยกตัวประกอบ ตัวสร้างเลขสุ่มเทียม และปัญหาอื่นๆ อีกมากมาย

ขั้นตอนวิธีของเบรนท์ มีหลักการทำงานคล้ายๆ กับขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's Tortoise and the Hare algorithm) ข้อได้เปรียบของขั้นตอนวิธีของเบรนท์คือจะใช้เวลาการทำงานน้อยกว่าและสามารถหาความยาวของวงรอบได้โดยตรง ไม่จำเป็นต้องไล่ค้นหาในลำดับย่อยอีกครั้ง

ตัวอย่างการใช้งาน[แก้]

จากรูป หากเริ่มเดินจากจุด 2 จะมีเส้นทางการเดินดังนี้ 2 → 0 → 6 → 3 → 1 → 6 → 3 → ... พบว่าการวนซ้ำนี้มีวงรอบ เนื่องจากมีการเดินทางซ้ำในเส้นทางเดิม คือ 6 → 3 → 1 ซึ่งขั้นตอนวิธีของเบรนท์มีความสามารถในการตรวจสอบการมีวงจรเช่นนี้ได้นั่นเอง

Functional graph.svg

การอธิบายขั้นตอนวิธี[แก้]

การทำงานของขั้นตอนวิธีของเบรนท์[3] เริ่มต้นโดยการกำหนดตัววนซ้ำ 2 ตัวคือ กระต่าย และ เต่า ยืนอยู่ที่จุดเริ่มต้น หลังจากนั้นให้ กระต่าย เดินไปทีละก้าวตามเส้นทาง และจะทำการเคลื่อนย้าย เต่า มาตำแหน่งเดียวกับ กระต่าย เมื่อถึงเวลาที่กำหนด

  • โดยหาก กระต่าย เดินไปได้ถึงจุดจบของรายการโยง นั่นแสดงว่า ไม่มีวงรอบ
  • แต่หาก กระต่าย เดินไปเจอ เต่า แสดงว่า มีวงรอบ

Flow Chart :[แก้]

Brent flowchart.png

รหัสเทียมแสดงการทำงาน[แก้]

  1. tortoise = begin_point
    
  2. hare = begin_point
    
  3.  
    
  4. steps_count = 0
    
  5. steps_limit = 2
    
  6.  
    
  7. loop forever:
    
  8.     if hare == end_point: return 'No Cycle Found'
    
  9.  
    
  10.     hare = hare.next
    
  11.     steps_count += 1
    
  12.  
    
  13.     if hare == tortoise: return 'Cycle Found'
    
  14.  
    
  15.     if steps_count == steps_limit:
    
  16.         steps_count = 0
    
  17.         steps_limit *= 2
    
  18.         // Teleport the tortoise to hare's position
    
  19.         tortoise = hare
    

การวิเคราะห์ความซับซ้อนเชิงเวลา[แก้]

สำหรับขั้นตอนวิธีของเบรนท์นั้น จะมีประสิทธิภาพในการทำงานเท่ากับขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ (Floyd's Tortoise and the Hare algorithm) คือ O(λ+μ) โดย μ คือ ความยาวของทางเดินจากจุดเริ่มต้น ไปยังวงรอบ (Cycle) ที่มี λ จุดยอด แต่ในความเป็นจริงแล้ว ขั้นตอนวิธีตรวจสอบการมีวงรอบของเบรนท์ ใช้เวลาในการทำงานเฉลี่ยเร็วกว่าขั้นตอนวิธีตรวจสอบการมีวงรอบของฟลอยด์ประมาณ 36% ซึ่งมีผลทำให้ประสิทธิภาพการทำงานของ "ขั้นตอนวิธีโรห์ของพอลลาร์ด" (Pollard rho algorithm) เพิ่มขึ้นประมาณ 24% อีกด้วย


ขั้นตอนวิธีที่เกี่ยวข้อง[แก้]


อ้างอิง[แก้]

  1. Brent's cycle detection algorithm: Algorithmic cryptanalysis, Antoine Joux, Chapman & Hall/CRC Taylor & Francis Group, 2009, P.266
  2. http://lab.iisec.ac.jp/labs/tanaka/publications/pdf/conference/conference-86-02.pdf
  3. Brent, R. P. (1980), "An improved Monte Carlo factorization algorithm", BIT 20 (2): 176–184, doi:10.1007/BF01933190 .