KHOA CÔNG NGHỆ THÔNG TIN

BÀI TẬP LỚN MÔN HỌC
PHÂN TÍCH ĐÁNH GIÁ THUẬT TOÁN

Đề 27: Thuật toán tìm kiếm. Một xâu gọi là xâu đối xứng nếu đem đảo ngược xâu
đó ta lại nhận được xâu ban đầu. Cho xâu S, hãy tìm số kí tự ít nhất cần thêm
vào S để S trở thành xâu đối xứng.Giả thiết các thao tác chèn kí tự tốn kém thời
gian không đáng kể.

Giáo viên hướng dẫn: PGS.TS. Đào Thanh Tĩnh
Học viên thực hiện: Hồ Trung Dũng
Lớp: Hệ thống thông tin K25B

Hà nội, 5/2014


PHẦN 1: THUẬT TOÁN TÌM KIẾM
I. Bài toán tìm kiếm
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. Bài toán tìm kiếm thông thường xảy ra trong hai tình huống:
+ Dữ liệu được coi là ngẫu nhiên

Chúng ta đã xét phương pháp tìm kiếm tuần tự, cách này đơn giản trong quá trình
cài đặt. Song , hạn chế của phương pháp tuần tự là thời gian tìm kiếm sẽ lâu trong
trường hợp tập hợp tổng số mẩu tin lớn. Để khắc phục hạn chế này, ta có phương pháp
tìm kiếm nhị phân. Nếu tập hợp các mẩu tin lớn thì tổng số thời gian tìm kiếm sẽ được
rút ngắn bằng cách dùng một thủ tục tìm kiếm dựa trên sự ứng dụng sơ đồ “chia - để trị”.
a.
b.
-

Phạm vi áp dụng: Tìm kiếm trên dữ liệu đã được sắp xếp.
Ý tưởng: Thay vì tìm kiếm tuần tự ta sé tìm kiếm phần tử theo vị trí ở giữa dãy.
Nếu chỉ số phải bé hơn chỉ số trái thì kết thúc.
Nếu giá trị tìm kiếm trùng với giá trị ở giữa thì kết thúc
Nếu bé hơn thì tìm kiếm từ đầu đến phần tử trước phần tử hiển tại
Nếu lớn hơn phần tử ở giữa thì tìm kiếm từ phần tử sau phần tử ở giữa đến phần tử ở

cuối dãy.
c. Thuật toán:
Input: A[0..N-1], x cần tìm kiếm
Output: thông tin về vị trí

"int" BinarySearch (Array a, int x) {
int left = 0, right, mid; right = a.n - 1;
3

3


while (left
là việc tìm phương án tối ưu cho bài toán đó có thể đưa về tìm phương án tối ưu của
một số hữu hạn các bài toán con. Đối với nhiều thuật toán đệ quy chúng ta đã tìm
hiểu, nguyên lý chia để trị (divide and conquer) thường đóng vai trò chủ đạo trong
việc thiết kế thuật toán. Để giải quyết một bài toán lớn, ta chia nó làm nhiều bài toán
con cùng dạng với nó để có thể giải quyết độc lập.
Quy hoạch động thường dùng một trong hai cách tiếp cận:
4

4


top-down (Từ trên xuống): Bài toán được chia thành các bài toán con, các bài

•

toán con này được giải và lời giải được ghi nhớ để phòng trường hợp cần dùng lại
chúng. Đây là đệ quy và lưu trữ được kết hợp với nhau.
bottom-up (Từ dưới lên): Tất cả các bài toán con có thể cần đến đều được giải

•

trước, sau đó được dùng để xây dựng lời giải cho các bài toán lớn hơn. Cách tiếp cận
này hơi tốt hơn về không gian bộ nhớ dùng cho ngăn xếp và số lời gọi hàm. Tuy
nhiên, đôi khi việc xác định tất cả các bài toán con cần thiết cho việc giải quyết bài
toán cho trước không được trực giác lắm.
Một số bài toán ứng dụng phương pháp quy hoạch động như:
+ Bài toán tính số tổ hợp
+ Bài toán cái balo
+ Bài toán tìm đường đi của người giao hàng
2. Tìm kiếm dựa vào đệ quy

chia một bài toán lớn và khó (tìm kiếm khắp không gian) thành các bài toán nhỏ và
đơn giản hơn (phát sinh các con của một trạng thái) và áp dụng chiến lược đệ quy cho
từng bài toán nhỏ đó. Quá trình cứ tiếp tục như vậy cho đến khi phát hiện được đích
hoặc hết không gian.
Function Depthsearch;
Begin
If open rỗng then trả lời (thất bại);
Trạng thái hiện hành := phần tử đầu tiên của open;
If trạng thái hiện hành là trạng thái đích
then trả lời (thành công)
Else
begin
Open := open - phần tử đầu tiên của open;
Closed := closed + trạng thái hiện hành;
For mỗi trạng thái con của trạng thái hiện hành do If chưa có
trong closed hay open
then bổ sung con đó vào đầu danh sách open
end;
Tìm kiếm sâu;
6

6


End;

PHẦN 2: ỨNG DỤNG THUẬT TOÁN TÌM KIẾM
CHO XÂU S, HÃY TÌM SỐ KÝ TỰ ÍT NHẤT CẦN THÊM
VÀO S ĐỂ S TRỞ THÀNH XÂU ĐỐI XỨNG
I.

L(i,j)=L(i,j-1)+1 ( +1 vào là do có 1 kí tự vừa được thêm vào)
Vậy ta có công thức truy hồi trong trường hợp 2 kí tự khác nhau là:
L(i,j)=max(L(i+1,j), L(i,j-1)) + 1 (với hàm max(a,b) sẽ trả về giá trị lớn hơn
trong 2 giá trị a,b)
Với cách giải thuật sử dụng đệ quy có nhớ trên chi phí sẽ la O().
2. Sử dụng quy hoạch động
Một cách tiếp cận khác của bài toán là sử dụng quy hoạch động để thực hiện.
Thông qua việc tìm xâu con chung dài nhất
Nếu ta gọi P là xâu đảo của S
8

8


T là xâu con chung dài nhất của S và P
Khi đó các ký tự của S không thuộc T cũng là các ký tự cần thêm vào để S trở
thành xâu đối xứng.
Vậy số ký tự ít nhất cần thêm vào sẽ là n-k với k là đọ dài của T
Ví dụ: Cho xâu S:edbabcd - >Xâu đảo của S sẽ là : dcbabde
Xâu con chung xài nhất: T: dbabd
Vậy e và c sẽ là 2 ký tự cần thêm vào để S thành xâu đối xứng.

Với việc sử dụng quy hoạch động để giải quyết bài toán, chúng ta phải giải quyết
bài toán con – tìm xâu con chung dài nhất. Khi đó bài toán sẽ đưa về giải quyết vấn
đề:
Cho hai dãy X = <x1,x2,…,xm> và Y = <y1,y2,…,yn>. Cần tìm dãy con chung dài
nhất của hai dãy X và Y.Thuật toán trực tiếp để giải bài toán đặt ra là: Duy ệt tất
cả các dãy con của dãy X và kiểm tra xem mỗi dãy như vậy có là dãy con của dãy
Y, và giữ lại dãy con dài nhất. Mỗi dãy con của X tương ứng với dãy chỉ số là tập con k phần tử của tập chỉ số {1, 2, …, m}, vì thế có tất cả 2m dãy con

s1,s2:string;
n,m,i,j:integer;
d:array[0..1000,0..1000] of integer;

function max(a,b:integer):integer;
begin
if a>b then exit(a);
exit(b);
end;
begin
assign(f,'doixung.in'); reset(f); readln(f,s1); close(f);
s2:='';
for i:=length(s1) downto 1 do (* làm 1 chuỗi đảo ngược của chuỗi đã cho ban đầu*)
s2:=s2+s1[i];
n:=length(s1); m:=length(s2);
for i:=1 to n do d[i,0]:=0;
for j:=1 to m do d[0,j]:=0;
for i:=1 to n do
for j:=1 to n do
if s1[i]=s2[j] then
d[i,j]:=d[i,j-1]+1
else
d[i,j]:=max(d[i,j-1],d[i-1,j]);
assign(f,’doixung.out'); rewrite(f); writeln(f,n-d[n,m]);

10

10



11

11