Luận văn: Giải bài toán tìm đường đi ngắn nhất bằng thuật toán song song meta-heuristic

Tham khảo luận văn - đề án luận văn:giải bài toán tìm đường đi ngắn nhất bằng thuật toán song song meta-heuristic, luận văn - báo cáo, thạc sĩ - tiến sĩ - cao học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Luận văn:Giải bài toán tìm đường đi ngắn nhất bằng thuật toán song song meta-heuristic -1- -2- B GIÁO D C VÀ ĐÀO T O Công trình ñư c hoàn thành t i Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG LÊ NG C QUANG Ngư i hư ng d n khoa h c: PGS.TSKH. Tr n Qu c Chi nGI I BÀI TOÁN TÌM ĐƯ NG ĐI NG N NH T Ph n bi n 1: B NG THU T TOÁN SONG SONG PGS.TS. Võ Trung Hùng META-HEURISTIC Ph n bi n 2: TS. Hoàng Th Lan Giao Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 Lu n văn s ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p Th c sĩ k thu t h p t i Đ i h c Đà N ng vào ngày 04 tháng 03 năm 2012. TÓM T T LU N VĂN TH C SĨ K THU T * 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 Đà N ng - Năm 2012 - Trung tâm H c li u, Đ i h c Đà N ng. -3- -4- M Đ U 3. Đ i tư ng và ph m vi nghiên c u Đ i tư ng nghiên c u1. Lý do ch n ñ tài - Nghiên c u các gi i thu t ki n Bài toán t i ưu t h p là d ng bài toán có ñ ph c t p tính - Mô hình tính toán song song Message Passing Interfacetoán cao thu c l p NP khó. S ra ñ i c a gi i thu t Meta-Heuristic - Thu t toán ki n song songñã gi i quy t các bài toán v i hi u qu cao cho k t qu l i gi i g n Ph m vi nghiên c ut i ưu như h gi i thu t ki n (Ant Algorithm), gi i thu t luy n thép - T p trung nghiên c u thu t toán song song áp d ng vào gi iSA (Simulated Annealing), gi i thu t di truy n GA (Genetic thu t ki n.Algorithm). - Vi c th nghi m ñ i v i bài toán ngư i du l ch - Travelling V i ñ ph c t p tính toán cao c a các bài toán t i ưu t h p Salesman problem (TSP) ñư c s d ng là thư vi n chu n TSPLIBcũng như ñòi h i v m t th i gian, vi c gi i các bài toán này v i tính 4. Phương pháp nghiên c uch t tu n t c a gi i thu t s g p ph i nh ng v n ñ v th i gian th c Phương pháp tài li u:hi n chương trình, t c ñ x lý, kh năng lưu tr c a b nh , x lý Nghiên c u lý thuy t v thu t toán ki n, các v n ñ songd li u v i quy mô l n... Kích thư c bài toán tăng lên và không gian song hóa. Trên cơ s lý thuy t nghiên c u ñư c s v n d ng k t qutìm ki m càng l n yêu c u c n ph i song song hóa các gi i thu t ñ tìm ki m t i ưu c a thu t ki n song song vào bài toán ngư i du l ch.tăng t c ñ và hi u qu c a gi i thu t. Phương pháp th c nghi m M c ñích c a ñ tài là gi i quy t bài toán tìm ñư ng ñi ng n Xây d ng chương trình và ñánh giá k t qu th nghi m v inh t b ng thu t toán ki n song song nh m phát huy s c m nh c a bài các mô hình song song.toán. Trên cơ s ñó s ñưa ra k t qu ñánh giá hi u qu c a thu t toán 5. Ý nghĩa khoa h c và th c ti n c a ñ tàiki n trên các mô hình song song. Nghiên c u và gi i thi u thu t toán ñàn ki n và thu t toán2. M c ñích nghiên c u ñàn ki n song song trong vi c gi i bài toán tìm ñư ng ñi ng n nh t và Các m c tiêu c th g m: ng d ng thu t toán vào bài toán ngư i du l ch. - Nghiên c u v gi i thu t Meta-Heuristic ñ c bi t là h các 6. C u trúc lu n văngi i thu t ki n N i dung chính c a lu n văn này ñư c chia thành ba chương - Nghiên c u v các v n ñ song song hóa và gi i thu t ñàn v i n i dung như sau:ki n song song. Chương 1 – Cơ s lý thuy t: N i dung chính là tìm hi u, - Áp d ng gi i thu t ki n song song vào bài toán tìm ñư ng nghiên c u lý thuy t liên quan ñ n v n ñ nghiên c u v lý thuy t ññi ng n nh t. th , các v n ñ l p trình song song, thu t toán ñàn ki n . -5- -6- Chương 2 – Thu t toán ki n song song: T thu t toán t i CHƯƠNG 1ưu ñàn ki n tu n t th c hi n chuy n sang thu t toán t i ưu ñàn ki n CƠ S LÝ THUY Tsong song trên mô hình truy n thông ñi p. Chương 3 – Phân tích, xây d ng và cài ñ t chương trình: 1.1. CÁC KHÁI NI M CƠ B N V Đ THPhân tích ch c năng và xây d ng chương trình ng d ng vào bài toán 1.1.1. Đ nh nghĩa ñ thngư i du l ch ñ ng th i ti n hành ch y th nghi m, ñánh giá k t qu . 1.1.2. Tính liên thông c a ñ th 1.1.3. Đ th Euler và ñ th Hamilton Đ nh nghĩa 1.13. Chu trình (tương ng ñư ng ñi) ñơn ch a t t c các c nh (ho c cung) và các ñ nh c a ñ th (vô hư ng ho c có hư ng) G ñư ...