Bài toán tìm kiếm và các phương pháp tìm kiếm cơ bản
Thu Hương
I. Bài toán:
Tìm kiếm luôn là thao tác nền móng cho rất nhiều tác vụ tính toán. Tìm kiếm nghĩa là tìm
một hay nhiều mẩu thông tin đã được lưu trữ. Thông thường, thông tin được chia thành các
mẩu tin (record), mỗi mẩu tin đều có một KHÓA (key) dùng cho việc tìm kiếm. Ta sẽ luôn
có một khoá cho trước giống như khoá của các mẩu tin mà ta cần tìm. Mỗi mẩu tin được
tìm thấy sẽ chứa toàn bộ thông tin để cung cấp cho một quá trình xử lý nào đó.
Việc tìm kiếm được áp dụng rất đa dạng và rộng rãi. Một Ngân hàng nắm giữ tất cả thông
tin của rất nhiều tài khoản khách hàng và cần tìm kiếm để kiểm tra các biến động. Một
hãng Bảo hiểm hay một hệ thống trợ giúp bán vé xe, vé máy bay….Việc tìm kiếm thông
tin để đáp ứng việc xắp đặt ghế và các yêu cầu tương tự như vậy là thực sự cần thiết.
Thuật ngữ thường được dùng trong việc mô tả cấu trúc dữ liệu của việc tìm kiếm là TỪ
ĐIỂN và BẢNG KÝ HIỆU. Một ví dụ điển hình như ta muốn xây dựng hệ thống tra từ
điển Tiếng Anh chẳng hạn. Ở đây, “khoá” là từ và “mẩu tin” là diễn giải cho từ đó, mỗi
mẩu tin chứa định nghĩa, cách phát âm và các thông tin khác. BẢNG KÝ HIỆU chính là từ
điển cho chương trình và các mẩu tin chứa thông tin mô tả đối tượng được đặt tên.
II. Hướng giải quyết bài toán tìm kiếm:
Trong tìm kiếm chúng ta thấy có rất nhiều trương trình được dùng thường xuyên và rộng
rãi. Vì vậy sẽ rất có ích khi nghiên cứu chi tiết nhiều phương pháp khác nhau.
Cách tốt nhất để suy nghĩ các thuật toán tìm kiếm là đưa ra các thao tác tổng quát được rút
ra từ các cài đặt cụ thể, sao cho các cài đặt khác nhau có thể được thay thế dễ dàng. Các
thao tác đó gồm:
- Khởi tạo cấu trúc dữ liệu (INITIALIZE)
- Tìm kiếm một hay nhiều mẩu tin có khoá đã cho (SEARCH)
- Chèn thêm một mẩu tin mới ( INSERT)
- Nối lại từ điển để tạo thành một từ điển lớn hơn.(JOIN)
- Sắp xếp từ điển; xuất ra tất các mẩu tin theo thứ tự được sắp xếp (SORT)
Trong một vài trường hợp, các thao tác này được tổ hợp thành một thao tác phức tạp hơn.
Ví dụ như thao tác SEARCH_INSERT (tìm kiếm và chèn). Thao tác này thường được
dùng trong các trường hợp các mẩu tin với khoá bằng nhau không được phép lưu trữ trong

function seqinsert(v : integer): integer;
begin
N:= N + 1;
A[N].key:= v;
seqinsert := N;
end
end;
Đoạn mã trên xử lý các mẩu tin có các khoá (key) và “thông tin đi kèm” có giá trị nguyên
(infor). Nhiều ứng dụng cần mở rộng các chương trình để làm việc các mẩu tin và khoá
phức tạp hơn, nhưng điều này sẽ không làm thay đổi nhiều các thuật toán.
Ví dụ: trường Infor có thể thay đổi thành con trỏ đến một cấu trúc mẩu tin phức tạp.
Trường hợp như vậy, trường infor có thể có thể xem như một chỉ danh duy nhất của mẩu
tin để phân biệt những mẩu tin có khoá bằng nhau.Thủ tục seqsearch có hai đối số: một là
giá trị khoá (v), một là chỉ số của mảng (biến x). Chỉ số x này dùng để xử lý trường hợp
nhiều mẩu tin có cùng một giá trị khoá. Bằng cách thực hiện liên tục m:= seqsearch(v, m)
khởi đầu với m:= 0; chúng ta có thể cho m lần lượt chỉ số của các mẩu tin có khoá bằng v.
Một mẩu tin đặc biệt có khoá là khoá đang tìm được thêm vào; nó bảo đảm rằng quá trình
tìm kiếm sẽ kết thúc và cũng làm đơn giản hơn phép kiểm tra trong vòng lặp. Sau khi vòng
lặp dừng, nếu chỉ số trả về nhỏ hơn hay bằng N thì đó chính là chỉ số của mẩu tin tìm
được. Nếu ngược lại thì trong bảng đã cho không có mẩu tin có giá trị khoá muốn tìm. Kỹ
thuật này giống như kỹ thuật dùng một mẩu tin chứa giá trị khoá nhỏ nhất hay lớn nhất để
làm đơn giản các vòng lặp của các thuật toán trong các chương trình sắp xếp.
Ta có thể rút ra một kết luận cho thuật toán tìm kiếm tuần tự như sau:
Tìm kiếm tuần tự (cài đặt mảng) sử dụng đúng (N +1) phép so sánh cho một lần tìm kiếm
không thành công và trung bình có khoảng N/2 phép toán so sánh cho một lần tìm kiếm
thành công.
Trường hợp tìm kiếm thành công, điều này là hiển nhiên được thấy ngay trong đoạn
chương trình trên.
Trường hợp tìm kiếm không thành công, chúng ta giả sử rằng mỗi mẩu tin có khả năng tìm
thấy là như nhau, thì số trung bình của số lần so sánh sẽ là:

end;
end;
Với một xâu được sắp xếp, một lần tìm kiếm có thể kết thúc không thành công khi một
mẩu tin có khoá lớn khoá đang tìm kiếm được tìm thấy. Do đó, về mặt trung bình, chỉ
khoảng một nửa các mẩu tin (không phải là tất cả) cần được kiểm tra cho một lần tìm kiếm
không thành công. Thứ tự sắp xếp được duy trì dễ dàng tại vị trí mà việc tìm kiếm kết thúc
không thành công. Ta xét kỹ thuật sau:
function listsearch(v : integer; t: lienket): lienket;
begin
z↑.key: = v;
while (t↑.next↑.key < v) do
new(x);
x↑.next:= t↑.next;
t↑.next:= x;
x↑.key:= v;
listsearch:= x;
end;
Như chúng ta đã biết, đối với các xâu liên kết, có thể một nút dẫn đầu (dau) và một nút kết
thúc z để làm đơn giản chương trình. Vì vậy, lệnh listsearch(v, dau) sẽ đặt một nút mới với
khoá v vào trong xâu được trỏ tới bởi trường (next) của (dau). Các lần gọi listsearch kế tiếp
dùng các xâu trả về của lần trước đó để đưa ra các mẩu tin có các khoá bằng nhau. Nút kết
thúc (z) dùng cho trường hợp thành không công, nghĩa là nếu listsearch trả về z thì sự tìm
kiếm không thành công.
Vậy tìm kiếm tuần tự (cài đặt bằng xâu có thứ tự) sử dụng trung bình khoảng N/2 phép so
sánh cho cả hai trường hợp tìm kiếm thành công và không thành công.
Xét trường hợp ta tìm kiếm thành công với kỹ thuật trên: điều này ta có thể thấy trực tiếp
từ đoạn code trên
Trường hợp không thành công khi tìm kiếm:
Giả sử rằng khả năng tìm kết thúc ở mỗi phần tử trong xâu và nút z là như nhau thì số
trung bình của các phép so sánh sẽ là:

pháp này. Ta có thể gọi Đệ quy một lần mà có thể đưa ra thuật toán dùng phương pháp lặp.
Ta hãy cùng xét hàm dưới đây để thấy được thuật toán Nhị Phân thể sẽ thực hiện như thế
nào( giả sử rằng: mảng A đã được sắp xếp tăng theo thứ tự Khoá):
function TKnhiphan(k: integer): integer;
var x, l , r : integer;
begin
l:=1;
r:= N;
repeat
x:= (l + r ) div 2;
if (kA[x].key) then
r:= x - 1;
else
r:= x + 1;
until (k = A[x].k) or (l>r);
if (k= A[x].key) then
TKnhiphan:= x;
else TKnhiphan:= N +1;
end;
Như chúng ta thấy trên hàm, thuật toán này đã sử dụng các con trỏ l và r để đánh dấu tập
tin con hiện đang làm việc. Mỗi khi vòng lặp thực hiện, biến x nhận giá trị điểm giữa của
đoạn hiện hành. Sẽ có ba khả năng sau xảy ra:
- Vòng lặp kết thúc thành công