กลวิธีการค้นหาแบบฟีโบนัชชี

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

ในวิทยาการคอมพิวเตอร์ กลวิธีการค้นแบบฟีโบนัชชี (อังกฤษ: Fibonacci search technique) เป็นกลวิธีการค้นโดยนำเอาจำนวนฟีโบนัชชีมาสร้างเป็นกลวิธีค้นตำแหน่งของข้อมูลในแถวลำดับ ที่ได้รับการเรียงลำดับแล้วโดยใช้หลักการของขั้นตอนวิธีการแบ่งแยกและเอาชนะ ซึ่งเป็นหลักการเดียวกับที่ใช้ในกลวิธีการค้นหาแบบทวิภาค

แต่เมื่อเปรียบเทียบกับกลวิธีการค้นแบบเลขคู่แล้วกลวิธีการค้นแบบฟีโบนัชชีจะมีการตรวจสอบตำแหน่งของข้อมูลโดยใช้การกระจายตัวที่น้อยกว่า ทำให้เกิดข้อได้เปรียบเมื่อใช้กลวิธีการค้นแบบฟีโบนัชชีกับข้อมูลที่ถูกเก็บอยู่ในแหล่งเก็บข้อมูลไม่มีรูปแบบ ซึ่งเวลาในการใช้ค้นตำแหน่งของข้อมูลที่ต้องการในแหล่งข้อมูลดังกล่าวจะขึ้นอยู่กับตำแหน่งของข้อมูลที่ได้มีการเข้าถึงครั้งล่าสุด ยกตัวอย่างแหล่งข้อมูลแบบไม่มีรูปแบบอาธิเช่น แถบบันทึก ที่ซึ่งเวลาในการเข้าถึงข้อมูลใดๆในแถบแม่เหล็กจะขึ้นอยู่กับระยะทางระหว่างข้อมูลนั้นกับข้อมูลที่หัวของแถบแม่เหล็กกำลังอ่านอยู่ ทั้งนี้กลวิธีการค้นแบบฟีโบนัชชียังมีข้อได้เปรียบในการค้นข้อมูลในแคช (Cache) หรือแรม (Ram) ซึ่งเป็นแหล่งข้อมูลแบบไม่มีรูปแบบอีกด้วยเช่นกัน

ลักษณะทั่วไป[แก้]

กลวิธีการค้นแบบฟีโบนัชชีใช้หลักการของขั้นตอนวิธีโดยการแบ่งแยกและเอาชนะโดยการตัดถอนข้อมูลในส่วนที่ไม่สนใจออกจนได้ตำแหน่งของข้อมูลที่ต้องการ การตัดถอนครั้งหนึ่งจะตัดถอนเป็นจำนวนในลำดับของจำนวนฟีโบนัชชี และจะลดค่าของลำดับลงเรื่อยๆทุกครั้งที่พิจารณาเสร็จ กลวิธีการค้นแบบฟีโบนัชชีจะสิ้นสุดลงก็ต่อเมื่อเจอตำแหน่งของข้อมูลที่สนใจหรือค้นแล้วไม่พบว่ามีข้อมูลที่สนใจปรากฏอยู่ในแหล่งข้อมูลเลย

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

ให้ F คือแถวลำดับของจำนวนฟีโบนัชชี ให้ k คือค่าของข้อมูลใดๆในF nคือขนาดของแถวลำดับของข้อมูล ถ้า n เป็นเลขฟีโบนนัชชีให้ Fm=n แต่ถ้า n ไม่ใช่จำนวนฟีโบนัชชีให้ Fm เป็นจำนวนฟีโบนัชชีที่มากกว่า n แต่ใกล้เคียงที่สุด นิยามให้ค่าใน F เหมือนกับลำดับฟีโบนนัชชีโดยให้ Fk+2=Fk+1+Fk โดยที่ k≥0 ,F1=1 และ F0=0

การหาตำแหน่งของข้อมูลที่สนใจสามารถหาตำแหน่งได้โดยทำตามขั้นตอนต่อไปนี้
  1. ให้ k = m
  2. ถ้า k = 0 หมายความว่าไม่พบข้อมูลที่สนใจและให้เลิกทำ
  3. เปรียบเทียบข้อมูลในตำแหน่ง Fk กับตำแหน่ง Fk-1
  4. ถ้าตรงกับข้อมูลที่สนใจก็ให้จบการทำงาน
  5. ถ้าข้อมูลที่สนใจมีค่าน้อยกว่าข้อมูลในตำแหน่ง Fk-1 ให้ทิ้งข้อมูลตั้งแต่ตำแหน่ง Fk+1 ถึง n ให้ k = k-1 แล้วกลับไปทำขั้นตอนที่สองอีกครั้ง
  6. ถ้าข้อมูลที่สนใจมีค่ามากกว่าข้อมูลในตำแหน่ง Fk-1 ให้ทิ้งข้อมูลตั้งแต่ตำแหน่ง 1 ถึง Fk-1 เรียงตัวเลขที่เหลือใหม่จาก 1 ถึง Fk-2 ให้ k = k-2 แล้วกลับไปทำขั้นตอนที่สองใหม่อีกครั้ง


นอกจากนี้ยังมีขั้นตอนวิธีอื่นๆอีกดังต่อไปนี้

ให้ R เป็นตารางที่เก็บสถิติขนาด n ช่อง ให้ ที่มีการเพิ่มขึ้นของลำดับ K โดยที่ K1 < K2 < ... < Kn ขั้นตอนวิธีนี้จะหาข้อมูลที่ต้องการตามค่าของ K โดยจะสมมติว่า N+1 = Fk+1ซึ่งหาก N+1ไม่ใช่จำนวนฟีโบนัชชีก็ให้ใช้หลักเกณฑ์การเปลี่ยนเป็นจำนวนฟีโบนัชชีเช่นเดียวกับขั้นตอนวิธีแรก โดยให้ X เป็นข้อมูลที่ต้องการจะหา

ขั้นที่หนึ่ง ให้ i ← Fk,p ← Fk-1,q ← Fk-2 โดยจากขั้นตอนวิธีจะได้ว่า p และ q เป็นลำดับจำนวนฟีโบนัชชีที่ต่อเนื่องกัน
ขั้นที่สอง ถ้า X < i ให้ไปทำขั้นที่สาม ถ้า X > i ให้ไปทำขั้นตอนที่สี่ แต่ถ้า X = i จะหมายถึงว่าค้นเจอตำแหน่งของข้อมูลแล้ว คำตอบคือที่ตำแหน่งk ให้จบการทำงาน
ขั้นที่สาม ถ้า q = 0 จะหมายถึงว่าค้นไม่เจอข้อมูลที่ต้องการและให้จบการทำงาน ถ้าไม่เช่นนั้นให้ i ← i - q ให้ p ← q แล้วจึงให้ q ← q - p จากนั้นกลับไปทำขั้นตอนที่สอง
ขั้นที่สี่ ถ้า p = 1 จะหมายถึงว่าค้นไม่เจอข้อมูลที่ต้องการและให้จบการทำงาน ถ้าไม่เช่นนั้นให้ i ← i + q ให้ p ← p - q แล้วจึงให้ q ← q - p จากนั้นกลับไปทำขั้นตอนที่สอง

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

ให้ R เป็นแถวลำดับขนาด 13 ช่องมีข้อมูลคือ {1, 4, 5, 7, 9, 11, 13, 16, 18, 20, 25, 27, 30} ต้องการหาว่า 9 อยู่ในตำแหน่งที่เท่าไหร่ในแถวลำดับ

เนื่องจาก 13เป็นจำนวนฟีโบนัชชีจึงให้ F เป็นแถวลำดับขนาดเท่ากันและให้ x = 9
1 4 5 7 9 11 13 16 18 20 25 27 30

1. กำหนดให้ i = F13, p = F8, q = F5 (ขั้นตอนที่หนึ่ง)

1 4 5 7 9 11 13 16 18 20 25 27 30

2. เนื่องจาก x < i (ขั้นตอนที่สอง) จึงกำหนดค่าใหม่ให้ i = F8, p = F5 , q = F3 (ขั้นตอนที่สาม)

1 4 5 7 9 11 13 16 18 20 25 27 30

3. เนื่องจาก x < i (ขั้นตอนที่สอง) จึงกำหนดค่าใหม่ให้ i = F5, p = F3 , q = F2 (ขั้นตอนที่สาม)

1 4 5 7 9 11 13 16 18 20 25 27 30

4. เนื่องจาก x = i จึงได้ว่าค้นเจอค่า 9 ในแถวลำดับที่ช่อง K = 5 (ขั้นตอนที่สอง)

วิเคราะห์ประสิทธิภาพเชิงเวลา[แก้]

จากทฤษฎีสำคัญ (อังกฤษ: Master method) จะได้ว่าประสิทธิภาพเชิงเวลาคือ
T(n) = a \; T\!\left(\frac{n}{b}\right) + f(n) \;\;\;\; \mbox{where} \;\; a \geq 1 \mbox{, } b > 1
กลวิธีการค้นแบบฟีโบนัชชีแบ่งการเรียกซ้ำออกเป็นสองส่วนจึงได้ว่าส่วนการเรียกซ้ำคือ T(n/2) และส่วนภาระจริงนั้นมีการทำงานเป็น \Theta\left( 1 \right) เมื่อรวมกันแล้วประสิทธิภาพเชิงเวลาของกลวิธีการค้นแบบฟีโบนัชชีมีค่าเป็น
T(n) = T(n/2) + \Theta\left( 1 \right) หรือคิดเป็น O(log(n))

หัวข้ออื่นๆที่เกี่ยวข้อง[แก้]

Golden section search

Binary search algorithm


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

  • David E. Ferguson, "Fibonaccian searching", Communications of the ACM, vol. 3 , is. 12, p. 648, Dec. 1960.
  • Manolis Lourakis, "Fibonaccian search in C". [1]. Retrieved January 18, 2007. Implements Ferguson's algorithm.
  • Donald E. Knuth, "The Art of Computer Programming (second edition)", vol. 3 , p. 418, Nov. 2003.
  • Fibonacci Search