Bài toán người du lịch

Một nguời du lịch muốn tham quan n thành phố T1,.., Tn . Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua đúng 1 lần rối quay trở lại thành phố xuất phát.

Gọi Cij là chi phí đi từ thành phố Ti đến Tj . Hãy tìm một hành trình thỏa yêu

cầu bài toán sao cho chi phí là nhỏ nhất.

Đây là bài toán tìm chu trình có trọng số nhỏ nhất trong một đơn đồ thị có hướng có trọng số. Thuật toán tham lam cho bài toán là chọn thành phố có chi phí nhỏ nhất tính từ thành phố hiện thời đến các thành phố chưa qua

Input C= (Cij)

output TOUR // Hành trình tối ưu,

Mô tả :

COST;//Chi phí tương ứng

TOUR := 0; COST := 0; v := u; // Khởi tạo

Mọi k := 1 -> n ://Thăm tất cả các thành phố

// Chọn cạnh kề )

- Chọn <v, w> là đoạn nối 2 thành phố có chi phí nhỏ nhất tính từ thành phố v đến các thành phố chưa qua.

- TOUR := TOUR + <v, w>; //Cập nhật lời giải

- COST := COST + Cvw ; //Cập nhật chi phí

// Chuyến đi hoàn thành TOUR := TOUR + <v, u>; COST := COST + C_vw

Minh họa:

Thao tác chọn đỉnh thích hợp trong n đỉnh được tổ chức bằng một vòng lặp

để duyệt. Nên chi phí cho thuật toán xác định bởi 2 vòng lặp lồng nhau, nên

T(n) € O (n²).

int GTS (mat a, int n, int TOUR[max], int Ddau)

{

int v, //Dinh dang xet

k, //Duyet qua n dinh de chon

w; //Dinh duoc chon trong moi buoc

int mini; //Chon min cac canh(cung) trong moi buoc int COST; //Trong so nho nhat cua chu trinh

int daxet[max]; //Danh dau cac dinh da duoc su dung

for(k = 1; k <= n; k++)

daxet[k] = 0; //Chua dinh nao duoc xet

COST = 0; //Luc dau, gia tri COST == 0

int i; // Bien dem, dem tim du n dinh thi dung

v = Ddau; //Chon dinh xuat phat la 1

i = 1;

TOUR[i] = v; //Dua v vao chu trinh daxet[v] = 1; //Dinh v da duoc xet

while(i < n)

{

mini = VC;

for (k = 1; k <= n; k++)

if(!daxet[k])

if(mini > a[v][k])

{

mini = a[v][k];

w = k;

}

v = w;

i++;

TOUR[i] = v;

daxet[v] = 1;

COST += mini;

}

COST += a[v][Ddau];

return COST;

}