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

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

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

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

## ขั้นตอนวิธี
ให้ F คือแถวลำดับของจำนวนฟีโบนัชชี ให้ *k* คือค่าของข้อมูลใดๆใน*F* *n*คือขนาดของแถวลำดับของข้อมูล ถ้า *n* เป็นเลขฟีโบนนัชชีให้ *F<sub>m</sub>=n* แต่ถ้า *n* ไม่ใช่จำนวนฟีโบนัชชีให้ *F<sub>m</sub>* เป็นจำนวนฟีโบนัชชีที่มากกว่า *n* แต่ใกล้เคียงที่สุด นิยามให้ค่าใน *F* เหมือนกับลำดับฟีโบนนัชชีโดยให้ *F<sub>k+2</sub>=F<sub>k+1</sub>+F<sub>k</sub>* โดยที่ *k≥0 ,F<sub>1</sub>=1* และ *F<sub>0</sub>=0*
: การหาตำแหน่งของข้อมูลที่สนใจสามารถหาตำแหน่งได้โดยทำตามขั้นตอนต่อไปนี้
# ให้ *k = m*
# ถ้า *k = 0* หมายความว่าไม่พบข้อมูลที่สนใจและให้เลิกทำ
# เปรียบเทียบข้อมูลในตำแหน่ง *F<sub>k</sub>* กับตำแหน่ง *F<sub>k-1</sub>*
# ถ้าตรงกับข้อมูลที่สนใจก็ให้จบการทำงาน
# ถ้าข้อมูลที่สนใจมีค่าน้อยกว่าข้อมูลในตำแหน่ง *F<sub>k-1</sub>* ให้ทิ้งข้อมูลตั้งแต่ตำแหน่ง *F<sub>k+1</sub>* ถึง n ให้ *k = k-1* แล้วกลับไปทำขั้นตอนที่สองอีกครั้ง
# ถ้าข้อมูลที่สนใจมีค่ามากกว่าข้อมูลในตำแหน่ง *F<sub>k-1</sub>* ให้ทิ้งข้อมูลตั้งแต่ตำแหน่ง 1 ถึง *F<sub>k-1</sub>* เรียงตัวเลขที่เหลือใหม่จาก 1 ถึง *F<sub>k-2</sub>* ให้ *k = k-2* แล้วกลับไปทำขั้นตอนที่สองใหม่อีกครั้ง

: นอกจากนี้ยังมีขั้นตอนวิธีอื่นๆอีกดังต่อไปนี้
ให้ *R* เป็นตารางที่เก็บสถิติขนาด *n* ช่อง ให้ ที่มีการเพิ่มขึ้นของลำดับ *K* โดยที่ *K<sub>1</sub> < K<sub>2</sub> < ... < K<sub>n</sub>* ขั้นตอนวิธีนี้จะหาข้อมูลที่ต้องการตามค่าของ *K* โดยจะสมมติว่า *N+1 = F<sub>k+1</sub>*ซึ่งหาก *N+1*ไม่ใช่จำนวนฟีโบนัชชีก็ให้ใช้หลักเกณฑ์การเปลี่ยนเป็นจำนวนฟีโบนัชชีเช่นเดียวกับขั้นตอนวิธีแรก โดยให้ *X* เป็นข้อมูลที่ต้องการจะหา
: **ขั้นที่หนึ่ง** ให้ *i ← F<sub>k</sub>,p ← F<sub>k-1</sub>,q ← F<sub>k-2</sub>* โดยจากขั้นตอนวิธีจะได้ว่า *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. กำหนดให้ *i = F<sub>13</sub>, p = F<sub>8</sub>, q = F<sub>5</sub>* (**ขั้นตอนที่หนึ่ง**)

2. เนื่องจาก *x < i* (**ขั้นตอนที่สอง**) จึงกำหนดค่าใหม่ให้ *i = F<sub>8</sub>, p = F<sub>5</sub> , q = F<sub>3</sub> * (**ขั้นตอนที่สาม**)

3. เนื่องจาก *x < i* (**ขั้นตอนที่สอง**) จึงกำหนดค่าใหม่ให้ *i = F<sub>5</sub>, p = F<sub>3</sub> , q = F<sub>2</sub> * (**ขั้นตอนที่สาม**)

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

## วิเคราะห์ประสิทธิภาพเชิงเวลา
: จากทฤษฎีสำคัญ () จะได้ว่าประสิทธิภาพเชิงเวลาคือ
: 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". http://www.ics.forth.gr/~lourakis/fibsrch/. 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

หมวดหมู่:ขั้นตอนวิธีการค้นหา