Đề tài số 5 1 GVHD: Lư Nhật Vinh
MỤC LỤC
BÀI TOÁN GTS1
I. Mô tả bài toán
Một người du lịch dự định tham quan quốc gia ABC. Anh ta dự kiến sẽ đến
N
thành phố. Chi phí để di chuyển từ thành phố i tới thành phố j là M[i][j]. Bạn
hãy
tum một lộ trunh để người du lịch này có thể xuất phát từ thành phố (từ skn
bay
chẳng hạn) đi đến các thành phố cần tham quan và quay về địa điểm ban
đầu, mỗi điểm tham quan chỉ qua 1 lần, sao cho chi phí là ít nhất.
Ví dụ:
Tìm Hiểu Và Cài Đặt Thuật Toán GTS
Đề tài số5 2 GVHD:Lư Nhật Vinh
C
∞
1 2 7 5
1
∞
4 4 3
= 2
4
∞
1 2
7 4 1
∞
3
5 3 2 3
∞
II. Ma trận hóa dữ liệu đồ

N
ế
u

t
ồ
n

t
ạ
i

đ
ư
ờ
n
g

đ
i

g
i
ữ
a

i
và j thì
M[i][j]
= x (x

Gán TOUR: = TOUR
+ (v, u);
COST: = COST
+ C(v, u); Chấm dứt
thuật giải.
IV. Cấu trúc dữ liệu đề nghị
int[MAX,MAX]
Matrix;
char[MAX] Visited;
char[MAX] TOUR;
int COST;
int nCities;
Diễn giải
 Matrix: ma trận chi phí di chuyển giữa các thành phố,
M[i][j]: chi phí di chuyển từ thành phố i đến thành phố j.
Visited: mảng cho biết tunh trạng thăm viếng của các thành phố
o Visited[i] = 0: thành phố thứ i chưa được tham quan
o Visited[i] = 1: thành phố thứ i đã được
tham quan
 TOUR: mảng chứa chu trunh tham quan
 COST: chi phí tham quan
 nCities: số thành phố
V. Cài đặt
Void KhoiTaoMaTran(char *filename)
{
Đọc ma trận chi phí từ file
}
Void
GTS1(int u)
{

I. Giải thuật GTS2
Giải thuật này sẽ tạo ra các lịch trình từ P thành phố xuất phát riêng biệt
cho bài
toán tìm chu trinh đi qua N thành phố (GTS1) như đã nói ở trên,
với 1 ≤ P ≤ N.
Khi đó P chu trình được tạo ra một cách tuần tự và chỉ có
chu trình tốt nhất đã tìm thấy được giữ lại mà thôi.
 Bước 1: Khởi tạo K:=0; BEST:= , COST:= ∞;
 Bước 2: Lần lượt tạo ra P chu trình với
đỉnh thứ K
Call(GTS1(v
K
)).
 Bước 3: Cập nhật chu trunh tốt nhất
Nếu C (K) < COST thì gán BEST:= T(K); (chu trunh xuất
phát từ K)
COST:= C(K);
 Bước 4: Nếu K ≤ P, lặp lại bước 2.
Ngược lại, chấm dứt thuật giải.
II. Cấu trúc dữ liệu đề nghị
int[MAX,MAX]
Matrix;
int nCities;
char[MAX]
BEST;
int COST;
Diễn giải
 Matrix: ma trận chi phí di chuyển giữa các thành phố, M[i][j]:
chi phí di chuyển từ thành phố i đến thành phố j.
 nCities: số thành phố

Chọn w = 5// đỉnh được chọn vì có chi
phí thấp nhất
TOUR={1,5}
COS
T =
0 +2
V=5
VI. Code cài đặt
CÀI ĐẶT THUẬT TOÁN GTS TRÊN C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.IO;
namespace DemoGTS
{
public class GTS
{
int MAX= 10;
int[,] a;//khai báo ma trận a
int n,kt=0;//kb số pt n và biến lấy phần tử cuối cùng của dường đi
public int cost = 0;//luu trọng số của duong92 đi
string st="";//khai báo chuỗi để lưu chuỗi đọc dk
int[] ChuaXet;//mảng chưa xét
int Best = 10000000;//giá trị đường đi tốt nhất
string[] Luu;//lưu đường đi tốt nhất
public string[] LuuVet;//mảng để lưu dường đi
int dem = 0;//sử dụng làm số phần tử của mảng LuuVet
public void DocFile()//hàm đọc file ma trận


}
catch (IOException e)
{
Console.WriteLine(e.Message);
}
}
public int layn()//hàm lấy số đỉnh
{
return n;
}
public int laya(int i,int j)//hàm lấy ma trận
{
return a[i, j];
}
public void HienThi()//hiển thị Ma trận
{
Console.WriteLine("so dinh ma tran la: {0}", n);
Console.WriteLine("Ma tran la:");
for (int i = 0; i < n; i++)
{
Console.WriteLine("\t");
for (int j = 0; j < n; j++)
{
Console.Write("{0}\t", a[i, j]);
}
Console.WriteLine("\n");
}
}


LuuVet[dem + 1] = "(" + kt+ "," + v + ")";//lưu dường đi từ đinh cuối đến đỉnh
đầu
}
public void GTS2(int[,] a, int n)
{
int i;
ChuaXet = new int[MAX];//khởi tạo mang chưa xét
LuuVet = new string[MAX];//khởi tạo mảng chứa dường đi
Luu = new string[MAX];//khởi tạo mảng chứa dường đi tốt nhất
for (i = 0; i < n; i++)
{
for (int di = 0; di < MAX; di++)//gán các giá trị mặc định cho mảng
LuuVet,và ChuaXet
{
LuuVet[di] = "-1,-1";
ChuaXet[di] = 0;
}
dem = 0;//gán biến đếm =0
cost = 0;//gán đường đi=0//dem và cost là 2 biến sử dụng trên hàm GTS()nên
mỗi lần gọi lại GTS ta gan nó =0
GTS1(i, a, n);//gọi hàm GTS()
cost += a[kt, i];//tính giá trị dường đi
Console.WriteLine("{0}", cost);///in ra giá trị dường đi chỉ demo thử
if (Best > cost && cost != 0 && dem == n - 1)//so sánh nếu giá trị dường đi
tốt nhất Best mà lớn hon7gia1 trị đường đi Cost vửa tính
{
Best = cost; //thỏa dk gán Best=Cost
for (int c = 0; c <= n; c++)

{