tailieunhanh - BÁO CÁO " THUẬT TOÁN SONG SONG TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ "

Kết quả chính của bài báo cáo là nghiên cứu thuật toán tìm đường đi ngắn nhất trên đồ thị. Dựa trên cơ sở vận dụng thuật toán Dijkstra và lý thuyết thuật toán song song, đề tài nghiên cứu để tìm ra các tiến trình cần xử lý song song,từ đó xây dựng được thuật toán song song phân chia công việc cho các bộ xử lý nhằm giảm thời gian xử lý. Chương trình tương ứng cài đặt bằng Java, công nghệ MySql cho kết quả chính xác | Tuyển tập Báo cáo Hội nghị Sinh viên Nghiên cứu Khoa học lần thứ 8 Đại học Đà Nẵng năm 2012 THUẬT TOÁN SONG SONG TÌM ĐƯỜNG ĐI NGẮN NHẤT TRÊN ĐỒ THỊ USING THE PARALLEL ALGORITHM TO FIND THE SHORTEST PATH ON THE GRAPH SVTH Nguyễn Mậu Tuệ Lớp 08CNTT01 Trường Đại Học Sư Phạm Đại Học Đà Nằng GVHD Trần Quốc Chiến Khoa Tin Học Trường Đại Học Sư Phạm Đại Học Đà Nằng TÓM TẮT Kết quả chính của bài báo cáo là nghiên cứu thuật toán tìm đường đi ngắn nhất trên đồ thị. Dựa trên cơ sở vận dụng thuật toán Dijkstra và lý thuyết thuật toán song song đề tài nghiên cứu để tìm ra các tiến trình cần xử lý song song từ đó xây dựng được thuật toán song song phân chia công việc cho các bộ xử lý nhằm giảm thời gian xử lý. Chương trình tương ứng cài đặt bằng Java công nghệ MySql cho kết quả chính xác. Từ khoá thuật toán Dijkstra thuật toán song song bộ xử lý. ABSTRACT Main result of this article is to study algorithms find the shortest path on the graph. Basing on Dijkstra s algorithm and theory of parallel algorithms we have researched to find the processes which must to be processed in parallel algorithms since then we have built the parallel algorithms in order to distribute work for processors to reduce time. This program is installed by Java and MYSQL technology and gave an accurate result. Key word Dijkstra s algorithm parallel algorithms processors. 1. Đặt vấn đề . Bối cảnh thực tế Ngày nay máy tính đã được sử dụng trong hầu hết các lĩnh vực và đã góp phần quan trọng vào việc thúc đẩy sự phát triển kinh tế xã hội khoa học kỹ thuật . Đặc biệt trong lĩnh vực tính toán máy tính là công cụ không thể thiếu khi giải quyết những bài toán đòi hỏi khối lượng tính toán lớn độ chính xác cao trong thời gian thực. Với những bài toán lớn việc tính toán xử lý chỉ trên một bộ vi xử lý hoặc trên một máy tính đã không thể đáp ứng được yêu cầu đặt ra ví dụ điều khiển các tàu vũ trụ xử lý thông tin về gien điều khiển các lò phản ứng hạt nhân .Vì vậy nhu cầu thực hiện tính toán song song để có