Xem mẫu
- 1
B GIÁO D C VÀ ĐÀO T O
Đ I H C ĐÀ N NG
NGUY N T N TH NG
THU T TOÁN SONG SONG GI I QUY T M T S
BÀI TOÁN V LÝ THUY T Đ TH
Chuyên ngành: KHOA H C MÁY TÍNH
Mã s : 60.48.01
TÓM T T LU N VĂN TH C SĨ K THU T
Đà N ng - Năm 2011
- 2
Công trình ñư c hoàn thành t i
Đ I H C ĐÀ N NG
Ngư i hư ng d n khoa h c: PGS.TSKH Tr n Qu c Chi n
Ph n bi n 1:
Ph n bi n 2:
Lu n văn s ñư c b o v trư c H i ñ ng ch m Lu n văn t t nghi p
th c sĩ k thu ttính h p t i Đ i h c Đà N ng vào ngày ….. tháng
10 năm 2011
* Có th tìm hi u lu n văn t i:
- Trung tâm Thông tin - H c li u, Đ i h c Đà N ng
- Trung tâm h c li u, Đ i h c Đà N ng.
- 3
M Đ U
1. Lý do ch n ñ tài:
Khoa h c k thu t ngày càng phát tri n, ñ t ra nhi u bài toán v i
kh i lư ng tính toán r t l n. Trong s ñó có nh ng bài toán mà k t qu ch
có ý nghĩa n u ñư c hoàn thành trong kho ng th i gian cho phép. Ví d
như các tính toán trong th i gian th c, mô ph ng s chuy n ñ ng c a các
phân t , tính quĩ ñ o chuy n ñ ng c a v t th trong không gian, d báo
th i ti t...
Đ gi i quy t nh ng bài toán này, ngư i ta ñã nghiên c u tăng t c
ñ tính toán b ng hai phương pháp hay k t h p c hai:
Phương pháp 1: C i ti n công ngh , tăng t c ñ x lý c a máy
tính. Công vi c này ñòi h i nhi u th i gian, công s c và ti n c a, nhưng t c
ñ cũng ch ñ t ñư c ñ n m t gi i h n nào ñó.
Phương pháp 2: Chia bài toán ra thành nh ng công vi c nh ñ có
th ch y song song trên nhi u b x lý.
Vi c phát tri n công ngh tính toán theo phương pháp 2 ñã cho ra
ñ i công ngh tính toán song song, ñó là vi c s d ng ñ ng th i nhi u tài
nguyên tính toán ñ gi i quy t m t bài toán. Các tài nguyên tính toán có th
bao g m m t máy tính v i nhi u b vi x lý hay m t t p các máy tính k t
n i m ng hay là m t s k t h p c a hai d ng trên. Công ngh tính toán
song song cho phép gi m th i gian th c thi bài toán tùy thu c cách phân
chia và s b x lý th c thi chương trình. Nguyên t c quan tr ng nh t c a
tính toán song song chính là tính ñ ng th i hay x lý nhi u tác v cùng m t
lúc.
Trong tính toán song song hi n nay, có hai công ngh chính:
Th nh t là s d ng các siêu máy tính v i r t nhi u b x lý ñư c
tích h p bên trong ñư c thi t k ñ ng b c v ph n c ng và ph n m m.
Các công ngh ñư c áp d ng trong các siêu máy tính thư ng là các công
ngh tiên ti n làm cho giá thành c a h th ng siêu máy tính tăng r t cao.Vì
- 4
th các siêu máy tính thư ng ñư c s d ng trong các lĩnh v c mà v n ñ
tính toán ph c t p, nh y c m và yêu c u th i gian th c như mô ph ng th c
hi n c a các ñ ng cơ máy bay, qu c phòng, vũ tr ...
Cách th hai là k t n i các máy tính l i v i nhau và cùng th c hi n
bài toán. H th ng các máy tính k t n i này chính là h th ng tính toán
song song phân c m. H th ng này có ưu ñi m là giá thành r hơn r t nhi u
so v i siêu máy tính có cùng s c m nh (do s d ng các thi t b thông
thư ng) và tính linh ho t c a h th ng (s nút, s b x lý, b nh , thi t b
m ng... ñ u mang tính tuỳ bi n cao). S phát tri n m nh m c a m ng máy
tính, các công ngh m ng hi n nay ñã l p ñi h n ch v truy n thông trong
h th ng máy tính song song phân c m làm cho nó ñư c phát tri n r ng rãi.
Các lĩnh v c s d ng h th ng tính toán song song phân c m thư ng yêu
c u tính toán không quá l n, không yêu c u th i gian th c như x lý nh,
nh n d ng vân tay, tính toán k t c u công trình, mô ph ng các thí nghi m...
V i s ra ñ i c a chíp ña lõi (multi-core) và x lí ña lu ng (multi-
threads) thì vi c khai thác h t kh năng x lí c a nó là m t v n ñ c n quan
tâm hi n nay. Tuy nhiên v i l p trình truy n th ng (l p trình tu n t ), các
câu l nh, các quá trình x lý ñư c th c h ên m t cách l n lư t, tu n t như
v y s không phát huy h t hi u năng c a b vi x lý ña lõi. Các nhà s n
xu t chip và ph n m m máy tính ñã b t ñ u nh ng n l c ñ ñ nh hư ng
gi i phát tri n ph n m m, cung c p cho h nh ng công c t t hơn trong
vi c l p trình ña lõi. Đi u ñó có nghĩa là ngư i l p trình ph i l p trình l i
theo m t cách khác ñ t n d ng s gia tăng v s lõi.
V i m c ñích tìm hi u và nghiên c u v thu t toán song song, tôi
ch n ñ tài “Thu t toán song song cho m t s bài toán v lí thuy t ñ th ”
nh m tìm hi u, nghiên c u và tìm gi i pháp song song cho m t s bài toán
v lý thuy t ñ th trên cơ s nh ng thu t toán tu n t truy n th ng.
- 5
2. M c tiêu c a ñ tài:
Tìm hi u, nghiên c u và xây d ng thu t toán song song cho m t s
bài toán c th ñ nâng cao kh năng th c hi n c a chương trình, gi m th i
gian th c hi n, góp ph n năng cao hi u năng ho t ñ ng c a h th ng.
3. Đ i tư ng và ph m vi nghiên c u:
+ Đ i tư ng nghiên c u:
- XLSS và thu t toán song song.
- Lý thuy t ñ th .
+ Ph m vi nghiên c u:
- M t s bài toán v lý thuy t ñ th : Tìm ñư ng ñi, cây bao trùm.
4. Phương pháp nghiên c u:
- Nghiên c u lý thuy t: XLSS, thu t toán song song, lý thuy t ñ th .
- Tìm hi u m t s thu t toán cơ b n: Tìm ñư ng ñi, cây bao trùm.
- Nghiên c u và xây d ng thu t toán song song.
4.1 Ý nghĩa khoa h c và th c ti n c a ñ tài:
- Nghiên c u và tìm gi i pháp nâng cao hi u năng c a h th ng b ng
XLSS.
- Có th áp d ng cho m t s lĩnh v c c th và m t s bài toán có ñ
ph c t p v th i gian l n, nh ng bài toán th i gian th c.
4.2 B c c c a ñ tài:
N i dung c a ñ tài này bao g m 3 chương:
Chương 1: Tính toán song song và thu t toán song song.
- Chương này gi i thi u t ng quan v tính toán song song, thu t
toán song song, các mô hình l p trình song song.
Chương 2: Lí thuy t ñ th .
- Chương này gi i thi u t ng quan v lí thuy t ñ th .
Chương 3: Song song hóa m t s bài toán v lí thuy t ñ th
- Chương này phát bi u, mô t và th c hi n song song hóa bài toán
tìm cây bao trùm nh nh t và bài toán tìm ñư ng ñi ng n nh t t ñ nh
ngu n ñ n m i ñ nh trên ñ th có tr ng s .
- 6
K t lu n: Nêu lên nh ng v n ñ ñã nghiên c u và k t qu ñ t
ñư c, nh ng h n ch và hư ng phát tri n c a ñ tài.
CHƯƠNG 1
Đ I CƯƠNG V X LÍ SONG SONG
1.1 M t s khái ni m v x lí song song
X lí song song là cách x lí thông tin b ng vi c s d ng nhi u hơn
m t b x lí ñ th c hi n nhi u hơn m t thao tác trên d li u t i m t th i
ñi m.
Thu t toán song song là m t t p các ti n trình (process) ho c các tác v
(task) có th th c hi n ñ ng th i và có th trao ñ i d li u v i nhau ñ k t
h p cùng gi i m t bài toán ñ t ra.
Nh ng thu t toán, trong ñó có m t s thao tác có th th c hi n ñ ng
th i ñư c g i là thu t toán song song.
1.2 Các ki n trúc song song
1.2.1 Mô hình SISD : Đơn l nh, ñơn d li u
Máy tính theo mô hình SISD ch có m t CPU, m i th i ñi m ch th c
hi n m t l nh và ch ñ c/ghi m t m c d li u. Có m t thanh ghi, g i là b
ñ m chương trình, ñư c s d ng ñ n p ñ a ch c a l nh ti p theo khi x lý
tu n t . Các câu l nh ñư c th c hi n theo m t th t xác ñ nh. Hay nói
cách khác, máy tính lo i SISD là máy tính thông thư ng, ch có duy nh t
m t b vi x lý, không có c u trúc song song và cũng không có d li u
song song.
Tín hi u
ñi u khi n
Đơn v ñi u BXL
khi n
Lu ng Lu ng Lu ng
l nh k t qu d li u
B nh
- 7
1.2.2 Mô hình SIMD: Đơn l nh, ña d li u
Máy theo mô hình SIMD có m t ñơn v ñi u khi n ñ ñi u khi n nhi u
ñơn v x lý (nhi u hơn m t ñơn v ) th c hi n theo m t lu ng các câu l nh.
Đơn v ñi u khi n (CU) phát sinh tín hi u ñi u khi n t i t t c các ph n t
x lý, nh ng b x lí này cùng th c hi n m t phép toán trên các m c d
li u khác nhau, nghĩa là m i b x lí có lu ng d li u riêng.
Đơn v ñi u khi n (CU)
Tín hi u ñi u
khi n
Ph n t Ph n t Ph n t
x lí 1 x lí 2 ... x lí n
1.2.3 Mô hình MISD: Đa l nh, ñơn d li u
Máy tính lo i MISD là ngư c l i v i SIMD. Máy tính MISD có th
th c hi n nhi u chương trình (nhi u l nh) trên cùng m t m c d li u.
Dòng l nh 1
CU 1 Ph n t x lí 1
Dòng l nh 2
CU 2 Ph n t x lí 2
. .
. .
. .
Dòng l nh n
CU n Ph n t x lí n
1.2.4 Mô hình MIMD: Đa l nh, ña d li u
Máy tính lo i MIMD còn g i là ña b x lí, trong ñó m i b x lí có
th th c hi n nh ng lu ng l nh (chương trình) khác nhau trên các lu ng d
- 8
li u riêng.
Dòng l nh 1 Lu ng d li u 1
CU 1 Ph n t x lí 1
Dòng l nh 2 Lu ng d li u 2
CU 2 Ph n t x lí 2
. .
. .
. .
Lu ng d li u
Dòng l nh n
CU n Ph n t x lí n N
1.3 Thi t k và ñánh giá thu t toán song song
1.3.1 Nguyên lý thi t thi t k thu t toán song song
Khi mu n th c hi n vi c x lí song song ta ph i xét c ki n trúc máy
tính và các thu t toán song song.
Đ thi t k ñư c các thu t toán song song c n ph i th c hi n:
- Phân chia d li u cho các tác v .
- Ch ra cách truy c p và chia s d li u.
- Phân các tác v cho các ti n trình (b x lí).
- Các ti n trình ñư c ñ ng b ra sao
Khi thi t k m t thu t toán song song có th s d ng năm nguyên lí
chính trong thi t k thu t toán song song:
+ Nguyên lý l p l ch: m c ñích là gi m t i thi u các b x lí s d ng
trong thu t toán sao cho th i gian tính toán là không tăng (xét theo khía
c nh ñ ph c t p).
+ Nguyên lý hình ng: Nguyên lý này ñư c áp d ng khi bài toán xu t
hi n m t dãy các thao tác {T1, T2, . . ., Tn}, trong ñó Ti+1 th c hi n sau khi
Ti k t thúc.
- 9
+ Nguyên lý chia ñ tr : Chia bài toán thành nh ng ph n nh hơn tương
ñ i ñ c l p v i nhau và gi i quy t chúng m t cách song song.
+ Nguyên lý ñ th ph thu c d li u: Phân tích m i quan h d li u
trong tính toán ñ xây d ng ñ th ph thu c d li u và d a vào ñó ñ xây
d ng thu t toán song song.
+ Nguyên lý ñi u ki n tương tranh: N u hai ti n trình cùng mu n
truy c p vào cùng m t m c d li u chia s thì chúng ph i tương tranh v i
nhau, nghĩa là chúng có th c n tr l n nhau.
Ngoài nh ng nguyên lý nêu trên, khi thi t k thu t toán song song ta
còn ph i chú ý ñ n ki n trúc c a h th ng tính toán. Khi chuy n m t thu t
toán tu n t sang thu t toán song song ho c chuy n m t thu t toán song
song thích h p v i ki n trúc ñang có. C n xác ñ nh ñư c yêu c u sau:
- Ki n trúc tính toán nào s phù h p v i bài toán?
- Nh ng bài toán lo i nào s x lý hi u qu trong ki n trúc
song song cho trư c ?
1.3.2 Các giai ño n thi t k thu t toán song song
- Song song hóa các thu t toán tu n t , bi n ñ i nh ng c u trúc tu n t
ñ t n d ng kh năng song song t nhiên c a t t c các thành ph n trong h
th ng x lí.
- Thi t k thu t toán song song hoàn toàn m i.
- Thi t k thu t toán song song t nh ng thu t toán song song ñã ñư c
xây d ng.
1.3.3 Đánh giá thu t toán song song
+ Th i gian tính toán
Th i gian tính toán c a gi i thu t song song là th i gian dành ñ th c
hi n tính toán. Th i gian tính toán s ph thu c vào s tác v th c hi n.
+ Th i gian truy n thông
Th i gian truy n thông c a m t gi i thu t là th i gian các tác v dành
- 10
ñ g i và nh n thông ñi p.
+ Th i gian r i
M t BXL có th ñ t trong tr ng thái r i n u thi u tính toán ho c d
li u ñ tính toán.
+ T c ñ và hi u qu :
Hi u qu c a thu t toán ñư c ñ nh nghĩa là ph n th i gian mà các b
x lí dùng ñ th c hi n công vi c có ích, ch ra m c ñ hi u qu c a m t
gi i thu t khi s d ng các tài nguyên tính toán c a m t chương trình song
song theo hư ng ñ c l p v i kích thư c bài toán.
Thu t toán song song có th có ñ ph c t p l n hơn thu t toán tu n t ,
do ñó r t khó ñ ñánh giá thu t toán song song. K t qu ñ t ñư c thư ng
ñư c ñánh giá b ng th c nghi m chương trình.
1.4 M t s mô hình l p trình song song
1.4.1 Mô hình chia s b nh :
Trong mô hình này các BXL ñ u có th truy c p vào b nh chia s , các
BXL có th ho t ñ ng ñ c l p nhưng luôn chia s ñ a ch các ô nh .
CPU 1 CPU 2 CPU n
Memory
1.4.2 Mô hình truy n thông ñi p
Trong mô hình truy n thông ñi p, các ti n trình chia s v i nhau kênh
truy n thông. Các kênh ñư c truy c p b i hai phương th c: g i và nh n
thông ñi p.
Mem1 Mem2 Memn
CPU 1 CPU 2 CPU n
Network
- 11
1.5 Môi trư ng l p trình song song
1.5.1 MPI
MPI là vi t t t c a Message Passing Interface. Đó là m t thư vi n các
hàm trong C và Fortran cho phép chèn vào trong code ñ th c hi n trao ñ i
d li u gi a các ti n trình.
MPI thư ng s d ng cho h th ng có ki n trúc b nh phân tán (h
th ng máy tính phân c m (cluster))), tuy nhiên nó cũng ho t ñ ng bình
thư ng trên h th ng ki n trúc chia s b nh .
Chương trình MPI ñư c d ch và ch y trên n n t ng có h tr chu n
MPI.
Trong mô hình l p trình MPI, các ti n trình truy n thông b ng cách g i
các hàm thư vi n ñ g i và nh n thông ñi p v i nh ng ti n trình khác.
Trong h u h t các chương trình MPI, s b x lí c ñ nh khi kh i t o
chương trình, và m t ti n trình ñư c t o ra trên m t b x lí. Tuy nhiên,
nh ng ti n trình này có th ch y nh ng chương trình khác nhau.
M t chương trình MPI bao g m nhi u chương trình tu n t có trao
ñ i d li u v i nhau thông qua vi c g i các hàm trong thư vi n.
1.5.2 OpenMP
OpenMP là công c cho phép l p trình song song h tr C/C++ và
Fortran77/90. OpenMP ho t ñ ng trên h th ng ki n trúc chia s b nh và
các máy tính ña lõi (multi-core).
OpenMP cung c p mô hình l p trình ña lu ng c p cao, xây d ng trên
thư vi n l p trình ña lu ng c a h th ng. Theo mô hình này ngư i l p trình
có th t o nhóm các lu ng cho th c hi n song song ñ ng th i ch rõ cách
các chia s công vi c gi a các lu ng thành viên c a nhóm. Cho phép khai
báo d li u chia s , riêng tư và ñ ng b các lu ng, cho phép các lu ng th c
- 12
hi n th c hi n công vi c m t các ñ c quy n. Ngoài ra OpenMP còn h tr
qu n lí th i gian th c hi n và s lư ng lu ng.
OpenMP cho phép vi t chương trình song song trong khi v n gi
nguyên mã ngu n c a chương trình tu n t . OpenMP s d ng ch th
chương trình d ch ñ ñi u khi n s song song.
OpenMP ñưa ra 2 cách song song ñó là:
+ Song song theo ch c năng: l p trình song song có c u trúc d a trên
phân chia công vi c trong vòng l p.
+ Song song theo d li u: H tr vi c gán các công vi c c th cho các
lu ng thông qua ch s c a lu ng.
CHƯƠNG 2
Đ I CƯƠNG V Đ TH
2.1 Các khái ni m cơ b n v ñ th
2.1.1 Đ nh nghĩa ñ th
Đ nh nghĩa 2.1: M t ñơn ñ th vô hư ng là m t b G=(V,E), trong ñó:
- V ≠∅ là t p h p h u h n g m các ñ nh c a ñ th .
- E là t p h p các c p không có th t g m hai ph n t khác
nhau c a V g i là các c nh.
Đ nh nghĩa 2.2: Đơn ñ th có hư ng là m t b G=(V,E), trong ñó:
- V ≠∅ là t p h p h u h n g m các ñ nh c a ñ th .
- E là t p h p các c p có th t g m hai ph n t khác nhau
c a V g i là các cung.
2.1.2 M t s khái ni m:
Đ nh nghĩa 2.3: Cho ñ th vô hư ng G=(V,E).
- Hai ñ nh u và v c a ñ th ñư c g i là k nhau n u (u,v) là
m t c nh c a ñ th .
- 13
- N u e = (u,v) là c nh c a ñ th thì ta nói c nh này là liên
thu c v i hai ñ nh u và v. C nh ñư c nói là n i ñ nh u và v. Đ nh u
và v ñư c g i là ñ nh ñ u c a c nh e.
Đ nh nghĩa 2.4: Cho ñ th vô hư ng G=(V,E). B c c a ñ nh v trong
ñ th , ký hi u là deg(v), là s c nh liên thu c v i nó. Đ nh có b c 0
ñư c g i là ñ nh cô l p, ñ nh có b c 1 g i là ñ nh treo.
Đ nh nghĩa 2.5: Cho ñ th có hư ng G=(V,E).
- Hai ñ nh u và v c a ñ th ñư c g i là k nhau n u (u,v) là m t
cung c a ñ th .
- N u e = (u,v) là cung c a ñ th thì ta nói cung này ñi ra kh i
ñ nh u vào ñi vào ñ nh v. Đ nh u ñư c g i là ñ nh ñ u c a cung
e và ñ nh v ñư c g i là ñ nh cu i c a cung e.
Đ nh nghĩa 2.6: Cho ñ th có hư ng G=(V,E)
+
- N a b c ra c a ñ nh v trong ñ th , ký hi u là deg (v), là s
c nh ñi ra kh i v.
-
- N a b c vào c a ñ nh v trong ñ th , ký hi u là deg (v), là s
c nh vào v.
2.2 Đư ng ñi, chu trình, tính liên thông
Đ nh nghĩa 2.7: Cho ñ th G = (V,E). Đư ng ñi ñ dài n t ñ nh u
ñ n ñ nh v (n là s nguyên dương) là dãy:
x0, x1, …, x n-1, xn
trong ñó u = x0, v = xn, (xixi+1)∈E, i = 0, 1, …, n-1.
Đư ng ñi nói trên còn có th ñư c bi u di n b ng dãy các c nh/cung:
(x0, x1), (x1, x2), …, (xn-1, xn)
Đ nh u g i là ñ nh ñ u c a ñư ng ñi, ñ nh v g i là ñ nh cu i c a ñư ng ñi.
Đư ng ñi có ñ nh ñ u và ñ nh cu i trùng nhau (u=v) g i là chu trình.
Đ nh nghĩa 2.8: Đ th vô hư ng G = (V,E) ñư c g i là liên thông n u
luôn tìm ñư c ñư ng ñi gi a hai ñ nh b t kỳ c a nó.
- 14
Đ nh nghĩa 2.9: Cho ñ th G = (V,E). Đ th H = (W,F) ñư c g i là ñ
th con c a G n u và ch n u W ⊆ V và F ⊆ E.
Trong trư ng h p m t ñ th vô hư ng G không liên thông, nó s ñư c
phân thành các ñ th con ñ c l p nhau và chúng ñ u liên thông. M i ñ th
con như v y ñư c g i là m t thành ph n liên thông c a G.
Đ nh nghĩa 2.10. Cho G = (V,E) là ñ th có hư ng.
- G ñư c g i là liên thông m nh n u luôn tìm ñư c ñư ng ñi gi a
hai ñ nh b t kỳ c a nó.
- G ñư c g i là liên thông y u n u ñ th vô hư ng tương ng v i nó
(ñ th vô hư ng có ñư c b ng cách bi n các cung m t
chi u thành các c nh hai chi u) là ñ th vô hư ng liên thông.
2.3 Bi u di n ñ th trong máy tính
2.3.1 Ma tr n k , ma tr n tr ng s
Xét ñ th ñơn vô hư ng G =(V, E), v i t p ñ nh V = {1, 2, . . ., n},
t p c nh E = {e1, e2, . . ., em}. Ta g i ma tr n k c a ñ th G là ma tr n
có các ph n t ho c b ng 0 ho c b ng 1 theo qui ñ nh như sau:
A = { aij: aij = 1 n u (i, j) ∈E, aij = 0 n u (i,j) ∉E; i, j =1, 2, . . ., n}.
2.3.2 Danh sách c nh (cung)
M i c nh (cung) e (x, y) ñư c tương ng v i hai bi n dau[e],
cuoi[e]. Như v y, ñ lưu tr ñ th , ta c n 2m ñơn v b nh . Như c ñi m
l n nh t c a phương pháp này là ñ nh n bi t nh ng c nh nào k v i c nh
nào chúng ta c n m phép so sánh trong khi duy t qua t t c m c nh (cung)
c a ñ th . N u là ñ th có tr ng s , ta c n thêm m ñơn v b nh ñ lưu
tr tr ng s c a các c nh.
2.3.3 Danh sách k
Trong bi u di n này, v i m i ñ nh v c a ñ th chúng ta lưu tr
danh sách các ñ nh k v i nó mà ta ký hi u là Ke(v), nghĩa là
Ke(v) = { u∈ V: (u, v)∈E},
V i cách bi u di n này, m i ñ nh i c a ñ th , ta làm tương ng v i
- 15
m t danh sách t t c các ñ nh k v i nó và ñư c ký hi u là List(i). Đ bi u
di n List(i), ta có th dùng các ki u d li u ki u t p h p, m ng ho c danh
sách liên k t.
2.4 Các thu t toán tìm ki m trên ñ th
2.4.1 Thu t toán tìm ki m theo chi u sâu
Thu t toán tìm ki m theo chi u sâu b t ñ u t ñ nh v nào ñó s
duy t t t c các ñ nh liên thông v i v. Thu t toán có th ñư c mô t b ng
th t c ñ qui DFS () trong ñó: chuaxet - là m ng các giá tr logic ñư c
thi t l p giá tr TRUE
procedure DFS( v);
begin
Thăm_Đ nh(v); chuaxet[v] := FALSE;
for u ∈ke(v) to n do
begin
if (chuaxet[u] ) then
DFS(A, n, v, chuaxet);
end;
2.4.2 Thu t toán tìm ki m theo chi u r ng (Breadth First Search)
Khác v i thu t toán tìm ki m theo chi u sâu, thu t toán tìm ki m
theo chi u r ng thay th vi c s d ng stack b ng hàng ñ i queue. Trong th
t c này, ñ nh ñư c n p vào hàng ñ i ñ u tiên là v, các ñ nh k v i v ( v1,
v2, . . ., vk) ñư c n p vào queue k ti p. Quá trình ñư c th c tương t v i
các ñ nh trong hàng ñ i. Thu t toán d ng khi ta ñã duy t h t các ñ nh k
v i ñ nh trong hàng ñ i.
chuaxet- m ng ki m tra các ñ nh ñã xét hay chưa;
queue – hàng ñ i lưu tr các ñ nh s ñư c duy t c a ñ th ;
procedure BFS(u);
begin
queue := φ;
u
- 16
chuaxet[u] := false;
while (queue ≠ φ ) do
begin
queue
- 17
2.5 Đ th Euler và Hamilton
2.5.1 Đ th Euler
Đ nh nghĩa 2.11: Cho ñ th G = (V,E). Chu trình ñơn trong G ñi qua
t t c các c nh c a nó ñư c g i là chu trình Euler. Đư ng ñi ñơn ñi qua t t
c các c nh c a ñ th ñư c g i là ñư ng ñi Euler.
Đ th G ñư c g i là ñ th Euler n u nó có ch a chu trình Euler. G
ñư c g i là ñ th n a Euler n u nó có ch a ñư ng ñi Euler.
2.5.2 Đ th Hamilton
Đ nh nghĩa 2.12: Cho ñ th G = (V,E). Chu trình sơ c p trong G ñi qua t t
c các ñ nh c a nó ñư c g i là chu trình Hamilton. Đư ng ñi sơ c p ñi qua
t t c các ñ nh c a ñ th ñư c g i là ñư ng ñi Hamilton.
Đ th G ñư c g i là ñ th Hamilton n u nó có ch a chu trình
Hamilton. G ñư c g i là ñ th n a Hamilton n u nó có ch a ñư ng ñi
Hamilton.
Đ th Hamilton cũng là ñ th n a Hamilton, ngư c l i thì không ph i
lúc nào cũng ñúng.
2.6 Cây và cây bao trùm c a ñ th
2.6.1 Cây và các tính ch t cơ b n c a cây
Đ nh nghĩa 2.13: Cây là m t ñ th vô hư ng liên thông và không ch a
chu trình.
+ G c c a cây là m t ñ nh ñ c bi t, thông thư ng là ñ nh trên cùng.
+ M c c a ñ nh là ñ dài ñư ng ñi t g c ñ n ñ nh ñó.
+ Đ cao c a cây là m c l n nh t c a cây (t c m c c a ñ nh cách xa cây
nh t).
2.6.2 Cây bao trùm c a ñ th
Đ nh nghĩa 2.14: Cho ñ th G=(V,E). Cây T g i là cây bao trùm c a G,
n u T là ñ th con ph c a G.
Đ nh lý 2.8: Đ th G=(V,E) có cây bao trùm khi và ch khi G liên thông.
- 18
2.6.3 Cây bao trùm nh nh t
Bài toán tìm cây bao trùm nh nh t là m t trong nh ng bài toán t i
ưu trên ñ th có ng d ng trong nhi u lĩnh v c khác nhau c a th c t . Bài
toán ñư c phát bi u như sau:
Cho ñ th vô hư ng G = (V,E,w). Hãy tìm cây bao trùm T c a
G sao cho t ng tr ng s c a các c nh c a T ñ t giá tr nh nh t.
Đ tìm m t cây bao trùm chúng ta có th th c hi n theo các bư c
như sau:
Bư c 1. Thi t l p t p c nh c a cây bao trùm là φ . Ch n c nh e = (i, j)
có ñ dài nh nh t b sung vào T.
Bư c 2. Trong s các c nh thu c E \ T, tìm c nh e = (i1, j1) có ñ dài
nh nh t sao cho khi b sung c nh ñó vào T không t o nên chu trình. Đ
th c hi n ñi u này, chúng ta ph i ch n c nh có ñ dài nh nh t sao cho
ho c i1∈ T và j1∉ T, ho c j1∈ T và i1∉ T.
Bư c 3. Ki m tra xem T ñã ñ n-1 c nh hay chưa? N u T ñ n-1 c nh
thì nó chính là cây bao trùm ng n nh t c n tìm. N u chưa ñ n-1 c nh thì
th c hi n l i bư c 2.
CHƯƠNG 3
XÂY D NG THU T TOÁN SONG SONG CHO M T S
BÀI TOÁN V Đ TH
3.1 Bài toán tìm cây bao trùm nh nh t
3.1.1 Bài toán:
Cho ñ th vô hư ng có tr ng s G =(V, E, w). Hãy tìm cây bao trùm
T c a G sao cho t ng tr ng s c a các c nh c a T ñ t giá tr nh nh t.
3.1.2 Thu t toán Prim tìm cây bao trùm nh t
Thu t toán Prim còn ñư c g i là phương pháp lân c n g n nh t. Trong
phương pháp này, b t ñ u t m t ñ nh tùy ý s c a ñ th , ñ u tiên, ta n i s
v i ñ nh lân c n g n nó nh t, ch ng h n là ñ nh t. K ti p, trong s các c nh
- 19
n i v i s hay t, ta l i ch n c nh có tr ng s nh nh t, … cho ñ n khi ta thu
ñư c cây g m n ñ nh và n-1 c nh. Đây chính là cây khung nh nh t c n
tìm.
+ Thu t toán Prim ñư c mô t như sau : Đ bi u di n l i gi i, ta s s
d ng 2 m ng:
- M ng d: d[v] dùng ñ lưu ñ dài c nh ng n nh t n i v i v trong
s các c nh chưa xét.
- M ng near: near[v] dùng ñ lưu ñ nh còn l i (ngoài v) c a c nh
ng n nh t nói trên.
+ Đ u vào: Đ th G = (V,E,w)
+ Đ u ra: Cây bao trùm nh nh t c a G và tr ng s tương ng
1. Procedure Prim(V, E, w)
2. Begin (* Kh i t o *)
3. Ch n s là m t ñ nh nào ñó c a ñ th .
4. H := {s}; (* T p nh ng ñ nh ñã ñưa vào cây *)
5. T := ∅; (* T p c nh c a cây *)
6. d[s] = 0;
7. near[s] = s;
8. For v∈(V \ H) do
9. Begin
10. d[v] := a[s,v];
11. near[v] := s;
12. End;
13. Stop := False;
14. While (not Stop) do (* Bư c l p *)
15. Begin
16 Tìm u∈(V \ H) th a mãn d[u] = min{d[v]: v∈(V \ H)};
17. H := H ∪ {u};
18. T := T ∪ { (u, near[u]) };
- 20
19. If |H| = n then
20. Begin
21. C := (H, T) là cây khung c a ñ th .
22. Stop := True;
23. End;
24. Else
25. For v ∈(V \ H) do
26. If d[v] > a[u,v] then
27. Begin
28. d[v] := a[u,v];
29. near[v] := u;
30. End;
31. End;
32. End;
+ Đ ph c t p c a thu t toán Prim là Ө(n2). Thu t toán s d ng 2 vòng
l p, m i vòng có (n-1) l n l p.
T(n)=2(n-1)(n-1) ∊ O(n2)
Do ñó ñ ph c t p c a thu t toán là O(n2)
3.1.3 Xây d ng thu t toán song song
+ Chia d li u cho thu t toán Prim:
- Gi thi t ñ th có n ñ nh, thu t toán th c hi n trên p BXL.
- T p các ñ nh V c a ñ th ñư c chia thành p t p con, m i t p con g m n/p
ñ nh li n k và m i t p ñư c gán ñ th c hi n trên m t BXL.
- BXL Pi qu n lí m t t p con Vi là các c t liên ti p c a ma tr n k và s
dòng là n (tương ng v i s ñ nh c a ñ th ).
- T i bư c k t n p ñ nh u vào H, BXL Pi s tính di[u]=min{d[v]:v∈(Vi H)};
- Tr ng s c a cây bao trùm nh nh t c a ñ th thu ñư c t các di[u] b ng
cách t ng h p k t qu t các BXL, l y di min[u] và chuy n v P0.
nguon tai.lieu . vn
