Thuật toán tìm đường đi tối ưu trong GIS

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

i

§¹i häc Th¸i Nguyªn

Khoa c«ng nghÖ th«ng tin

Ph¹m ThÞ H»ng Nga

ThuËt to¸n t×m ®-êng ®i tèi -u trong GIS

LuËn v¨n th¹c sÜ C¤ng ngHÖ TH¤NG TIN

Th¸i Nguyªn - 2010

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

ii

§¹i häc Th¸i Nguyªn

Khoa c«ng nghÖ th«ng tin

Ph¹m ThÞ H»ng Nga

ThuËt to¸n t×m ®-êng ®i tèi -u trong gis

Chuyªn ngµnh: Khoa häc m¸y tÝnh

M· sè: 60 48 01

LuËn v¨n th¹c sÜ C¤NG NGHÖ TH¤NG TIN

Ng-êi h-íng dÉn khoa häc

PGS. TS. §Æng V¨n §øc

Th¸i Nguyªn - 2010

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iii

ỜI CAM ĐOAN

Tôi xin cam đoan bản luận văn “Thuật toán tìm đƣờng đi tối ƣu trong

GIS” là công trình nghiên cứu của tôi dƣới sự hƣớng dẫn khoa học của

PGS.TS. Đặng Văn Đức, tham khảo các nguồn tài liệu đã đƣợc chỉ rõ trong

trích dẫn và danh mục tài liệu tham khảo. Các nội dung công bố và kết quả

trình bày trong luận văn này là trung thực và chƣa từng đƣợc ai công bố trong

bất cứ công trình nào.

Thái Nguyên, tháng 10 năm 2010

Phạm Thị Hằng Nga

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iv

Lời cảm ơn

Tôi xin gửi lời cảm ơn sâu sắc tới PGS. TS. Đặng Văn Đức, người đã tận tình

có những chỉ bảo cần thiết để giúp đỡ tôi trong suốt quá trình nghiên cứu và phát

triển luận văn.

Xin chân thành cảm ơn quý Thầy cô trong khoa Sau đại học trường Đại học

Thái Nguyên đã nhiệt tình giảng dạy, trang bị cho tôi những kiến thức quý báu

trong suốt thời gian học tập tại trường.

Xin chân thành cảm ơn các bạn cùng lớp, đồng nghiệp và đơn vị nơi tôi công

tác đã tạo điều kiện cho tôi hoàn thành luận văn này.

Xin gửi lời cảm ơn tới gia đình tôi đã động viên tôi trong suốt quá trình học

và hoàn thành luận văn.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

v

MỤC LỤC

LỜI CAM ĐOAN ............................................................................................iii

MỞ ĐẦU ........................................................................................................... 1

CHƢƠNG 1 - TỔNG QUAN VỀ GIS.............................................................. 4

1.1 Định nghĩa, các thành phần, chức năng GIS....................................... 4

1.1.1 Định nghĩa ......................................................................................... 4

1.1.2 Các thành phần.................................................................................. 9

1.1.3 Chức năng của Gis .......................................................................... 12

1.2 Cấu trúc dữ liệu không gian véctơ và các thuật toán liên quan ....... 14

1.2.1 Các thành phần dữ liệu.................................................................... 14

1.2.2 Các phép toán phân tích không gian trên mô hình Vector.............. 18

1.3 Các ứng dụng GIS ............................................................................ 22

CHƢƠNG 2 – MỘT SỐ THUẬT TOÁN TÌM ĐƢỜNG ĐI TỐI ƢU ỨNG

DỤNG TRONG GIS....................................................................................... 24

2.1 Một số thuật toán cơ sở: Disktra, Floy, A* ....................................... 24

2.1.1 Phát biểu bài toán............................................................................ 24

2.1.2 Thuật toán Dijkstra.......................................................................... 25

2.1.3 Thuật toán Bellman-Ford ................................................................ 34

2.1.4 Thuật toán A* .................................................................................. 37

2.2 Ứng dụng logíc mờ trong tìm đƣờng đi tối ƣu.................................. 46

2.2.1 Giới thiệu Logic mờ......................................................................... 46

2.2.2 Ứng dụng logic mờ trong tìm đường đi tối ưu ................................ 51

2.3 Nhận xét đánh giá.............................................................................. 53

CHƢƠNG 3 – PHÁT TRIỂN CHƢƠNG TRÌNH THỬ NGHIỆM............... 57

3.1 Giới thiệu bài toán tìm đƣờng đi tối ƣu............................................. 57

3.1.1 Lý do xây dựng chương trình........................................................... 57

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

vi

3.1.2 Mục tiêu, nhiệm vụ của chương trình.............................................. 57

3.2 Các công nghệ sử dụng ..................................................................... 58

3.2.1 MapInfo Professional ...................................................................... 58

3.2.2 Thư viện hỗ trợ xây dựng ứng dụng bản đồ MapXtreme ................ 61

3.2.3 Hệ quản trị cơ sở dữ liệu Access.................................................... 65

3.2.4 Ngôn ngữ lập trình Microsoft Visual C#.NET................................. 65

3.3 Thiết kế, lập trình hệ thống demo ..................................................... 66

3.3.1 Thiết kế............................................................................................. 66

3.3.2 Lập trình demo................................................................................. 68

3.4 Đánh giá kết quả thu đƣợc................................................................. 73

KẾT LUẬN..................................................................................................... 73

HƢỚNG PHÁT TRIỂN.................................................................................. 74

TÀI LIỆU THAM KHẢO............................................................................... 75

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

vii

DANH MỤC HÌNH VẼ

Hình 1.1 Hệ thống thông tin tin địa lý .............................................................. 6

Hình 1.2 Tầng bản đồ........................................................................................ 7

Hình1.3 Các hoạt động chính của GIS.............................................................. 8

Hình 1.4 Các thành phần của GIS..................................................................... 9

Hình 1.5 Phần cứng GIS ................................................................................. 11

Hình 1.6 Phần mềm của GIS........................................................................... 12

Hình 1.7 Các nhóm chức năng trong GIS....................................................... 13

Hình 1.8 Các thành phần hình học cơ sở ........................................................ 14

Hình 1.9: Số liệu vector đƣợc biểu thị dƣới dạng điểm (Point)...................... 15

Hình 1.10: Số liệu vector đƣợc biểu thị dƣới dạng Arc.................................. 16

Hình 1.11: Số liệu vector đƣợc biểu thị dƣới dạng vùng (Polygon)............... 17

Hình 1.12 Một số khái niệm trong cấu trúc cơ sở dữ liệu bản đồ................... 17

Hình 1.13 Phép toán Buffer ............................................................................ 18

Hình 1.14 Phép toán Difference...................................................................... 18

Hình 1.15 Phép toán Clip............................................................................... 19

Hình 1.16 Phép toán Intersect ......................................................................... 19

Hình 1.17 Phép toán Convex hull ................................................................... 20

Hình 1.18 Phép toán Symmetric difference .................................................... 20

Hình 1.19 Phép toán cut.................................................................................. 20

Hình 2.1 Đồ thị minh họa thuật toán Dijkstra................................................. 28

Hình 2.2 Đồ thị minh họa thuật toán Bellman-Ford ....................................... 35

Hình 2.3: Minh hoạ phép toán hợp trên tập mờ.............................................. 50

Hình 2.4: Minh hoạ phép toán giao trên tập mờ ............................................. 51

Hình 2.5: Đồ thị mờ G minh hoạ thuật toán FSA........................................... 51

Hình 2.6: Các đƣờng đi mờ ngắn nhất của đồ thị mờ G................................. 53

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

viii

Hình 3.1 Sơ đồ phân cấp chức năng................................................................ 66

Hình 3.2 Bảng dữ liệu .................................................................................... 67

Hình 3.3 Giao diện tìm kiếm đƣờng đi ngắn nhất........................................... 72

Hình 3.4 Giao diện kết quả tìm kiếm............................................................. 73