Phương Án Tìm Được Theo Thuật Toán

for (x VVT)

if (bx > c[p, x])

{

bx:=c[p, x]; ax:=p;

}

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

Trong thuật toán ta coi phép toán tích cực là phép so sánh (bx<bp) khi tìm đỉnh có nhãn tốt nhất để bổ sung vào cây khung. Phép so sánh nằm trong vòng lặp for (x VVT), vòng lặp này thực hiện nhiều nhất (n-1) lần.

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

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

Vòng lặp for (x VVT) nằm trong vòng lặp while(kt) có số lần thực hiện nhiều nhất (n-1) lần.

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

3.2.5. Tìm đường đi ngắn nhất

1) Bài toán

Cho đồ thị có hướng (hoặc vô hướng) G=(V,E), V =n, E =m với các cạnh được gán trọng số, nghĩa là, mỗi cạnh (u,v)  E được đặt tương ứng với một số thực a(u,v) gọi là trọng số của nó. ở đây ta chỉ xét đồ thị có trọng số của các cạnh là không âm. Chúng ta sẽ đặt a(u,v) =, nếu (u,v) E.

Nếu dãy v0, v1, ... , vp là một đường đi trên G, thì độ dài của nó được định nghĩa là tổng sau

a(vi1 , vi)

i1

(nếu chúng ta gán trọng số cho tất cả các cạnh đều bằng 1, thì ta thu được định nghĩa độ dài của đường đi như là số cạnh của đường đi).

Bài toán tìm đường đi ngắn nhất trên đồ thị có thể phát biểu như sau: Tìm

đường đi có độ dài nhỏ nhất từ một đỉnh xuất phát sV đến đỉnh cuối cùng (đích) t  V. Đường đi như vậy ta sẽ gọi là đường đi ngắn nhất từ s đến t.

Ta sẽ xem xét việc giải quyết bài toán này bằng thuật toán Dijkstra và xem xét tính chất tham lam trong thuật toán.

2) Thuật toán Dijkstra

Thuật toán Dijkstra giải bài toán tìm đường đi ngắn nhất từ đỉnh s đến các đỉnh còn lại của đồ thị được xây dựng dựa trên cơ sở gán cho các đỉnh các nhãn tạm thời. 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 chỉ đỉnh đi trước x trong đường đi còn thành phần bx là cận trên của độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh x. Các nhãn của các đỉnh sẽ được chỉnh dần trong một quá trình lặp. Cứ mỗi bước lặp sẽ có có một nhãn tạm thời được chọn làm nhãn cố định. Khi đỉnh x có nhãn trở thành cố định thì bx sẽ là độ dài đường đi ngắn nhất từ đỉnh xuất phát đến đỉnh x. Các nhãn đã được cố định sẽ không tham gia sửa nhãn trong các bước lặp tiếp theo. Quá trình lặp sẽ kết thúc khi nhãn đỉnh t được chọn làm nhãn cố định. Khi đó bt là độ dài đường đi nhắn nhất từ đỉnh s đến đỉnh t và đường đi là: s ->...->at->t.

Thuật toán

input: Đồ thị G = (V,E) với n đỉnh,

ma trận trọng số C với c(u,u)=0, c(u,v) =, nếu (u,v) E. s V là đỉnh xuất phát, t V là đỉnh đích

output: Độ dài đường đi ngắn nhất từ đỉnh s đến đỉnh t. Dijkstra(c,s,t)

{

/* khởi tạo */ for x V do

{

bx= c[s,x]; ax=s;

}

U:= V{s}; /* U là tập các đỉnh có nhãn tạm thời*/ p=s;

while (p t)

{

p=v; //v là một đỉnh thuộc U

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

U = U {p} ; /* Cố định nhãn đỉnh p */

for (x  U) /* Gán lại nhãn các đỉnh trong U */ if (bx >bp + c[p,x] )

{

bx = bp + c[p,x] ax= p;

}

Kỹ thuật tham lam thể hiện trong thuật toán: tại mỗi bước lặp sẽ chọn một nhãn tạm thời làm nhãn cố định:

Tìm đỉnh p U thoả mãn bp = min{ bu : u U};

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

Ở mỗi bước lặp để tìm ra đỉnh p cần phải thực hiện O(n) phép toán, và để gán nhãn lại cũng cần phải thực hiện một số lượng phép toán cũng là O(n). Thuật toán phải thực hiện n-1 bước lặp, vậy thời gian tính toán của thuật toán là O(n2).

Trong thuật toán ta coi phép toán tích cực là phép so sánh (bx<bp) khi tìm đỉnh để cố định nhãn. Phép so sánh nằm trong vòng lặp for (xU), vòng lặp này thực hiện nhiều nhất (n-1) lần.

Vòng lặp for (xU) nằm trong vòng lặp while (p t) có số lần thực hiện nhiều nhất (n-1) lần.

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

3.2.6. Bµi to¸n ph©n c«ng c«ng viÖc

1) Bài toán

Cần gia công m chi tiết máy J1, J2,...,Jm. Có n máy gia công giống nhau là P1, P2, ...Pn. Mọi chi tiết đều có thể được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị cắt ngang. Ðể gia công một chi tiết Ji trên một máy bất kỳ ta cần dùng một thời gian tương ứng là ti. Hãy phân công công việc cho các máy sao cho thời gian

gia công xong toàn bộ m chi tiết là ít nhất.

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

Chúng ta xét bài toán trong trường hợp có 3 máy P1, P2, P3 và 6 chi tiết với thời gian gia công là t1=2, t2=5, t3=8, t4=1, t5=5, t6=1. Ta có một phương án phân công (L) như hình sau :

j2=5

j5=5

j1=2

j4=1

j3=8

j6=1

Hình 3.4. Phương án phân công L

Theo hình này, tại thời điểm t=0, ta tiến hành gia công chi tiết J2 trên máy P1, J5 trên P2 và J1 tại P3. Tại thời điểm t=2, công việc J1 được hoàn thành, trên máy P3 ta gia công tiếp chi tiết J4. Trong lúc đó, hai máy P1 và P2 vẫn đang thực hiện công việc đầu tiên mình...Sơ đồ phân việc theo hình ở trên được gọi là lược đồ Gantt. Theo lược đồ này, ta thấy thời gian để hoàn thành toàn bộ 6 công việc là 12. Nhận xét một cách cảm tính ta thấy rằng phương án (L) vừa thực hiện là một phương án không tốt. Các máy P1 và P2 có quá nhiều thời gian rỗi.

Xây dựng một thuật toán để tìm một phương án tối ưu cho bài toán này là một bài toán khó, đòi hỏi các kỹ thuật phức tạp mà chúng ta sẽ không đề cập ở đây. Bây giờ ta xét đến một thuật toán được thiết kế theo tinh thần của kỹ thuật tham lam để giải bài toán này mà kết quả là ta được một phương án tốt chứ chưa chắc đã là tối ưu.

Ý tưởng:

1. Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công.

2. Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời gian nhất.

Thuật toán:

- Mảng T lưu trữ thời gian gia công các chi tiết.

- Mảng TT lưu trữ thứ tự các chi tiết: TT[i]=j là chi tiết j có thứ tự i.

- Mảng TG lưu trữ thời gian gia công các chi tiết cho từng máy theo phân công. Ban đầu TG[i]=0 với 1 i  n.

Phancong(n,m)

{

// Khởi tạo mảng TG và TT for(i=1;i<=n;i++)

TG[i]=0;

for(i=1;i<=m;i++) TT[i]=i;

// Sắp xếp mảng TT theo chiều giảm dần của thời gian gia công for(i=1;i<=m;i++)

for(j=i+1;j<=m;j++) if(T[i]<T[j])

{

tg=TT[i];

TT[i]=TT[j];

TT[j]=tg;

}

// Phân công công việc min=0; for(i=1;i<=m;i++)

{

j=1;

while(TG[j]!=min) j++;

Phân chi tiết TT[i] cho máy j; TG[j]=TG[j]+T[TT[i]]; min=TG[1] ; for(j=1;j<=n;j++)

if (TG[j]<min) min=TG[j];

}

Với bài toán cụ thể trên theo thuật toán này ta sẽ có một phương án L* như

j3=8

j2=5

j1=2

j5=8

j4=1

j6=1

Hình 3.5. Phương án L*

Dễ nhận thấy rằng phương án L* vừa tìm được cũng chính là phương án tối ưu vì thời gian hoàn thành là 8, đúng bằng thời gian gia công của chi tiết J3. Tuy nhiên ta biết rằng thuật toán này chỉ cho kết quả là một phương án "tốt", không có gì đảm bảo rằng phương án đó là phương án tối ưu. Trường hợp trên có thể coi là một trường hợp "may mắn". Để thấy điều này ta xét ví dụ sau:

Ví dụ 3.2.

Có 2 máy P1, P2 và 5 chi tiết j1, j2, j3, j4, j5 với thời gian gia công là: t1=3, t2=3, t3=2, t4=2, t5=2.

j1=3

j3=2

j5=2

j2=3

j4=2

Khi đó phương án tìm được theo thuật toán có thời gian gia công xong các chi tiết là 7, trong khi đó thời gian gia công xong 5 chi tiết đã cho theo phương án tối ưu là 6. Đièu này được minh hoạ trong hình dưới đây:

Hình 3.6. Phương án tìm được theo thuật toán

j1=3

j2=3

j3=3

j4=2

j5=2

Hình 3.7. Phương án tối ưu

Nếu gọi T* là thời gian để gia công xong n chi tiết máy do thuật toán đưa ra và To là thời gian tối ưu thì người ta đã chứng minh được rằng:

T 4 1

T 0 3 3n

Với kết quả này, ta có thể xác lập được sai số mà chúng ta gặp phải nếu dùng thuật toán thay vì tìm một lời giải tối ưu. Chẳng hạn với số n=2 ta có:

T * 7

T 06

và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công thức này, số máy càng lớn thì sai số càng lớn.

Trong trường hợp n lớn thì 1/(3n) xem như bằng 0. Như vậy, sai số tối đa sẽ là 4/3To, nghĩa là sai số tối đa là 33%. Tuy nhiên, khó tìm ra được những trường hợp mà sai số đúng bằng giá trị cực đại, dù trong trường hợp xấu nhất. Thuật toán thiết kế theo kỹ thuật tham lam trong trường hợp này rò ràng đã cho chúng ta những lời giải tương đối tốt.

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

Ta có thể coi phép toán tích cực trong thuật toán là phép so sánh:

if (TG[i]<min)

Phép so sánh này nằm trong vòng lặp for(j=1;j<=n;j++) nên được thực hiện n lần. Vòng lặp for(i=1;i<=n;i++) được đặt trong vòng lặp for(i=1;i<=m;i++) do vậy phép toán tích cực if (TG[i]<min) được thực hiện n.m lần. Do vậy độ phức tạp tính toán của thuật toán là O(n.m).

Bµi tËp ch•¬ng 3

1.Cho một cái ba lô có thể đựng một trọng lượng W và n loại đồ vật, mỗi đồ vật i có một trọng lượng gi, một giá trị vi và số lượng là si. Dùng kỹ thuật tham lam tìm một cách lựa chọn các đồ vật đựng vào ba lô sao cho tổng giá trị các đồ vật được đựng trong ba lô là lớn nhất.

2. Tìm số màu ít nhất để tô cho các đỉnh của các đồ thị sau sao cho không có hai đỉnh nào kề nhau được tô cùng một màu:

a. Đồ thị vô hướng đầy đủ Kn.

b. Đồ thị vòng tròn Cn

c. Đồ thị bánh xe Wn

d. Đồ thị phân đôi đầy đủ Kn,m

3. Xếp lịch thi

Một trường đại học tổ chức học theo tín chỉ. Nếu sinh viên tích lũy đủ số chứng chỉ cho một số môn quy định của một ngành là có quyền nhận bằng tốt nghiệp của ngành đó. Đối với các đại học như thế, việc học và thi không tổ chứa theo lớp mà theo các môn học. Hàng năm nhà trường thông báo các môn sẽ học để sinh viên tự đăng ký học các môn học theo ngành mình chọn. Cuối năm nhà trường tổ chức thi cho các môn đã giảng trong năm. Mỗi môn thi trong một ngày nhưng trong một ngày có thể tổ chức thi nhiều môn. Do một sinh viên có thể đăng ký thi nhiều môn nên lịch thi cần phải bố trí để nếu có một sinh viên đăng ký thi hai môn nào đó thì các môn đó không được thi cùng ngày.

Dùng kỹ thuật tham lam thiết kế lịch thi sao cho tổng số ngày thi càng ít càng

tốt.

Hướng dẫn:

Đưa bài toán về bài toán tô màu đồ thị. Ta xây dựng đồ thị như sau :

+ Mỗi đỉnh của đồ thị là một môn học

+ Hai đỉnh của đồ thị được gọi là có cạnh nối nếu có ít nhất một sinh viên tham gia học 2 môn đó.

Như vậy ta xây dựng được một đồ thị vô hướng N đỉnh, trong đó a[i,j] = 1 nếu có cạnh nối, a[i,j] = 0 nếu không có cạnh nối.

Sau khi xây dựng được đồ thị trên ta áp dụng thuật toán tô màu đồ thị . Ta sẽ tìm ra