thuật tìm kiếm nhị phân giải một số bài toán tối ưu
Nguyễn Thanh Tùng
Có lẽ ai trong chúng ta cũng biết về thuật toán tìm kiếm nhị phân và sự hiệu quả của nó. Sử
dụng kỹ thuật tìm kiếm tương tự trong một số bài toán ta cũng đạt được kết quả rất khả
quan. Sau đây là một số bài toán như vậy.
I. Bài toán ví dụ.
Thông tin về mạng giao thông gồm n thành phố cho bởi mảng A kích thước n�n gồm các
phần tử a
ij
là một giá trị nguyên dương chỉ tải trọng của tuyến đường nối 2 thành phố i,j.
Nếu a
ij
=0 thì giữa i,j không có đường nối.
Tải trọng của một lộ trình từ thành phố s đến thành phố t (có thể đi qua một số thành phố
trung gian) là tải trọng của tuyến đường có tải trọng nhỏ nhất thuộc lộ trình.
Cho trước 2 thành phố s và t. Giả thiết luôn có lộ trình từ s đến t, hãy tìm một lộ trình từ s
đến t có tải trọng lớn nhất.
Thuật giải
Đặt k
min
= min {a
ij
: a
ij
>0}; k
max
= max {a
ij
: a
ij
>0}

until l>=r;
end;
Trong đó thủ tục Check (k) thực hiện:
1. Xây dựng đồ thị G(k) như đã mô tả ở trên.
2. Dùng thuật toán DFS để kiểm tra xem có đường đi từ s đến t không. Nếu có thì đặt Ok là
true, ngược lại thì Ok là false.
Chương trình mẫu
Để bạn đọc tiện theo dõi, tôi xin cung cấp chương trình mẫu của bài toán này. Để xử lí lỗi,
một số đoạn chương trình hơi phức tạp so với mẫu trên.
program weight;
const
inp = ’weight.inp’;
out = ’weight.out’;
max = 100;
type
mang1 = array[1..max] of integer;
mang2 = array[1..max, 1..max] of LongInt;
var
n,s,t,z : integer;
k,l,r : LongInt;
a : mang2;
đ,kq : mang1;
ok : boolean;
(*********************)
procedure nhap;
var
i,j : integer;
f : text;
begin
assign(f, inp);

end;
end;
(*********************)
procedure check;
begin
fillchar(đ,sizeof(đ),0);
đ[s] := -1;
dfs(s);
if đ[t] = 0 then ok := false
else ok := true;
end;
(*********************)
procedure search;
begin
repeat
k := (l+r) div 2;
check;
if ok then l := k
else r := k-1;
until (l=r) or (l = r-1);
if l = r-1 then begin
k := r;
check;
if ok then exit;
end;
k := l;
check;
end;
procedure trace;
var

nhap;
chbi;
xuly;
inkq;
end.
Nhận xét
a. Với kỹ thuật tìm kiếm nhị phân, giải thuật trên chỉ cần thực hiện cỡ log
2
(k
max
−k
min
)
lần kiểm tra (gọi thủ tục check). Do hạn chế a
ij
là nguyên dương ≤ maxLongInt nên k
max
− k
min
< 2
32
. Thủ tục check sử dụng thuật toán DFS có độ phức tạp tính toán là O(n
2
) nên
giải thuật có thời gian thực thi cỡ C.O(n
2
) với C < 32.
b. Ta không cần phải xây dựng G(k) một cách tường minh (tính hẳn thành ma trận kề)
mà chỉ cần thay biểu thức kiểm tra có cạnh (i,j) không bằng biểu thức a
ij

ij
. Hãy tìm một cách xếp mỗi người một việc sao cho tiền công lớn nhất cần trả trong cách
xếp việc đó là nhỏ nhất.
Thuật giải
Nếu bài toán yêu cầu là tìm cách xếp việc sao cho tổng tiền công phải trả là nhỏ nhất thì đó
là bài toán tìm cặp ghép đầy đủ trọng số cực tiểu. Tuy nhiên bài này là tìm cách xếp việc
sao cho tiền công lớn nhất là nhỏ nhất. Ta có ý tưởng như sau: tìm số k bé nhất sao cho tồn
tại một cách sắp xếp đủ n người, n việc và các yêu cầu về tiền công đều ≤ k.
Dễ thấy việc tìm kiếm đó có thể thực hiện bằng kĩ thuật tìm kiếm nhị phân, và việc kiểm
tra số k có thoả mãn không chính là việc kiểm tra đồ thị 2 phía G(k) có bộ ghép đầy đủ hay
không. Đồ thị đồ thị 2 phía G(k) được xác định như sau:
G(k) = (X,Y,E) Trong đó: X là tập n đỉnh ứng với n công nhân, Y là tập n đỉnh ứng với n
công việc. Với i thuộc X, j thuộc Y nếu a
ij
≥ k thì cho (i,j) thuộc E (2 đỉnh i,j chỉ được nối
với nhau nếu a
ij
≥k) .
Nếu k là số nhỏ nhất mà G(k) có bộ ghép đầy đủ thì bộ ghép đó chính là cách xếp việc cần
tìm.
Ta cũng có một số bài toán dạng tương tự:
Bài toán 2. Thời gian hoàn thành
Có n công nhân và n công việc. Nếu xếp công nhân i nếu làm việc j thì thời gian hoàn
thành là T
ij
. Hãy tìm một cách xếp mỗi người một việc sao tất cả các công việc hoàn thành
trong thời gian sớm nhất (các công việc được tiến hành song song).
Bài toán 3. Năng suất dây truyền
Dây truyền sản xuất có n vị trí và n công nhân (đều được đánh số từ 1..n). a
ij

ij
là khoảng cách giữa 2 cửa hàng i,j: d
ij
= |p
i
−p
j
|