Về một thuật toán nổi tiếng

Không biết, nhiều người chơi game có biết rằng, ẩn chứa bên trong trò chơi xếp bi (lines game) nổi tiếng có chứa đựng một thuật toán cũng không kém phần nổi tiếng đối với những người yêu thích toán học hoặc các lập trình viên máy tính !? Đó là thuật toán tìm đường đi ngắn nhất…

Bài toán tìm đường đi ngắn nhất

Thuộc về lĩnh vực lý thuyết đồ thị (graph theory), bài toán tìm đường đi ngắn nhất (đơn) là bài toán tìm một đường đi giữa hai đỉnh của một đồ thị liên thông sao cho tổng các trọng số của các cạnh tạo nên đường đi đó là nhỏ nhất (Bài toán đường đi ngắn nhất giữa mọi cặp đỉnh là một bài toán tương tự, trong đó ta phải tìm các đường đi ngắn nhất cho mọi cặp đỉnh). Cách định nghĩa mang “dáng dấp” toán học có thể trình bày như sau:

Cho một đồ thị có trọng số, với V là tập đỉnh (vertex), E là tập cạnh (edge) và hàm trọng số có giá trị thực f : E → R. Cho trước một đỉnh v € (thuộc) V, tìm một đường đi P (path) từ v tới mỗi đỉnh v’ thuộc V sao cho:  ∑ f(p) (p € P) là nhỏ nhất trong tất cả các đường nối từ v tới v’ .

graph theory

Có 2 thuật toán quan trọng dùng để giải quyết bài toán tìm được đi ngắn nhất đó là giải thuật Bellman-Fordgiải thuật Dijkstra. Thuật toán Dijkstra có thời gian thực hiện tính toán nhanh hơn thuật toán Bellman-Ford, tuy nhiên, để thực hiện thuật toán Dijkstra, cần có thêm điều kiện là các trọng số phải không âm.

Ứng dụng trong thực tế

Bài toán tìm đường đi ngắn nhất giữa hai đỉnh trong một đồ thị liên thông được ứng dụng nhiều trong nhiều lĩnh vực: trò chơi máy tính (computer game), giao thông vận tải, thông tin viễn thông,…

Khi chơi trò chơi “Lines 98” nổi tiếng, ta sẽ thấy các viên bi xanh, đỏ, vàng,…di chuyển từ một vị trí chọn ban đầu (ô nguồn), chạy qua các ô vuông rỗng (chưa có viên bi nào ở đó) liền kề nhau theo một đường đi có vẻ đã được tính toán sẵn, và dừng lại ở một vị trí nào đó (ô đích). Nhìn trên 81 ô vuông của màn hình “Lines 98”, ta có thể vẽ ra được rất nhiều đường di chuyển như thế, nhưng đường đi mà viên bi đã đi qua chính là đường đi ngắn nhất.

Trong một thành phố, khi cần di chuyển từ một vị trí này đến một vị trí khác, bằng sự hỗ trợ của các phần mềm tìm kiếm đường đi tối ưu, chúng ta có thể có một lộ trình ngắn nhất (-> tiết kiệm được năng lượng thời gian – dĩ nhiên là trong một số điều kiện đã được tính toán sẵn như: vấn đề kẹt xe, đường một chiều, giới hạn tốc độ,…). Hay, rộng hơn, trong một vùng địa lý nào đó, có rất nhiều địa điểm (thành phố, thị trấn, làng mạc,…), được kết nối với nhau bằng các con đường, cần tìm một lộ trình để chở hàng hóa từ thành phố P, đến làng M, sao cho độ dài quãng đường là ngắn nhất,…

Có rất nhiều ứng dụng thực tiễn khác, mà ẩn chứa trong đó, người thiết kế đã áp dụng bài toán tìm đường đi ngắn nhất cùng những bài toán liên quan trong lý thuyết đồ thị và toán học rời rạc dưới sự hỗ trợ của các chương trình máy tính, để giải quyết một số vấn tối ưu hệ thống và mang lại lợi ích thiết thực cho người sử dụng. Có rất nhiều bài toán mang dáng dấp của bài toán tìm đường đi ngắn nhất được áp dụng rộng rãi trong các ngành như dịch vụ kinh doanh, dịch vụ vận tải, hàng không, xây dựng, dịch vụ GPS,…như: bài toán người đưa thư, bài toán người bán hàng,…

Thủ tục (mã nguồn ví dụ) tìm đường đi ngắn nhất

Hai thủ tục (hàm) này được viết trong Delphi, nhằm tìm đường đi ngắn nhất trong trò chơi Lines: từ một vị trí (ô chứa bi) sang một vị trí khác cần xếp bi vào đó.

const

cMax2 = 81; // Số đỉnh của đồ thị (ví dụ cho trò chơi Lines có 81 ô (9 cột, 9 dòng))

var

ArrayA: array[1..cMax2, 1..cMax2] of Byte;

ArrayQueue: array[1..cMax2] of Byte;

ArrayTrace: array[1..cMax2] of Byte;

ArrayFree: array[1..cMax2] of Byte;

ArrayRoad: array[1..cMax2] of Byte;

Solt: Integer;

procedure BFS(aPos: integer);

var u, j, bQ, eQ: integer;

begin

bQ := 1; eQ := 1;

ArrayQueue[eQ] := aPos;

ArrayFree[aPos] := Solt;

while bQ <= eQ do

begin

u := ArrayQueue[bQ];

bQ := bQ + 1;

for j := 1 to cMax2 do

if (ArrayA[u,j] = 1) and (ArrayFree[j] = 0) then

begin

eQ := eQ + 1;

ArrayQueue[eQ] := j;

ArrayFree[j] := Solt;

ArrayTrace[j] := u;

end;

end;

end;

function SeekingRoad(sPos, tPos: Integer; var aNumPoint: Integer): Boolean;

var j,k : integer;

vStr: String;

begin

for j := 1 to cMax2 do

begin

ArrayRoad[j] := 0;

ArrayTrace[j] := 0;

ArrayFree[j] := 0;

end;

Solt := 1;

BFS(sPos);

if ArrayTrace[tPos] = 0 then

begin

Result := False;

//    ShowMessage(‘Không có đường đi từ: ‘ + IntToStr(sPos) + ‘ đến ‘ + IntToStr(tPos));

end

else

begin

vStr := ‘Đường đi từ: ‘ + IntToStr(sPos) + ‘ đến ‘ + IntToStr(tPos) + ‘ là: ‘;

j := tPos;

ArrayRoad[1] := tPos;

k := 2;

vStr := vStr + IntToStr(tPos) + ‘ <== ‘;

while ArrayTrace[j] <> sPos do

begin

vStr := vStr + IntToStr(ArrayTrace[j]) + ‘ <== ‘;

j := ArrayTrace[j];

ArrayRoad[k] := j;

aNumPoint := k;

k := k+1;

end;

Result := True;

//    ShowMessage(vStr);

end;

end;

Lines Game iOS

Mai Thế Hùng

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s