ขั้นตอนวิธีการตรวจสอบการเกิดวงวนของฟลอยด์

ขั้นตอนวิธีการตรวจสอบการเกิดวงวนของฟลอยด์ (อังกฤษ: Floyd's cycle-finding algorithm) หรือเรียกอีกชื่อหนึ่งว่า ขั้นตอนวิธีเต่าและกระต่าย (อังกฤษ: Tortoise and hare algorithm) เป็นขั้นตอนวิธีที่ง่ายและรวดเร็วที่สุดในการตรวจสอบวงในลำดับรายการของข้อมูล ถูกคิดค้นขึ้น ในปี ค.ศ. 1967 โดย นักวิทยาศาสตร์คอมพิวเตอร์สัญชาติอเมริกัน ชื่อ โรเบิร์ต ฟลอยด์ (Robert W. Floyd) เพื่อใช้เป็นขั้นตอนในการตรวจสอบวงที่เกิดขึ้นภายในลำดับของข้อมูลในโครงสร้างข้อมูลแบบรายการ (list) ขั้นตอนวิธีของฟลอยด์นี้ มีความน่าสนใจตรงที่ เป็นขั้นตอนที่ใช้ตัวชี้ 2 ตัว ในการทำงาน ใช้ขอบเขตเวลาไม่เกิน λ+μ (O (λ+μ)) และ ใช้เนื้อที่บนหน่วยความจำเป็นค่าคงตัว (O (1))

หมายเหตุ : λ คือ ความยาวจากจุดเริ่มต้นของรายการไปถึงจุดแรกของการเกิดวง μ คือ ค่าความยาวของ 1 รอบวง (ขนาดของวง) การตรวจสอบวงวนดังกล่าวได้ถูกนำมาใช้ในการตรวจสอบรายการของข้อมูลเพื่อหาตำแหน่งการเกิดของวงวนไม่สิ้นสุดที่เกิดขึ้นในรายการของข้อมูล หรือ วงวนเครื่องสถานะจำกัด หรือ "ไฟไนต์สเตทแมชชีน" (finite state machine) เพื่อที่จะกำจัดวงวนที่ตรวจพบได้ดังกล่าว

แนวคิดการทำงาน[แก้]

อธิบายแนวคิดการทำงานโดยการเปรียบเทียบพฤติกรรมของตัวชี้ทั้งสองเป็นเต่าและกระต่ายตามลำดับ (Tortoise and hare) ซึ่งตัวชี้ทั้งสองจะทำการวิ่งไปบนรายการของข้อมูล โดยเริ่มจากจุดเริ่มต้นของข้อมูลพร้อมกัน โดยที่ตัวชี้ที่เคลื่อนที่ช้ากว่า เปรียบเสมือนเป็นเต่า จะเคลื่อนที่ไปครั้งละ 1 ก้าว ส่วนตัวชี้อีกตัวหนึ่งซึ่งเคลื่อนที่เร็วกว่าเสมือนกับกระต่าย จะเคลื่อนไปบนรายการของข้อมูลด้วยความเร็วเป็นสองเท่าของเต่า จะตรวจสอบการเกิดวงได้จากการที่ตัวชี้ทั้งสองเคลื่อนที่ไปในรายการของข้อมูลจะมีการพิจารณาจากค่าภายในข้อมูลของตำแหน่งที่ที่ตัวชี้แต่ละตัวชี้อยู่ ถ้าในรายการนั้น มีวงวนแสดงว่ากระต่ายก็มีโอกาสวิ่งวนมาพบกับเต่า (ตรวจสอบได้จาก เมื่อตัวชี้ทั้งสองเคลื่อนที่มาพบกันที่ตำแหน่งเดียวกัน ค่าภายในข้อมูลเท่ากัน แสดงว่ามีวงวนในรายการ) แต่ถ้าหากภายในรายการไม่มีวงวนแล้วนั้นกระต่ายจะวิ่งไปจนถึงปลายทาง (ปลายสุดของรายการ) โดยไม่พบกับเต่าเลยนั่นเอง

ขั้นตอนวิธี[แก้]

อธิบายใจความสำคัญของขั้นตอนวิธีได้ดังนี้ ในทุกๆ ค่า i >= μ, X (i) = X (i + kλ), โดยที่ k >= 0 หรืออธิบายง่ายๆ คือที่ i = kλ (โดยที่ k มีค่ามากกว่า 0) เมื่อเราพบตำแหน่งที่ X (i) = X (2i) ( หรือ ในทางกลับกันคือ ถ้าเราพบตำแหน่งที่ X (2i) = X (i) ) เราจะพบว่าค่า i ที่น้อยที่สุดจะเป็นตัวคูณของ λ (โดยที่ i มีค่า มากกว่าเท่ากับ μ) ดังนั้นเราต้องทำการตรวจสอบค่าซ้ำกันที่เกิดในกรณีที่กล่าวข้างต้นเพื่อหาจุด v ที่ ค่าใน X (i) = X (2i) เมื่อเราพบจุด v ดังกล่าวแล้ว นั่นคือเราพบว่ามีวงอยู่ในรายการของข้อมูลนั่นเอง

นอกจากนั้นเรายังสามารถย้อนหาระยะจากต้นรายการมาจนถึงจุดแรกที่เกิดวง (λ) ได้โดย การหาจุดที่ X (ν + μ) = X (μ) ทำได้ดังนี้ คือ ให้ตัวชี้เต่ากลับไปเริ่มต้นใหม่ที่ต้นรายการ และตัวชี้ที่แทนกระต่ายอยู่ที่เดิม (เต่าและกระต่ายอยู่ห่างกันเป็นระยะ v) แล้วให้ทั้งสองวิ่งด้วยความเร็วเท่ากันคือ 1 จนกว่าจะพบจุดที่ค่าใน X (ν + μ) = X (μ) เป็นจุดแรกของการเกิดวงนั่นเอง และ เรายังสามารถหาความยาวสั้นสุดของวงได้โดยหาจากจุดที่ X (μ + λ) = X (μ) นั่นเอง สามารถทำได้ดังนี้ เมื่อเราได้ ระยะจากต้นรายการมาจนถึงจุดแรกที่เกิดวง (λ) มาแล้วเริ่มจากจุดแรกที่เกิดวง ให้เราทำการวิ่งโดยใช้ตัวชี้เต่าหยุดอยู่กับที่ และให้ตัวชี้กระต่ายวิ่งไปทีละ 1 แล้วนับจำนวนครั้งการเคลื่อนที่ของตัวชี้กระต่ายจนกว่าจะวนกลับมาพบกับตัวชี้เต่าอีกครั้งหนึ่ง จะได้จำนวนครั้งของการเคลื่อนที่ที่ได้เท่ากับจำนวนระยะสั้นสุดของ 1 รอบวง

รหัสเทียม[แก้]

เขียนรหัสเทียมได้ดังนี้

   tortoise = head
   hare = head
   Forever:
       if end==hare : return 'No loop' : else : hare = hare.next
       if end==hare : return 'No loop' : else : hare = hare.next
       tortoise = tortoise.next
       if hare==tortoise: return 'Loop found'

รหัสเทียมภาษาไทย

   ขั้นตอนวิธี การตรวจสอบการเกิดวงวนของฟลอยด์ :
   เต่าเริ่มที่ตำแหน่งต้นของรายการ
   กระต่ายเริ่มที่ตำแหน่งต้นของรายการ
   วนซ้ำ {
       ถ้า ตำแหน่งกระต่ายเท่ากับตำแหน่งปลายทาง “ไม่พบวงวน” : หรือ : กระต่ายเคลื่อนตำแหน่งถัดไปอีก 1 ช่อง
       ถ้า ตำแหน่งกระต่ายเท่ากับตำแหน่งปลายทาง “ไม่พบวงวน” : หรือ : กระต่ายเคลื่อนตำแหน่งถัดไปอีก 1 ช่อง
       เต่าเคลื่อนตำแหน่งถัดไปอีก 1 ช่อง
       ถ้าตำแหน่งเต่าเท่ากับตำแหน่งกระต่าย “พบวงวน”
   }

ประสิทธิภาพการทำงาน[แก้]

การทำงาน ใช้ขอบเขตเวลาไม่เกิน λ+μ (O (λ+μ)) และ ใช้ เนื้อที่บนหน่วยความจำเป็นค่าคงตัว (O (1))

หมายเหตุ : λ คือ ความยาวจากจุดเริ่มต้นของรายการไปถึงจุดแรกของการเกิดวง , μ คือ ค่าความยาวของ1รอบวง (ขนาดของวง)

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

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