Thiết kế và đánh giá thuật toán

}

/* Xây dựng phương án*/ for(i=1;i<=n-1;i++)

{

Dsdv[i].Phuong_an:= Chon(dsdv[i].Trong_luong, W); W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong;

}

Trong trường hợp trọng lượng của các vật và W là các số nguyên thì ta bỏ

hàm Chon(d,S) và khi đó thuật toán sẽ là: Dovat(dsdv,W)

{

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

/*Sắp xếp mảng dsdv theo thứ tự giảm của don_gia*/ for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++) if(dsdv[i].don_gia<dsdv[j].don_gia)

{

tg=dsdv[i]; dsdv[i]=dsdv[j]; dsdv[j]=tg;

}

/* Xây dựng phương án*/ for(i=1;i<=n-1;i++)

{

Dsdv[i].Phuong_an:= W/dsdv[i].Trong_luong;

W := W – dsdv[i].phuong_an * dsdv[i].Trong_luong;

}

3) Đánh giá độ phức tạp tính toán của thuật toán

Trong thuật toán Dovat(dsdv,W) ta phải sắp xếp mảng dsdv, công việc này

mất thời gian O(n2). Tiếp theo là công việc xây dựng phương án chọn đồ vật. Công việc này được thực hiện bởi vòng lặp for(i=1;i<=n-1;i++), vòng lặp được thực hiện n lần, mỗi lần lặp lại gọi hàm Chon(dsdv[i].Trong_luong, W). Trong hàm Chon(dsdv[i].Trong_luong, W) có vòng lặp while thực hiện nhiều nhất là n phép so sánh. Do đó công việc xây dựng phương án chọn đồ vật mất thời gian O(n2).

Vậy độ phức tạp tính toán của thuật toán là O(n2).

3.2.3. Bµi to¸n t« mµu b¶n ®å

1) Bài toán

Hãy dùng số màu ít nhất để tô màu cho một bản đồ với điều kiện: mỗi quốc gia được tô một màu và hai quốc gia kề nhau (có chung đường biên giới ) thì phải có màu khác nhau.

Ta xây dựng một đơn đồ thị vô hướng: Mỗi quốc gia tương ứng với một đỉnh của đồ thị, hai quốc gia kề nhau thì hai đỉnh tương ứng kề nhau (có cạnh nối giữa chúng).

Khi đó bài toán đã cho sẽ chính là bài toán:

Hãy dùng số màu ít nhất để tô màu cho các đỉnh của một đơn đồ thị vô hướng sao cho hai đỉnh kề nhau phải có màu khác nhau. (Bài toán tô màu đồ

thị)

2) Thiết kế thuật toán

Có nhiều kỹ thuật được sử dụng để thiết kế thuật toán giải bài toán tô màu đồ thị và tìm được phương án tối ưu với thời gian hàm mũ. Ở đây chúng ta sẽ thiết kế thuật toán giải bài toán này theo tinh thần của kỹ thuật tham lam: kết quả có thể chỉ là một phương "tốt" chứ chưa đảm bảo là tối ưu nhưng thời gian là có thể chấp nhận được.

Trước hết ta định nghĩa bậc của một đỉnh là số đỉnh trên đồ thị chưa được tô mầu mà đỉnh này được nối trực tiếp với đỉnh đang xét bằng một cạnh nối trực tiếp. Nếu đỉnh đó không được nối với bất kỳ đỉnh nào thì bậc của đỉnh đó là 0

-Bước 1 : Tìm đỉnh có bậc cao nhất trên đồ thị ( gọi là đỉnh u )

-Bước 2 : Tăng số màu cần tô lên 1 và tô màu cho đỉnh vừa tìm

-Bước 3 : Tìm đỉnh v để tô màu giống u thỏa mãn các điều kiện sau : v đi đến đỉnh u thông qua duy nhất 1 đỉnh w khác và v có số bậc lớn nhất. Nếu không tìm được đỉnh như vậy ta sẽ tìm đỉnh v có bậc lớn nhất mà không kề với u. Nếu tìm được v thỏa mãn thì ta tô màu cho v chính là màu của đỉnh u. Sau đó nhập đỉnh u và

v vào làm 1 đỉnh. Tức : đỉnh w kể với v thì cũng coi như kề với u ( a[v,w] =1 thì a[u,w] =1 and a[w,u] = 1 )

-Bước 4 : Lập lại bước 3 cho đến khi v = 0.

-Bước 5 : Lặp lại bước 1 cho đến khi tô hết mầu các đỉnh của đồ thị.

Tổ chức dữ liệu:

somau: Lưu trữ số màu cần tô n : Số đỉnh của đồ thị

color : Mảng lưu màu của đỉnh đồ thị, color [i] = 0 nghĩa là đỉnh i chưa được tô màu

a : ma trận kề - a[u,v] = 1 tức hai đỉnh u và c có cạnh nối, a[u,v] = 0 tức hai đỉnh không có cạnh nối

count : Đếm số đỉnh đã tô màu ,Count = n: dừng

Thuật toán

Thuật toán được xây dựng qua các hàm sau:

- dinh_bac_max(): Hàm tìm ra đỉnh có bậc lớn nhất

- tomau(u ): tô màu cho đỉnh u

- tim_dinh_cung_mau(u, v): tìm đỉnh v để tô màu cùng với màu đinh u

- Nhapdinh(u,v): u,v được tô cùng màu thì các đỉnh kề với v được coi như kề

với u.

- main() Các hàm:

dinh_bac_max ()

{

max := -1;//Vi co the co dinh co bac la 0 for(i=1;i<=n;i++)

if (color[i] == 0) /*Xét các đỉnh chưa được tô màu để tìm ra đỉnh bậc lớn nhất*/

{

dem = 0;

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

if ((color[j] == 0) && (a[i][j] == 1)) dem++;

if (dem > max) //Cập nhật giá trị lớn nhất

{

max = dem; u = i;

}

return(u);

}

tomau(u);

{

count = count + 1; color[u] = somau;

}

tim_dinh_cung_mau(u, v )

{

max = 0; for(i=1;i<=n;i++)

if (color[i] == 0) && (a[u][i] == 0)) /* Xét các đỉnh mà u không kề mà đi

đến u qua duy nhất 1 đỉnh khác */

{

dem = 0; for(j=1;j<=n;j++)

if (color[j] == 0) && (a[i][j] == 1) && (a[u][j] == 1)) dem++;

if (dem > max) then // Cập nhật giá trị max

{

max = dem;

v = i;

}

if (v > 0) return; /*Nếu tồn tại v chưa tô màu đi đến được u thông qua

duy nhất 1 đỉnh khác*/ max = -1; // vì có thể tồn tại v mà bậc chỉ là 0 for(i=1;i<=n;i++)

if (color[i] == 0) &&(a[u][i] ==0))

{

dem = 0; for(j=1;j<=n;j++)

if ((color[j] == 0) and (a[i][j] == 1)) dem++;

if (dem > max)

{

max = dem; v = i;

}

Nhapdinh(u,v)

{

for(i=1;i<=n;i++) if (a[v,i] == 1)

{

a[u,i] = 1;

a[i,u] = 1;

}

main()

{

somau = 0; do

somau = somau+1; u = dinh_bac_max; tomau(u);

tim_dinh_cung_mau(u,v); /* Tìm đỉnh v có thể tô màu giống mầu

của u*/

if (v > 0)

{

tomau(v); nhap_dinh(u,v);

}

while (v == 0); while (count == n);

}

3) Đánh giá độ phức tạp tính toán của thuật toán

Trong hàm main() có hai vòng lặp do ... while lồng nhau, mỗi vòng lặp thực hiện nhiều nhất n lần. Trong hai vòng lặp này có lời gọi hàm tim_dinh_cung_mau(u,v), trong hàm này phép toán tích cực là phép so sánh (có thời gian O(1)) được đặt trong hai vòng lặp lồng nhau là for(i=1;i<=n;i++) và

for(j=1;j<=n;j++).

Vậy độ phức tạp của thuật toán là O(n4)

3.2.4. Tìm cây khung nhỏ nhất

1) Bài toán

Cho G = (V, E) là đồ thị vô hướng liên thông với tập đỉnh V = { 1,2,…,n} và tập cạnh E gồm m cạnh. Mỗi cạnh e của đồ thị G được gán với một số không âm c(e), gọi là độ dài của nó. Giả sử T =(V, ET) là cây khung của đồ thị G. Ta gọi độ dài c(T) của cây khung T là tổng độ dài của các cạnh của nó:

c(T ) c(e)

eET

Bài toán đặt ra là trong số tất cả các cây khung của đồ thị G hãy tìm cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất của đồ thị và bài toán đặt ra được gọi là bài toán cây khung nhỏ nhất.

Để giải bài toán cây khung nhỏ nhất, tất nhiên có thể liệt kê tất cả các cây khung của đồ thị và chọn trong số chúng cây khung nhỏ nhất. Phương pháp như vậy, trong trường hợp đồ thị đầy đủ, sẽ đòi hỏi thời gian cỡ nn-2 , và rò ràng không thể thực hiện được ngay cả với những đồ thị với số đỉnh cỡ hàng chục. Rất may đối với bài toán cây khung nhỏ nhất chúng ta đã có những thuật toán rất hiệu quả để giải chúng .Chúng ta sẽ xét một trong số những thuật toán như vậy, đó là thuật toán

Prim

2) Thuật toán Prim

Thuật toán Prim còn được gọi là phương pháp lân cận gần nhất, phương pháp này sử dụng kỹ thuật tham lam.

Cụ thể, bắt đầu từ một đỉnh nào đó tuỳ ý của đồ thị chẳng hạn là đỉnh s, đầu tiên ta nối s với đỉnh lân cận có độ dài nhỏ nhất, chẳng hạn là đỉnh y. Nghĩa là trong số các đỉnh kề của đỉnh s, cạnh(s,y) có độ dài nhỏ nhất. Tiếp theo, trong số các cạnh kề với hai đỉnh s hoặc y ta tìm cạnh có độ dài nhỏ nhất, cạnh này dẫn đến đỉnh thứ ba z, và ta thu được cây bộ phận gồm ba đỉnh và hai cạnh. Quá trình này sẽ được tiếp tục cho đến khi ta thu được cây gồm n đỉnh và n-1 cạnh, đó chính là cây khung nhỏ nhất cần tìm.

Giả sử đồ thị cho bởi ma trận trọng số C= { c[i,j] i,j =1, 2,…, n} với qui ước c[x, x] = 0 và c[x,y] =  nếu không có cạnh (x,y). Trong quá trình thực hiện thuật toán, ở mỗi bước để có thể nhanh chóng chọn đỉnh và cạnh cần bổ sung vào cây khung, các đỉnh của đồ thị sẽ được gán cho các nhãn. Nhãn của một đỉnh x sẽ gồm hai thành phần và có dạng [ ax, bx], trong đó thành phần ax ghi nhận đỉnh của cây khung gần x nhất (cây khung đang xây dựng) còn thành phần bx dùng để ghi nhận độ dài của cạnh có độ dài nhỏ nhất trong số các cạnh nối đỉnh x với các đỉnh của cây khung đang xây dựng (ta sẽ gọi là khoảng cách từ đỉnh x đến tập đỉnh của cây khung), tức là:

bx = min { c[x,y]: y  VT } (VT là tập các đỉnh của cây khung đang xây dựng). Các nhãn sẽ được chỉnh dần trong một quá trình lặp. Tại mỗi bước lặp tìm được một đỉnh có nhãn “tốt nhất” để bổ sung vào cây khung. Đỉnh đã được chọn bổ sung vào

cây khung sẽ không được tham gia chỉnh nhãn trong các bước lặp tiếp theo. Quá trình lặp sẽ kết thúc khi tập VT có n phần tử.

Thuật toán Prim được thể hiện nhu sau: CKNN()

{ // khởi tạo

//Chọn s là một đỉnh nào đó của đồ thị VT={s};

ET=;

bs=0; as=s;

for (x  V VT)

{

ax = s;

bx= c[s,x];

}

kt=1; while(kt)

{

// tìm đỉnh có nhãn “tốt nhất” bổ sung vào cây khung p=v; //v là một đỉnh thuộc VVT

for (x  V VT) if(bx<bp) p=x;

VT =VT  {p}; ET=ET{(p, ap)};

if (VT==n)

{

T= (VT, ET) là cây khung nhỏ nhất của đồ thị; kt=0;

}

else /* chỉnh nhãn */