(Thầy Trần Thông Quế)
Để các bạn học sinh và sinh viên mới bắt đầu nghiên cứu hoặc học “Lý thuyết đồ thị” dễ nhận thức hơn về thuật toán này tôi sẽ nói chi tiết về nó và cung cấp cho các bạn một cài đặt trực quan.
1. Mục đích của Floyd-Warshall Algorithm (viết tắt là F-W Algo.) là tìm đường đi ngắn nhất giữa mọi cặp đỉnh trên đồ thị vô hướng không có chu kỳ âm dựa trên khái niệm “các đỉnh trung gian”.
2. Khái niệm trung tâm của F-W Algo. là “các đỉnh trung gian”.
3. Định nghĩa: Ký hiệu p=(x1, x2,…, xk)là đường đi từ x1 đến xk thì mọi đỉnh x2,…,xk gọi là các đỉnh trung gian trên đường đi p từ x1 đến xk.
4. Ý tưởng chính của F-W Algo. là: Cho V={1, 2,…, n} là tập đỉnh của đồ thị và tập đỉnh U={1, 2,…, k}. Xét cặp đỉnh i,j và mọi đường đi có thể từ i đến j với các đỉnh trung gian chỉ là các đỉnh thuộc tập U. Gọi p là đường đi ngắn nhất từ i đến j với các đỉnh trung gian thuộc U. Khi đó ta có hai tình huống sau:
a. Nếu k không là đỉnh trung gian trên đường đi từ i đến j thì đường đi ngắn nhất từ i đến j có các đỉnh trung gian là {1, 2,…, k-1} cũng là đường đi ngắn nhất từ i đến j với các đỉnh trung gian là {1, 2,…, k}
b. Nếu k là một đỉnh trung gian trên đường đi từ i đến j thì ta tách đường đi p thành hai đoạn con là p1 đi từ i đến k và p2 đi từ k đến j. Các đoạn đường con p1, p2 là các đường đi ngắn nhất với các đỉnh trung gian là các đỉnh {1, 2,…, k-1}. Từ đó suy ra cách xác định độ dài của đường đi từ i đến j nhờ hệ thức sau:
Trong đó dij là độ dài đường đi ngắn nhất từ i đến j; wij là trọng số trên đường đi ij.
Từ hệ thức trên ta thấy: để xác định độ dài đường đi ngắn nhất dij{1..k} từ i đến j qua các đỉnh
tập {1, 2,…, k} ta chỉ cần dựa vào dij{1..k-1} (đường đi ngắn nhất từ i đến j qua tập đỉnh 1… k-1).
5. Đến đây ta có thủ tục mô tả ý tưởng chính của F-W Algo:
Procedure F_W;
{Đoạn chương trình khởi trị cho các biến}
Begin
For i:=1 to n do
For j:=1 to n do
d[i,j]:=w[i,j]; {Trị ban đầu của biến lưu đường đi ngắn nhất là trọng sô w[i,j] }
p[i,j]:=i; {Ghi nhớ đỉnh i đứng trước j có đưưòng đi ngắn nhất đến j}
End;
{Đoạn chương trình mô tả F-W Algo.}
Begin
For k:=1 to n do
For i:=1 to n do
For j:=1 to n do
If di,j]>d[i,k]+d[j,k] Then
Begin
d[i,j:=d[i,k]+d[j,k];
p[i,j]>p[k,j]; {k là đỉnh trung gian trên đường ngắn nhất từ i đếnj}
End;
End;
Thuật toán Karatsuba
(Nguyễn Khắc Vượng)
Một trong những bài toán đầu tiên mà bất cứ học sinh Tin nào cũng phải
vượt qua, đó là thực hiện những phép toán với 2 số lớn sử dụng mảng.
Thực hiện cộng trừ hai số có n chữ số sẽ có độ phức tạp là O(n), nhân
hai số có n chữ số sẽ có độ phức tạp là O(n2). Vậy thì cài đặt phép nhân
như vậy đã là tối ưu chưa?
Lịch sử
Ngược dòng lịch sử, vào năm 1952, Andrey Kolmogorov đề xuất rằng thuật
toán nhân tay là tối ưu, và bất cứ một thuật toán khác đều cần đến Ω(n2)
phép toán cơ bản. Đến năm 1960, Kolmogorov tổ chức một hội thảo ở
Moscow và trình bày một loạt các bài toán về độ phức tạp của thuật toán,
trong đó có giả thuyết Ω(n2). Trong vòng 1 tuần, Anatolii Alexeevitch
Karatsuba, một sinh viên 23 tuổi đã tìm ra một thuật toán chia để trị
giải quyết bài toán nhân 2 số n-chữ số chỉ cần O(n(log3)) phép toán cơ
bản. Thuật toán này sau đó đã được công bố vào năm 1962, trong khi tác
giả của nó cũng không hề biết đến bài báo này.
Thuật toán
Xét phép tính (ax+b)(cx+d)=acx2+(ad+bc)x+bd. Thay vì 1 phép nhân 2 số
lớn, chúng ta đã thay thế nó bằng 4 phép nhân 2 số nhỏ hơn. Vậy nếu hai
số ban đầu là A và B có 2N chữ số, chúng ta sẽ chọn x=10k, thế thì a, b,
c, d đều chỉ có N chữ số. Nhân hai số A và B cần (2N)2=4N2 phép toán,
nhân mỗi cặp số nhỏ hơn cần N2 phép toán, như vậy thì nhanh hơn ở chỗ
nào? Liệu có cách nào giảm số phép nhân đi nữa không?
Xét tiếp (a+b)(c+d)=ac+ad+bc+bd. Vậy thì chỉ cần tính ac, bd, (a+b)(c+d)
là ta đã có đủ 3 hệ số. Khi đó, độ phức tạp sẽ là T(N)=3*T(N/2)+O(N),
nghĩa là O(N(log3)), xấp xỉ O(N1.58), quá là hiệu quả.
Các bước thực hiện
1. Nhập hai số X và Y gồm N chữ số
2. Tìm A, B, C, D sao cho X=A*10M+B; Y=C*10M+D với M=N/2
3. Tính A1=A*C; A3=B*D; A2=(A+B)*(C+D)-A1-A3;
4. Kết quả X*Y=A1*10(2M)+A2*10M+A3
Ví dụ: nhân 2 số 1234 và 5678, gồm 4 chữ số M=2; 1234=12*102+34; 5678=56*102+78; A=12, B=34, C=56, D=78.
A1=12*56=672; A3=34*78=2652; A2= (12+34) (56+78)-A1-A3=46*134-672-2652=2840.
1234*5678=672*104+2840*102+2652=7006652
Ở bước 1, khi ta lưu X và Y dưới dạng BigNum thì ở bước 2, tìm 4 số A,
B, C, D sẽ vô cùng đơn giản, vì A và C chỉ là lấy từ chữ số đầu đến chữ
số thứ M của X và Y, phần còn lại là B và D, bước 3 khi thực hiện phép
nhân, ta sẽ dùng đệ quy, áp dụng lại thuật toán Karatsuba cho đến khi A,
B, C, D còn ít hơn 121 chữ số thì nhân tay. Lí do sử dụng nhân tay cho
số có ít hơn 121 chữ số là vì khi đó, số phép cộng trừ và dời chỗ sẽ làm
cho thuật toán Karatsuba chạy kém hiệu quả hơn.
Cài đặt :
#include ...
#include ...
#include ...
#define MAX_DIGITS 60000
#define LIMIT 121
void normalMult(long *a, long *b, long *ret, long d) {
long i, j;
for(i = 0; i < 2 * d; i++) ret[i] = 0;
for(i = 0; i < d; i++) {
for(j = 0; j < d; j++) ret[i + j] += a[i] * b[j];
}
}
void
karatsubaMult(long *a, long *b, long *ret, long d) {
long i;
long *ar = &a[0];
long *al = &a[d/2];
long *br = &b[0];
long *bl = &b[d/2];
long *asum = &ret[d * 5];
long *bsum = &ret[d * 5 + d/2];
long *x1 = &ret[d * 0];
long *x2 = &ret[d * 1];
long *x3 = &ret[d * 2];
// khi d nhỏ thì nhân tay
if(d <= LIMIT) {
normalMult(a, b, ret, d);
return;
}
// tính tổng a+b và c+d
for(i = 0; i < d / 2; i++) {
asum[i] = al[i] + ar[i];
bsum[i] = bl[i] + br[i];
}
// tính 3 hệ số lưu vào cùng 1 mảng
karatsubaMult(ar, br, x1, d/2);
karatsubaMult(al, bl, x2, d/2);
karatsubaMult(asum, bsum, x3, d/2);
// kết hợp lại cho ra kết quả
for(i = 0; i < d; i++) x3[i] = x3[i] - x1[i] - x2[i];
for(i = 0; i < d; i++) ret[i + d/2] += x3[i];
}
void
doCarry(long *a, long d) {
long c;
long i;
c = 0;
for(i = 0; i < d; i++) {
a[i] += c;
if(a[i] < 0) {
c = -(-(a[i] + 1) / 10 + 1);
} else {
c = a[i] / 10;
}
a[i] -= c * 10;
}
}
void Input(long *a, long *d_a) {
char c;
long i;
*d_a = 0;
c = '0';
while(!(c == ' ' || c == EOF)) {
scanf("%c",&c);
a[*d_a] = c - '0';
++(*d_a);
}
// đảo lại mảng lưu số
for(i = 0; i * 2 < *d_a - 1; i++) {
c = a[i], a[i] = a[*d_a - i - 1], a[*d_a - i - 1] = c;
}
}
void Output(long *a, long d) {
long i;
for(i = d - 1; i > 0; i--) if(a[i] != 0) break;
for(; i >= 0; i--) printf("%d", a[i]);
}
int main() {
long a[MAX_DIGITS];
long b[MAX_DIGITS];
long r[6 * MAX_DIGITS];
// chỉ dùng 1 mảng lớn lưu kết quả cùng các giá trị tạm
// | ar*br | al*bl | asum*bsum | giá trị tạm | asum | bsum |
// d d d 3d d/2 d/2
long d_a;
long d_b;
long d;
long i;
clock_t start;
clock_t stop;
Input(a, &d_a);
Input(b, &d_b);
if(d_a < 0 || d_b < 0) {
printf("0 ");
exit(0);
return 0;
}
// cho tất cả các số còn lại của a và b là 0
i = (d_a > d_b) ? d_a : d_b;
for(d = 1; d < i; d *= 2);
for(i = d_a; i < d; i++) a[i] = 0;
for(i = d_b; i < d; i++) b[i] = 0;
//nhân dùng thuật toán karatsuba
start = clock(); // dùng để tính thời gian
karatsubaMult(a, b, r, d);
doCarry(r, 2 * d);
start = clock() - start;
Output(r, 2 * d);
printf(" %f ms ", 1000 * (double) start / CLOCKS_PER_SEC);
//nhân tay
start = clock();
normalMult(a, b, r, d);
doCarry(r, 2 * d);
start = clock() - start;
Output(r, 2 * d);
printf(" %f ms ", 1000 * (double) start / CLOCKS_PER_SEC);
}
Kết quả
Trên máy tính xách tay chạy CPU AMD X2 QL-62 2.0 Ghz, bộ nhớ RAM 4 GB,
đoạn code trên chạy trong Dev-C++ 4.9.9.2 được kết quả như sau:
Vậy thì với N tăng lên 30 lần, thuật toán Karatsuba đã vượt hoàn toàn
cách nhân tay thông thường tới 10 lần, nhân 2 số có 30000 chữ số chỉ mất
chưa đầy 0.3s, trong khi cách cài đặt này hoàn toàn chưa tối ưu.
Hướng tối ưu
Bạn đọc có thể tìm cách tối ưu cách cài đặt hơn nữa bằng cách đưa về hệ
cơ số 2, để có thể sử dụng phép SHL và SHR nhanh hơn. Để tăng được giới
hạn tính toán, chúng ta có thể dùng các mảng phụ để lưu biến tạm thay vì
lưu chung vào một mảng chính.
Mở rộng
Thay vì chia 2 số ban đầu thành 2 phần, ta có thể chia nó làm 3 phần để
được thuật toán Toom-3 với độ phức tạp O(n1.465), thậm chí làm k phần để
được thuật toán Toom-k với độ phức tạp O(ne), với e = log(2k − 1) /
log(k). Thế nhưng hằng số c của thuật toán Toom-k lại tăng nhanh một
cách khủng khiếp, cộng với việc nhân chia cộng trừ để tìm ra kết quả quá
rắc rối nên chúng ta không cần thiết phải dùng đến, trừ khi với những
phép nhân khá lớn. Tuy nhiên một thuật toán còn nhanh hơn nữa đã ra đời
vào năm 1971 mang tên Schönhage–Strassen. Độ phức tạp của thuật toán này
chỉ còn là O(NlogN), nhưng chỉ vượt mặt thuật toán Karatsuba khi 2 số
ban đầu có nhiều hơn 40000 chữ số. Cài đặt thuật toán này đòi hỏi phải
biết về Fast Fourier transforms (FFT)–biến đổi Fourier nhanh nên không
khả thi với trình độ học sinh. Vào năm 2007, một thuật toán nữa còn
nhanh hơn Schönhage-Strassen được tìm ra, đó là thuật toán Fürer với độ
phức tạp nhỏ hơn một chút và chỉ thực sự nhanh khi nhân 2 số vô cùng
lớn.
Quy hoạch động và ứng dụng
(School@net)
Đối với nhiều thuật toán nguyên lý “chia để trị” 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,
chúng ta chia nó thành nhiều bài toán con có thể được giải quyết độc
lập. Trong phương pháp quy hoạch động, việc thể hiện nguyên lý này được
đẩy đến cực độ: khi không biết chắc cần giải quyết bài toán con nào,
chúng ta giải quyết tất cả những bài toán con và lưu trữ những lời giải
này với mục đích sử dụng lại chúng theo một sự phối hợp nào đó để giải
quyết các bài toán tổng quát hơn.
Thuật ngữ “ quy hoạch” ở đây ngụ ý nói đến quá trình đưa bài toán ban
đầu về một dạng nào đó có thể áp dụng phương pháp này để giải. Đó là cả
một nghệ thuật, do vậy, bài viết này chỉ xem xét một vài ví dụ nhỏ để
qua đó giới thiệu cùng bạn đọc cách tiếp cận này.
Khi sử dụng phương pháp quy hoạch động để giải quyết vấn đề, ta có thể gặp phải hai khó khăn sau:
- Một là, không phải lúc nào sự kết hợp lời giải của bài toán con cũng cho ra lời giải bài toán lớn hơn
- Hai là, số lượng các bài toán con cần giải quyết và lưu trữ đáp án có
thể rất lớn, không thể chấp nhận được. Cho đến nay, chưa ai xác định
được một cách chính xác những bài nào có thể được giải quyết hiệu quả
bằng phương pháp quy hoạch động. Có những vấn đề quá phức tạp và khó
khăn mà xem ra không thể ứng dụng quy hoạch động để giải quyết được,
trong khi cũng có những bài toán quá đơn giản khiến cho việc sử dụng quy
hoạch động để giải quyết lại kém hiệu quả hơn so với dùng các thuạt
toán kinh điển.
Chúng ta sẽ cùng xem xét một vài ví dụ cụ thể sử dụng quy hoạch động dưới đây:
Ví dụ 1: Cho một xâu S <= 1000 kí tự; tìm palindrome dài nhất là xâu con của S ( Xâu con là một dãy các kí tự liên tiếp ).
(Palindrome hay còn gọi là xâu đối xứng, xâu đối xứng là tên gọi của
những xâu kí tự mà khi viết từ phải qua trái hay từ trái qua phải thì
xâu đó không thay đổi. VD: MADAM, IOI,... )
Cách 1: Dùng phương pháp quy hoạch động
Dùng mảng F[i, j] có ý nghĩa: F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j của S có/không là palindrome.
Ta có công thức là:
* F[i, i] = True
* F[i, j] = F[i+1, j-1]; ( nếu s[ i ] = s[ j ] )
* F[i, j] = False; ( nếu s[ i ] <> s[j] )
Đoạn chương trình như sau:
FillChar( F, sizeof(F), false );
for i := 1 to n do F[i, i] := True;
for k := 1 to (n-1) do
for i := 1 to (n-k) do
begin
j := i + k;
F[i, j] := ( F[i+1, j-1] ) and (s[ i ] = s[ j ] );
end;
Kết quả là : Max(j-i+1) <=j thỏa F[i,j] = True.
Với phương pháp này, ta thấy độ phức tạp thuật toán là 0(N2).
Lưu ý : Với N lớn, ta phải thay mảng 2 chiều F bằng 3 mảng 1 chiều và dùng thêm biến max lưu giá trị tối ưu.
Cách 2: Phương pháp duyệt có cận.
Ta xét từng vị trí i:
+ xem a[ i ] có phải là tâm của Palindrome có lẻ kí tự không?
( ví dụ Palindrome MADAM có tâm là kí tự D )
+ xem a[ i ] và a[ i+1 ] có phải là tâm của Palindrome có chẵn kí tự không?
( ví dụ Palindrome ABBA có tâm là 2 kí tự BB )
Với mỗi kí tự ta tìm palindrome dài nhất nhận nó là tâm, cập nhập lại
kết quả khi duyệt. Ta duyệt từ giữa ra để dùng kết quả hiện tại làm cận.
Và ta có chương trình sau:
procedure Pacondainhat;
var i, j : Longint ;
procedure Pacon( first, last : Longint );
var dd : Longint;
begin
if first = last then
begin dd := 1; dec(first); inc(last); end
else dd := 0;
repeat
if (first < 1) or (last > N) then break;
if s[ i ] = s[ j ] then
begin
dd := dd + 2;
first := first - 1;
last := last + 1;
end
else break;
until false;
if max < dd then max := dd;
end;
{ }
begin
i := n div 2;
j := n div 2 + 1;
max := 1;
while (i > max div 2) and (j <= N-max div 2) do
begin
if i > max div 2 then
begin
try( i, i );
try( i, i+1 );
end;
if j <= N - max div 2 then
begin
try( j, j );
try( j, j+1 );
end;
i := i - 1;
j := j + 1;
end;
end;
Cách làm này có độ phức tạp: max*(N-max). Vì vậy nó chạy nhanh hơn cách
quy hoạch động (QHĐ) trên, thời gian chậm nhất khi max = N/2 cũng chỉ
mất N2/4 nhanh gấp 4 lần cách dùng QHĐ. Nhờ vậy, chúng ta biết là: không
phải lúc nào QHĐ cũng chấp nhận được về mặt thời gian và không phải lúc
nào duyệt lúc nào cũng chậm.
Ví dụ 2: Chia một xâu thành ít nhất các Palindrome (độ dài <=1000).
Ví dụ này phức tạp hơn vídụ1, cách làm chúng ta vẫn sử dụng QHĐ.
Gọi F[ i ] là số palindrome ít nhất mà đoạn 1..j chia thành được.
Ta có công thức:
F[ i ] = max( F[ j ] + 1; "j < i thỏa mãn:đoạn j+1..i là palindrome)
Ta có đoạn chương trình sau:
F[0] := 0;
for i := 1 to n do
begin
for j := i-1 downto 0 do
if (đoạn j+1..i là palindrome) then F[ i ] := max( F[ i ], F[ j ]+1 );
end;
Hai vòng for ***g nhau mất O(N2), phần kiểm tra đoạn j+1..i là
palindrome hay không mất O(N), vậy độ phức tạp thuật toán là O(N3). Sẽ
không được khả thi nếu N = 1000. Để giảm độ phức tạp thuật toán, ta sử
dụng mảng L[i, j] có ý nghĩa tương tự như mảng F[i, j] ở Vídụ1. QHĐ lập
mảng L[i, j] mất N2. Tổng cộng là O(N2) vì mỗi lần kiểm tra chỉ mất
O(1).
Nhưng đến đây lại nảy sinh vấn đề: mảng L[i, j] không thể lưu được khi
N=1000 vì bộ nhớ của chúng ta có hạn. Một cách khắc phục là dùng xử lý
bít. Nhưng có cách đơn giản hơn là dùng hai mảng một chiều L[ i ] và C[ i
] có ý nghĩa:
* L[ i ] là độ dài lớn nhất của palindrome độ dài lẻ nhận s[ i ] làm tâm;
* C[ i ] là độ dài lớn nhất của palindrome độ dài chẵn nhận s[ i ] và s[ i+1 ] làm tâm;
L[ i ] và C[ i ] có thể tính được bằng cách 2 bài 2 trong O(N2). Phần kiểm tra ta viết lại như sau:
function is_palindrome(i, j : integer) : boolean;
var dd : integer;
begin
dd := j-i+1;
if dd then is_palindrome := (L[(i+j) div 2] >= n)
else is_palindrome := (C[(i+j) div 2] >= n)
end;
Vậy thuật toán của chúng ta có độ phức tạp tính toán là O(N2), chi phí bộ nhớ là O(N).
Ví dụ 3 : Cho một xâu, hỏi nó có bao nhiêu xâu con là palindrome; xâu
con ở đây gồm các kí tự không cần liên tiếp ( độ dài <= 120 ).
Ví Dụ: với xâu IOICAMP ta tìm thấy 9 xâu con.
Đây là một bài tập rất thú vị đơn giản nhưng ứng dụng nhiều trong thực tế. Phương pháp là dùng quy hoạch động.
Gọi F[i, j] là số palindrome là xâu con của đoạn i..j.
Ta có công thức :
* F[i, i] = 1;
* F[i, j] = F[i+1, j] + F[i, j-1] - F[i+1, j-1] + T;
Nếu s[ i ] = s[j] thì T = F[i+1, j-1] + 1;
Nếu s[ i ] <> s[j] thì T = 0;
Đoạn chương trình như sau :
procedure Pacon;
var k, i, j : integer;
begin
n := length(s);
for i := 1 to n do F[i, i] := 1;
for k := 1 to n do
for i := 1 to n-k do
begin
j := i+k;
F[i, j] := F[i, j-1] + F[i+1, j];
if s[ i ] = s[ j ] then F[i, j] := F[i, j] + 1
else F[i, j] := F[i, j] - F[i+1, j-1];
end;
end;
Đoạn chương trình trên chỉ có tính mô phỏng, muốn hoàn thiện bạn phải
cài đặt các phép tính cộng trừ số lớn vì kết quả có thể lên tới 2n-1.Độ
phức tạp của thuật toán là O(N2). Vì vậy, chúng ta hoàn toàn có thể làm
với N = 1000, khí đó cần rút gọn mảng F thành ba mảng một chiều.
Thuật toán Floyd ứng dụng cho bài toán tìm đường đi ngắn nhất
Đề bài: Cho một đồ thị có trọng số, với mọi cặp đỉnh x, y hãy tìm đường đi từ x tới y sao cho đoạn đường đi là ngắn nhất?
(Đường đi từ đỉnh x tới đỉnh y trong một đồ thị là một danh sách các
đỉnh mà hai đỉnh liên tiếp nhau trong danh sách đó được nối bởi một cạnh
của đồ thị.)
Bài toán tìm đường đi ngắn nhất cho tất cả các cặp đỉnh trong một đồ thị
có rất nhiều phương pháp để giải, một trong những phương pháp ứng dụng
tìm đường đi ngắn nhất phải kể đến là sử dụng thuật toán Floyd.
for y:=1 to V do
for x:= 1 to V do
if a[x,y]>0 then
for j:=1 to V do
if a[y,j]>0 then
if (a[x,j]=0) or (a[x,y]+a[y,j]<="" p="">
then a[x,j]:= a[x,y]+a[y,j];
Cấu trúc của thuật toán dùng phép logic “or” để theo dõi các đường đi,
chúng ta thêm một ít tính toán cho mỗi cạnh để xác định xem nó có là bộ
phận của đường đi ngắn nhất mới hay không: “ đường đi ngắn nhất từ nút x
tớinút j chỉ đi qua các nút có chỉ số nhỏ hơn y+1 thì hoặc là đường đi
ngắn nhất từ nút x tới nút j chỉ đi qua các nút có chỉ số nhỏ hơn y hoặc
nếu ngắn hơn thì nó là đường đi ngắn nhất từ x tới y cộng vớiđường đi
ngắn nhất từ y tới j”. Phần tử 0 trong ma trận tương ứng không có cạnh
nối hai đỉnh, chương trình có thể cải tiến đơn giản hơn (bỏ đi các phép
so sánh với 0) bằng cách dùng một biến để ký hiệu cạnh có trọng số vô
hạn.
*** Thuật toán Floyd cần O(V3) để giải bài toán đường đi ngắn nhất cho mỗi cặp đỉnh.
Các hình dưới đây minh hoạ chi tiết tính năng của thuật toán Floyd trên
ví dụ của chúng ta, chúng được bố trí chính xác để dễ so sánh. Các phần
tử 0 tương ứng với ý nghĩa không có đường đi, các phần tử khác 0 trong
thuật toán Floyd chứa độ dài của đường đi ngắn nhất. Đường đi ngắn nhất
cũng có thể được tìm ra bằng cách dùng phiên bản ma trận của mảng dad:
cho phần tử trong dòng x cột j nhận tên của đỉnh trước trong đường đi
ngắn nhất từ x tới j (trong đoạn chương trình trên chính là đỉnh y ở
vòng lặp trong).
(Mảng dad[1..V] chứa chỉ số đỉnh cha của mỗi đỉnh (thành phần có giá trị
0 dùng cho nút gốc của cây). Để tìm cha của đỉnh j, ta chỉ đơn giản gán
j:=dad[j] và để tìm gốc của cây có chứa đỉnh j, ta lặp lại thao tác này
cho tới khi gặp giá trị 0.)
Chúng ta cùng xét một ví dụ sử dụng thuật toán Floyd để tìm đường đi ngắn nhất trong đồ thị như sau:
Cho đồ thị có trọng số như hình dưới đây:
Với thuật toán Floyd thì trạng thái khởi động của thuật toán này cho ví dụ trên sẽ như sau:
Và dưới đây là trạng thái cuối cùng của thuật toán Floyd
Thuật toán đơn giản xử lý một tình huống trên bàn cờ !
Các trò chơi đối kháng giữa hai người chúng ta thường biết là những trò
chơi như cờ tướng, cờ vua, cờ caro…đã được hình thành từ lâu. Và những
người chơi luôn cố gắng tìm mọi cách để mình giành được phần thắng. Và
bạn có biết rằng có thể đoán trước người thắng thua, hay hoà ? Điều này
có nghĩa là nếu một trò chơi cho trước vị trí ban đầu thì kết quả tốt
nhất mà người chơi đầu tiên đạt được đã được biết từ trước (giả thiết cả
hai người chơi đều chơi tối ưu). Vấn đề là các trò chơi thường quá phức
tạp nên không có một ai có thể đảm bảo rằng mọi nước đi của mình là tối
ưu. Do vậy cho đến nay, chỉ một số lượng nhỏ bài toán đó đã được giải
quyết.
Có thể hiểu đơn giản các bài toán dạng này như dạng đồ thị :
Cho đồ thị có hướng G=(V,E) (Đồ thị G có tập đỉnh V, tập cạnh là E). Với mỗi đỉnh
Một trò chơi hai người được định nghĩa là một đồ thị có hướng G = (V, E)
trong đó mỗi trạng thái chơi tương ứng với một đỉnh của đồ thị, hàm
E(v) là qui tẵc chơi tức là E(v) chứa các đỉnh hay trạng thái chơi mà từ
v có thể đi đến. Hai người luân phiên nhau đi , ở thế chơi u người chơi
chỉ có thể đi sao cho nước v nhận được thoả mãn . Trò chơi kết thúc khi
đến lượt đấu mà không thể đi tiếp được nữa. (Thông thường thì người
không thể đi tiếp là người thua cuộc).
Và cách xử lý những bài dạng này cũng trở nên đơn giản hơn. Chúng ta cùng xét một ví dụ cụ thể như sau:
Bài toán: Hai người luân phiên nhau điều khiển một con tốt theo một số
con cho trước. Một người có thể di chuyển con tốt từ vị trí u đến v nếu
có một đường nối trực tiếp có hướng từ u đến v. Trò chơi kết thúc không
thể tiếp tục di chuyển. Người không thể tiếp tục đi là người thua cuộc.
Hỏi nếu cho trước vị trí ban đầu và danh sách các đường nối hỏi người đi
trước thắng hay người đi sau thắng hay cả hai hoà? Giả sử rằng hai
người này rất thông minh các bước đi của họ là tối ưu (tức cả hai người
không bao giờ đi các nước không có lợi cho mình).
Input:
- Dòng đầu ghi số N là số vị trí con tốt có thể đừng, và số M là số
đường đi (có hướng) mà con tốt có thể đi (1≤ N ≤ 200, 1 ≤ M ≤ N*(N-1)).
- Dòng thứ hai ghi u là trạng thái bắt đầu.
- M dòng tiếp theo mỗi dòng ghi hai số u, v mô tả một đường đi từ u đến v.
Output:
- Ghi một số duy nhất 1, 2, hoặc 0. 1 nghĩa là người 1 thắng, 2 là người hai thắng, 0 là hoà.
Nhận xét:
- Những vị trí không có đường ra thì chắc chắn sẽ thua.
- Những vị trí nào có một đường ra nối với vị trí chắc chắn thua thì chắc chắn thắng.
- Những vị trí nào tất đường ra nối với các vị trí chắc chắn thắng thì chắc chắn thua.
- Những vị trí nào mà trạng thái thắng thua không thể xác định thì là vị trí hoà.
- Bài toán có trạng thái hoà: VD: có các đường nối 1 → 2, 2 → 3, 3 → 1, 1 → 4, 4 → 5.Các vị trí 1,2,3 sẽ hòa, 5 thua, 4 thắng.
Thuật toán:
- Lúc đầu coi tất cả các vị trí v đều hoà gán giá trị đỉnh F[v] = 0. Tìm
các vị trí không có đường ra thì gán lại F[v] = 2 (tức là nếu người
chơi ở vị trí này sẽ thua).
- Khi thay trạng thái một vị trí từ hoà sang thắng hoặc thua thì kiểm
tra các vị trí có đường đi đến nó: Những vị trí u nào có một đường ra
nối với vị trí v chắc chắn thua (F[v] = 2) sẽ thì chắc chắn thắng (thay F
= 1); Những vị trí u nào tất đường ra nối với các vị trí v (F[v] = 1)
chắc chắn thắng thì chắc chắn thua (thay F = 2).
- Quá trình này ngừng khi không có sự chuyển trạng nào nữa.
Chương trình mô tả thuật toán:
procedure gan_nhan (u: byte);
var td, v : byte;
begin
td := 0;
if t then td := 1 else // t là trạng thái người chơi ở vị trí chắc thắng
if (vị trí không có đường ra, hoặc chắc chắn thua) then td := 2;
F := td;
if td <> 0 then
for v := 1 to N do
if F[v] = 0 then
if C[v, u] then gan_nhan (td);
End;
procedure Main;
var u : Integer;
Begin
Fillchar (F, sizeof (F), 0);
for u := 1 to N do
if Khong_Co_Canh_Ra (u) then Gan_nhan(u);
end;
0 comments: