Luận văn thạc sĩ: Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

78
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị nhằm 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sĩ: Thuật toán song song giải quyết một số bài toán về lý thuyết đồ thị

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.