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

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. }