}
/* 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!
- Sắp Xếp Dãy A Theo Thứ Tự Tăng Dần Lúc Này A Đã Được Sắp Thứ Tự.
- Thiết kế và đánh giá thuật toán - 8
- Trọng Lượng Và Giá Trị Của 4 Loại Đồ Vật Tính Đơn Giá Cho Các Loại Đồ Vật:
- Phương Án Tìm Được Theo Thuật Toán
- Đưa Ra Các Hoán Vị Của N Số Nguyên
- Thiết kế và đánh giá thuật toán - 13
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);
do
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)
eET
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 */