Giải thuật tìm kiếm Fibonacci

Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”,
nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching”
không có ngữ nghĩa gì nhiều.

Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài
ra đây cũng là một nội dung được đề cập trong TAoCP – Vol 3.

Lịch sử

Thuật toán được để xuất bởi Devid E. Ferguson (CACM-1960, link).
Một số phát hiện liên quan, chủ yếu về nguồn gốc cây Fibonacci có thể tham khảo tại TAoCP – Vol 3 (Mục 6.2.1).

Thuật toán

Điểm thú vị của thuật toán này nằm ở chỗ thuật toán không sử dụng phép chia, nhưng vẫn đạt được
độ hiệu quả của binary search. Tuy nhiên, ưu điểm này thực sự có tác dụng
vào thời điểm thuật toán này được đề xuất (1960) khi mà các chép chia, hay
shift bit tốn nhiều chi phí hơn so với phép cộng trừ. Tuy nhiên, fibsearch còn được sử dụng khi tốn ưu thời gian tìm kiếm khi mà dữ liệu quá lớn không
thể đọc lên được toàn bộ lên RAM hoặc cache, khi đó thời gian đọc trên bộ
lưu trữ ngoại vi trở nên tốn kém ( link ).
Tuy nhiên mình nghĩ fibsearch sẽ là một câu hỏi phỏng vấn cực kì thú vị.

Thiết kế một thuật toán tìm kiếm nhị phân không sử dụng phép nhân, chia hoặc
dịch bit với độ phức tạp $\mathcal{O}(\lg N)$

Cài đặt

Phần dưới đây là giải thuật lấy từ TAoCP, mình nghĩ là cực kì dễ hiểu, tạm thời
mình chỉ trình bày mã giả. Có thể tham khảo phần cài đặt bằng C, trong phần
References. Một phiên bản cải tiến với kích thức mảng $N$ bất
kì sẽ được update sau.

[[code]]czo2MDQ6XCJJbnB1dDogbeG6o25nICRLXzEsIEtfMiwgLi4uLCBLX04kIMSRxrDhu6NjIHPhuq9wIHjhur9wIHbDoCBwaOG6p24gdOF7WyYqJl19u60gJEskIGPhuqduIHTDrG0uIEdp4bqjIHPhu60NCiROKzEgPSBGX3trKzF9LiBMxrB1IMO9IGluZGV4IGPhu6dhIG3huqNuZyBi4XtbJiomXX26r3QgxJHhuqd1IDEkDQoNClAxLiBbS2jhu59pIHThuqFvXSBpID0gRltrXSwgcCA9IEZbay0xXSwgcSA9IEZbay0yXQ0KUDIuIFtTe1smKiZdfW8gc8OhbmhdLg0KICAgIGlmIEtbaV0gJmx0OyBLOiBnbyB0byBQMy4NCiAgICBlbHNlIGlmIEtbaV0gJmd0OyBLOiBnbyB0byBQNC57WyYqJl19DQogICAgZWxzZTogcmV0dXJuIGk7DQpQMy4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gdHLDoWldDQogICAgaWYgcSA9IHtbJiomXX0wOiByZXR1cm4gLTENCiAgICBlbHNlOg0KICAgICAgICBpIC09IHENCiAgICAgICAgKHAsIHEpID0gKHEsIHAtcSkNCiAgICAgICAge1smKiZdfWdvIHRvIFAyDQpQNC4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gcGjhuqNpXQ0KICAgIGlmIHAgPSAxOiByZXR1cm4gLTF7WyYqJl19DQogICAgZWxzZToNCiAgICAgICAgaSArPSBxDQogICAgICAgIHAgLT0gcQ0KICAgICAgICBxIC09IHANCiAgICAgICAgZ28gdG8gUHtbJiomXX0yDQpcIjt7WyYqJl19[[/code]]

Bài tập

  • Thiết kế thuật toán cho trường hợp $N \geq 0$.
  • Thiết kế thuật toán với index bắt đầu bằng 0. Về mặt kĩ thuật chỉ có 1 thay đổi
    nhỏ trong code, nhưng cây Fibonacci sẽ tương đối khác.

Phân tích

Cây tìm kiếm Fibonacci với k=6. Source: TAoCP, Vol 3, P417.

Phần dưới đây là mô tả ngắn gọn cách mà thuật toán này thực thi. Khác với tìm
kiếm nhị phân chia các nhánh tìm kiếm thành các cây nhị phân, fibsearch thay
vào đó xây dựng cây Fibonacci. Cây Fibonacci bậc $k$ được định nghĩa là “cây” với
$F_{k+1}-1$ internal nodes (vòng tròn) và $F_{k+1}$ external nodes (hình vuông),1
cây Fibonacci được xây dựng như sau:

  1. $k=0$ hoặc $k=1$, cây chỉ có 1 external node là 0.
  2. $k \geq 2$, root là có giá trị $F_k$, cây con bên trái là cây fibonacci
    bậc $k-1$ và cây con bên phải là cây fibonacci bậc $k-2$ với tất cả các nodes
    tăng $F_k$ đơn vị.

Thuật toán fibsearch chính là việc xây dựng cây fibonacci bậc $k$ với $N=F_{k+1}$.

Trong Figure 1, cây có bậc $k=6$ (tương đương với tìm mảng có $N=12$ phần tử
($N+1=F_{k+1} = F_7 = 13$)), số internal nodes
$F_{k+1}-1=12$ và $F_{k+1}=13$ external nodes. Ngoài ra,
ta có thể thấy root = $F_6 = 8$, phần nhánh bên trái của 8 có
$F_6-1=7$ internal nodes, và bên phải gồm $F_5-1 = 4$ internal
nodes. Tiếp tục xuống các level thấp hơn là các giá trị $F$ nhỏ hơn và theo
đúng quy luật đã nêu. Nhìn hình ta có thể hình dung phần nào, với cách tiếp cận
chia để trị tương đồng với tìm kiếm nhị phân, tìm kiếm fibonaci “có thể”
có độ phức tạp tương tự.

Một chứng minh cụ thể và chi tiết hơn sẽ được cập nhật sau, kèm theo đó là mã
nguồn C++ của thuật toán.

Dạng tổng quát

Cả tìm kiếm nhị phân lẫn Fibonacci search thực ra cũng thuộc một dạng tổng quát
của một chiến lược chia để trị trong tìm kiếm chuỗi đã được sắp xếp.

Gọi $p$ và $q$ thỏa $p+q=1$, gọi $C(N)$ là số phép so sánh cần thực hiện của
giải thuật. Chiến lược ở đây đó là chia mảng thành 2 phần với số lượng phần
tử lần lượt là $pN$ và $qN$. Ta có dãy truy hồi số phép so sánh trong thuật toán:

$$ C(N) = 1 + pC(pN) + qC(qN) $$

Công thức này có dạng close form là $C(N) = \log_bN$ trong đó $b$ là hằng số
cần tìm. Dễ dàng thấy được với tìm kiếm nhị phần $p=q={1 \over 2}$, còn với
fibsearch thì $p={1 \over \phi}$ và $q= {1 \over \phi^2}$. Cụm $pC(pN)$ ở
đây có nghĩa là xác suất $p$ phần tử cần tìm nằm trong khoảng $pN$ phần tử
đã được chia, tương tự với $qC(qN)$.

[$b = p^{-p}q^{-q}$
nhưng hiện giờ vẫn chưa biết giải như thế nào. Đây là dạng divide-and-conquer
recurrence. Nếu sử dụng Akra-Bazzi method
thì ta chỉ mới tìm được $\Theta(1 + \ln N)$ của nó nhưng vẫn chưa xác định được $b$].

References

TODO

Mình cũng không biết nên dịch internal nodes với external nodes thế nào cho hợp (node trong và node ngoài?). ^

Khuyên dùng

 

Speak Your Mind

*