Tham khảo tài liệu 'giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình poisson với tham số p7', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
AMBIENT/
Chủ đề:
Nội dung Text: Giáo trình hình thành công cụ phân tích hàm mũ với tham số theo tiến trình Poisson với tham số p7
- Bảng 4.3
Nút init. A(0) B(5) C(1) E(11) D(6)
A 0(-) A 0(-) B 0(-) C 0(-) E 0(-) D 0(-) B
5(A) C 5(A) E 4(C) D 4(C) B 4(C) F
B (-)
1(A) 1(A) D 1(A) B 1(A) F 1(A)
C (-)
6(B) 6(B) 6(B) 6(B)
D (-) (-)
11(B) 11(B) 11(B) 11(B)
E (-) (-)
13(E) 10(D)
F (-) (-) (-) (-)
B(4) F(10) E(10) D(5) F(9)
A 0(-) F 0(-) E 0(-) D 0(-) F 0(-)
B 4(C) E 4(C) D 4(C) 4(C) 4(C)
C 1(A) D 1(A) 1(A) 1(A) 1(A)
D 5(B) 5(B) 5(B) 5(B) 5(B)
E 10(B) 10(B) 10(B) 10(B) 10(B)
F 10(D) 10(D) 10(D) 9(D) 9(D)
Thuật toán có thể viết như sau:
array[n]
- while (not(Empty( scan_queue ))
i
- cả các nút khác. Một khả năng có thể đó là sử dụng thuật toán
Bellman hoặc thuật toán Dijkstra N lần, bắt đầu từ mỗi nút nguồn. Một
khả năng khác, đặc biệt thích hợp với các mạng dày, là sử dụng thuật
toán Floyd.
Thuật toán Floyd dựa vào quan hệ đệ quy đã được trình bày trong
phần giới thiệu thuật toán Dijkstra, nhưng thuật toán này sử dụng quan
hệ đệ quy đó theo một cách khác. Lúc này, dij(k) được định nghĩa là
đường đi ngắn nhất từ i tới j sử dụng các nút được đánh số là k hoặc
thấp hơn như là các nút trung gian. Vì thế dij(0) được định nghiã như là
lij, độ dài của liên kết từ nút i tới nút j, nếu liên kết đó tồn tại hoặc dij(0)
sẽ bằng vô cùng nếu liên kết đó không tồn tại. Vì vậy,
dij(k) = min (dij(k-1), dik(k-1) + dkj(k-1) )
nghĩa là, chúng ta chỉ quan tâm đến việc sử dụng nút k như là một
điểm quá giang cho mỗi đường đi từ i tới j. Thuật toán có thể được viết
như sau:
array[n]
- Hình 4.7: Ví dụ graph
Ví dụ 4.9:
Xét graph trong hình 4.7. Mảng chứa khoảng cách ban đầu và mảng
chứa nút trung gian cuối cùng của mỗi đường đi được cho trước như
sau:
Đến Đến
A B C D E A B C D E
A 0 3 2 - - A A A A A A
B - 0 - 2 - B B B B B B
T T
C - 5 0 - 2 C C C C C C
ừ ừ
D - - 1 0 1 D D D D D D
E - - - - 0 E E E E E E
sp_dist pred
Chú ý rằng sp_dist có các giá trị 0 trên đường chéo chính và vô
cùng lớn (được biểu diễn là dấu "-") nếu giữa hai nút không tồn tại một
liên kết. Ngoài ra vì graph là graph hữu hướng và không đối xứng nên
sp_dist cũng không đối xứng.
Xét A ta thấy A là một nút trung gian không ảnh hưởng đến các dãy
này vì không có cung nào đi tới nó và vì thế không có đường đi nào đi
qua A. Tuy nhiên, xét nút B ta thấy rằng nút B gây nên sự thay đổi ở vị
trí (A, D) và (C, D) trong các dãy trên , cụ thể như sau :
Đến Đến
A B C D E A B C D E
T A 0 3 2 5 - T A A A A B A
ừ ừ
B - 0 - 2 - B B B B B B
C - 5 0 7 2 C C C C B C
70
- D - - 1 0 1 D D D D D D
E - - - - 0 E D D D D D
sp_dist pred
Tiếp tục xét các nút C, D và E thì gây nên sự thay đổi cụ thể như sau:
Đến Đến
A B C D E A B C D E
A 0 3 2 5 4 A A A A B C
B - 0 3 2 3 B B B D B D
T T
C - 5 0 7 2 C C C C B C
ừ ừ
D - 6 1 0 1 D D C D D D
E - - - - 0 E E E E E E
sp_dist pred
Các thuật toán tìm đi ngắn nhất mở rộng
Trong quá trình thiết kế v à phân tích mạng đôi khi chúng ta phải tìm
đường đi ngắn nhất giữa mọi cặp các nút (hoặc một số cặp) sau khi có
sự thay đổi độ dài một cung. Việc thay đổi này bao gồm cả việc thêm
hoặc loại bỏ một cung (trong trường hợp đó độ dài của cung có thể
được xem như là chuyển từ không xác định thành xác định hoặc
ngược lại). Vì thế ta giả thiết rằng đường đi ngắn nhất giữa tất cả các
cặp nút là biết trước và bài toán đặt ra ở đây là xác định (nếu có)
những sự thay đổi do việc thay đổi độ dài của một cung nào đó. Thuật
toán sau đây được Murchland phát biểu, trong đó xem xét riêng rẽ cho
từng trường hợp: tăng và giảm độ dài của các cung . Những thuật toán
này hoạt động với các graph hữu hướng và có thể hoạt động với các
độ dài cung là âm, tuy nhiên thuật toán này vẫn không giải quyết các
chu trình có tổng độ dài là âm.
Độ dài cung giảm
Giả sử rằng độ dài cung (i,j) được giảm. Vì sự lồng nhau trong các
đường đi ngắn nhất (nghĩa là một nút k thuộc một đường đi ngắn nhất
từ i tới j thì đường đi ngắn nhất từ i tới j sẽ bằng đường đi ngắn nhất
từ i tới k hợp với đường đi ngắn nhất từ j tới k) nên nếu cung (i, j)
không phải là đường đi ngắn nhất sau khi cung này được làm ngắn
(trong trường hợp này cung (i, j) có thể không phải là đường đi ngắn
nhất trước khi độ dài của cung (i, j) bị thay đổi) thì nó không phải là một
phần của đường đi ngắn nhất nào cả và sự thay đổi được bỏ qua.
Tương tự, nếu (i, j) là một phần của đường đi ngắn nhất từ k tới m thì
nó phải là một phần của đường đi ngắn nhất từ k tới j và đường đi
ngắn nhất từ i tới m. Thực ra, đường đi ngắn nhất từ k tới m mới phải
71
- chuỗi các đường đi từ k tới i cũ, liên kết (i, j) và đường đi từ j tới m.
Điều này được biểu diễn trong hình 4.8.
Hình 4.8. Đường đi ngắn nhất mở rộng khi (i, j) được làm ngắn
Vì thể cần phải quét các nút i v à j để tìm các tập K và M thích hợp
chứa các nút k và m như trong hình 4.8 và thực hiện việc xét các cặp
nút, mỗi nút từ một tập (K hoặc M đã nói ở trên ). Với i thuộc K và j
thuộc M thực hiện việc kiểm tra điều kiện sau
dkm > dki+lij +djm
nếu đúng, cập nhật dkm và nút trung gian cuối cùng của đường đi này.
Thuật toán này có thể được viết như sau:
(array[n,n], array[n,n])
sp_dist[k,i] + length + sp_dist[j,m])
sp_dist[k,m]
- else
pred[k, m]
- for each (a , n )
for each ((k,m) , pairs )
if(sp_dist[k,m] > sp_dist[k,a]+
sp_dist[a,m])
sp_dist[k,m] lBE + dEC
nhưng
dBx lBE + dEx
74
- đối với tất cả các nút khác. Vì vậy
setm = C, E
Tương tự,
setk = A, B
Bảng 4.4
A B C D E
A 0 2 3 5 4
B 2 0 5 3 6
C 3 5 0 5 1
D 5 3 5 0 4
E 4 6 1 4 0
Bây giờ chúng ta xét các cặp nút
(k, m) với k setk và m setm, (nghĩa là các cặp (A,C), (A, E), (B, C)
và (B, E)). Chúng ta thấy rằng tất cả các cặp trừ cặp (A, C) đều bị thay
đổi nên chúng ta cập nhật các đường đi ngắn nhất và nút trung gian
cuối cùng của mỗi đường đi ngắn nhất giữa các cặp nút này. Ma trận
đường đi ngắn nhất bây giờ được biểu diễn trong bảng 4.3
Bảng 4.5
A B C D E
A 0 2 3 5 3
B 2 0 2 3 1
C 3 5 0 5 1
D 5 3 5 0 4
E 4 6 1 4 0
Chú ý rằng, ma trận này không còn đối xứng nữa vì một cung (B, E)
vừa mới được thêm vào mạng.
Bây giờ giả sử rằng lBE = 5 (ví dụ cho bài toán có sự tăng độ dài một
cung). Kiểm tra ma trận đường đi ngắn nhất, ta thấy rằng trước khi
thay đổi lBE thì
dBE = lBE
Chúng ta kiểm tra tất cả các cặp nút (k, m) và thấy rằng điều kiện
dkm = dki + lij + djm
75
- chỉ có các cặp (A, E), (B, C) và (B, E) thoả mãn. Vì thế chúng ta thực
hiện phép gán sau
pairs
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
