Số hoá bản đồ và ứng dụng tìm đường đi ngắn nhất

Đây là báo cáo đồ án môn học của sinh viên năm thứ 4 khoa công nghệ thông tin hoặc toán tin ứng dụng. Đồ án bước đầu tìm hiểu GIS, dùng phần mền MapInfo để số hóa bản đồ, Cuối dùng áp dụng thuật toán Floy tìm đường đi ngắn nhất trên bản đồ số. Đồ án được viết bằng ngôn ngữ lập trình C# 2005 và SQL Server 2005. NỘI DUNG : - Giới thiệu công nghệ GIS - Bản đồ trong MapInfo - Bài toán tìm đường đi ngắn nhất - Phân tích và thiết kế CHÚ THÍCH : ĐỒ ÁN ĐƯỢC TRÌNH BÀY DƯỚI DẠNG SLIDE

ppt20 trang | Chia sẻ: lvcdongnoi | Ngày: 02/07/2013 | Lượt xem: 2091 | Lượt tải: 4download
Bạn đang xem nội dung tài liệu Số hoá bản đồ và ứng dụng tìm đường đi ngắn nhất, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
SỐ HÓA BẢN ĐỒ VÀ ỨNG DỤNG TÌM ĐƯỜNG ĐI NGẮN NHẤT Giới thiệu công nghệ GIS GIS Địa lý Thông tin Hệ thống Hệ thống thông tin không gian dựa trên công nghệ máy tính. Mục đích: Lưu trữ hợp nhất và mô hình hóa. Phân tích và mô tả nhiều loại dữ liệu. Mô hình công nghệ GIS Khái quát hóa như một quá trình vào ra: Số liệu vào Số liệu ra Xử lý Số liệu Công nghệ số hóa bản đồ Quá trình đưa thông tin từ bản đồ giấy vào máy tính. Các bước trong việc số hóa bản đồ: -Số hóa bản đồ. -Định nghĩa cấu trúc dữ liệu. -Gán thuộc tính cho đối tượng. -Cài đặt cơ sở dữ liệu. -Chuẩn bị bản đồ. -Trình bày bản đồ. Bản đồ trong MapInfo Thông tin: Dữ liệu được thể hiện trên bảng và có cấu trúc như các bảng của SQL Server, Oracle,… Bản đồ = đồ họa + thông tin. Đồ họa: - Điểm. - Đường. - Vùng. Bài toán tìm đường đi ngắn nhất Đồ thị có hướng G = (V, E), |V| = n, |E| = m. Thuật toán đơn giản tìm đường đi ngắn nhất từ s đến t: Mỗi cặp đỉnh s và t ≠ s → tìm được đỉnh v E sao cho: d(s,t)=d(s,v)+d(v, t),v như vậy gọi là đỉnh trước của t. Từ giả thiết không âm về các trọng số ta có dãy s, v, t,…xác định, không lặp lại và kết thúc tại t. Rõ ràng dãy thu được là xác định (lật ngược thứ tự các đỉnh) ta được đường đi ngắn nhất từ s tới t. Cách thức tính toán của việc tìm đường đi ngắn nhất Từ ma trận trọng số a[u,v]; u,v V, ta tính cận trên d[v] của khoảng cách từ s đến tất cả các đỉnh v V. Mỗi khi phát hiện: d[u] + a[u,v] d[i,k] + d[k,j] then begin d[i,j]:=d[i,k] + d[k,j]; p[i,j]:=p[k,j]; end; Phân tích và thiết kế ▪ Sơ đồ phân cấp chức năng: ▪ Bảng dữ liệu: Mô đun đường đi ngắn nhất Ký hiệu: ▪Start, stop là điểm bắt đầu và điểm kết thúc . ▪d(x,y): Là khoảng cách từ x đến y. ▪min(x,y): Là khoảng cách ngắn nhất từ x đến y. ▪path(x,y): Là đường đi ngắn nhất từ x đến y. ▪minPath(x,y): Là đường đi ngắn nhất từ x đến y. Mô đun đường đi ngắn nhất Trường hợp 1: Cả Start, stop đều là điểm rẽ: → Kết quả có sau khi chạy thuật toán Floyd: Trường hợp 2: Start là điểm rẽ, stop không là điểm rẽ: Mô đun đường đi ngắn nhất ▪Thực hiện tính toán: w1 = min(start,Dau). path1 = minPath(start,Dau). w2 = min(start,Cuoi). path2 = minPath(start,Cuoi). ▪ So sánh: if w1 + d1 > w2 + d2 { min(start,stop):=w2 + d2; minPath(start,stop):=path2 +d2; } else { min(start,stop):=w1 + d1; minPath(start,stop):=path1 +d1; } Mô đun đường đi ngắn nhất Trường hợp 3: Start là điểm rẽ, stop không là điểm rẽ: ▪Thực hiện tính toán: w1 = min(stop,Dau). path1 = minPath(stop,Dau). w2 = min(stop,Cuoi). path2 = minPath(stop,Cuoi). Mô đun đường đi ngắn nhất So sánh: if w1 + d1 > w2 + d2 { min(start,stop):=w2 + d2; minPath(start,stop):=path2 +d2; } else { min(start,stop):=w1 + d1; minPath(start,stop):=path1 +d1; } Mô đun đường đi ngắn nhất Trường hợp 4: Start, stop đều không là điểm rẽ: ▪Thực hiện tính toán: w1 = minTH3(stop,Dau). //min trong trường hợp 3. path1 = minPathTH3(stop,Dau). //minPath trong trường hợp 3. w2 = minTH3(stop,Cuoi). //minTH3 trong trường hợp 3. path2 = minPathTH3(stop,Cuoi). //minPath trong trường hợp 3. Mô đun đường đi ngắn nhất ▪ So sánh: if w1 + d1 > w2 + d2 { min(start,stop):=w2 + d2; minPath(start,stop):=path2 +d2; } else { min(start,stop):=w1 + d1; minPath(start,stop):=path1 +d1; } Chỉ đường chi tiết của đường đi Giả sử đường đi từ P1 → P2 → P3 Chỉ đường chi tiết của đường đi if (x1 < x2) { P3 nằm dưới → rẽ phải. P3 nằm trên → rẽ trái. } else { P3 nằm dưới → rẽ trái. P3 nằm trên → rẽ phải. }

Các file đính kèm theo tài liệu này:

  • pptPham Cong Hoan_Slide_2k3.ppt
  • rarTimDuong_BanDo.rar
Luận văn liên quan