Bàn thêm về thuật toán floyd-warshall

(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;