ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH TRƯỜNG I HC BCH KHOA LUAN VAấN THAẽC Sể Đề tài: NGHIÊN CỨU VÀ PHÁT TRIỂN BÀI TỐN TÌM ĐỐI TƯỢNG GẦN NHẤT (FINDING THE CLOSEST FACILITY) DỰA TRÊN LÝ THUYẾT TẬP MỜ VÀ BIẾN NGÔN NGỮ CHUYÊN NGÀNH: HỆ THỐNG THÔNG TIN ĐỊA LÝ (GIS) MÃ SỐ NGÀNH: 2.15.04 TÁC GIẢ: TRẦN VĨNH TRUNG THÀNH PHỐ HỒ CHÍ MINH - 2004 Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường Lời cảm ơn Tơi muốn bày tỏ lịng biết ơn sâu sắc đến người Cô, người Thầy tận tâm hướng dẫn giúp đỡ tơi hồn thành luận văn Tôi xin trân trọng cảm ơn: Thầy PGS.TSKH BÙI CÔNG CƯỜNG, người trực tiếp hướng dẫn khoa học Thầy PGS.TSKH NGUYỄN XUÂN HUY, Thầy PGS.TS TRẦN VĨNH PHƯỚC, Thầy TS NGUYỄN LƯƠNG BÁCH động viên cho kiến thức quý báu liên quan đến đề tài Và người Cô, người Thầy tận tâm giảng dạy tơi suối khóa cao học chuyên ngành GIS Tôi xin chân thành cảm ơn đồng nghiệp công tác Trung tâm Công Nghệ Thông Tin Địa Lý người bạn lớp cao học Tôi xin chân thành cảm ơn Trung tâm Công Nghệ Thông Tin Địa Lý tạo điều kiện cho tiếp cận học hỏi nhiều GIS Cuối tơi xin trân trọng bày tỏ lịng biết ơn vơ hạn đến gia đình tơi, ngưịi cho tơi nguồn động viên lớn lao để hồn thành nghiên cứu TRẦN VĨNH TRUNG Tháng 8/2004 SVTH: Trần Vĩnh Trung ii Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Cơng Cường Tóm tắt luận văn Khoa học thơng tin địa lý lý thuyết mờ ngày phát triển mạnh khả ứng dụng chúng thực tiễn sống Đã có nhiều nghiên cứu đề cập đến việc ứng dụng lý thuyết mờ GIS để khẳng định khoa học thông tin địa lý lý thuyết mờ ngày gần hơn, đặc biệt người muốn tìm hiểu nhiều giới tự nhiên Đề tài nghiên cứu việc ứng dụng lý thuyết mờ vấn đề phân tích mạng hệ thống GIS, cụ thể ứng dụng lý thuyết mờ vào tốn Tìm đối tượng gần – Finding the closest facilities Trong này, tác giả trình bày tổng quan việc ứng dụng lý thuyết mờ nhiều khía cạnh GIS mục tiêu, phương pháp nghiên cứu, nội dung thực cụ thể, ý nghĩa đề tài chương Chương đề tài kiến thức lý thuyết GIS, mạng, số mờ có liên quan đến nội dung nghiên cứu Trong chương 3, tác giả tập trung làm bật vấn đề cần giải ứng dụng giải thuật Dijkstra mờ vào hệ thống GIS cụ thể với số mờ biểu diễn cấu trúc topology Bên cạnh đó, nhiều phương pháp, giải thuật, nhận xét phương pháp cộng so sánh số mờ, mơ hình liệu hỗ trợ phân tích mạng mờ trình bày chương Chương đề tài kết cài đặt chương trình phân tích mạng mờ Bài nghiên cứu kết thúc chương Trong chương 5, tác giả trình bày nội dung thực đề tài hướng nghiên cứu phát triển đề tài SVTH: Trần Vĩnh Trung iii Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường Abstract Geographic Information Science and Fuzzy Theory have been developing rapidly due to their capabilities of practical applications There have been a lot of papers concentrating on applying fuzzy theory to GIS This proves that GIS and fuzzy theory are coming together to help scientists to reveal the real world This research is about applying fuzzy theory to GIS network analysis, specifically, using fuzzy theory in the issue of finding the closest facilities The author presents an overview of applying fuzzy theory to various aspects of GIS as well as the purpose, methodology, duty, and significance of the research in the first chapter The second chapter is about some theories of GIS, network flow, and fuzzy number In chapter 3, the author discusses the important issues when applying GIS to a specific GIS using topology structure to represent fuzzy numbers Besides, some methodologies, algorithms, remarks of fuzzy addition and ranking methods, and data model supporting fuzzy network analyses are presented as well Chapter should be about the results of the research The report is ended with chapter which summarizes the tasks of this research and proposes some future researches SVTH: Trần Vĩnh Trung iv Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường Mục lục Tóm tắt luận văn ii Abstract iv Mục lục v Danh sách hình ảnh ix CHƯƠNG 1: GIỚI THIỆU 1 GIỚI THIỆU 1.1 Đặt vấn đề 1.2 Tổng quan tình hình nghiên cứu ứng dụng GIS 1.2.1 Trên giới 1.2.2 Trong nước 1.3 Một số nghiên cứu ứng dụng lý thuyết mờ GIS 1.4 Tình hình nghiên cứu liên quan đến đề tài .9 Mạng mờ phân loại mạng mờ .9 1.4.1 Loại I: Tập mờ mạng rõ 1.4.2 Loại II: Tập đỉnh rõ tập cạnh mờ 10 1.4.3 Loại III: Tập đỉnh cạnh rõ với liên kết mờ 11 1.4.4 Loại IV: Tập đỉnh mờ tập cạnh rõ 12 1.4.5 Loại V: Mạng rõ với trọng số mờ 13 Biểu diễn số mờ cấu trúc topology 13 Một số nghiên cứu khác 14 NỘI DUNG NGHIÊN CỨU 15 2.1 Mục tiêu đề tài 15 2.2 Phạm vi thực 15 2.3 Phương pháp nghiên cứu 15 2.4 Nội dung nghiên cứu .16 2.4.1 Nội dung nghiên cứu .16 2.4.2 Mô tả chi tiết nội dung nghiên cứu 16 2.5 Ý nghĩa khoa học 18 2.5.1 Ý nghĩa khoa học 18 2.5.2 Ý nghĩa xã hội 18 SVTH: Trần Vĩnh Trung v Luận văn thạc sĩ 2.6 GVHD: PGS.TSKH Bùi Cơng Cường Tiến trình thực .19 CHƯƠNG 2: CƠ SỞ LÝ THUYẾT 20 LÝ THUYẾT MẠNG 20 1.1 Một số khái niệm định nghĩa .20 1.2 Biểu diễn mạng .25 1.2.1 Ma trận quan hệ nút cung (node – arc incidence matrix) 25 1.2.2 Ma trận liên kết nút - nút (node – node adjacency matrix) .27 1.2.3 Danh sách liên kết (adjacency lists) 28 1.2.4 Tóm tắt 29 MẠNG TRONG CÁC HỆ THỐNG THÔNG TIN ĐỊA LÝ (Geographic Information Systems - GIS) 30 2.1 Một số khái niệm hệ thống thông tin địa lý .30 2.2 Phân tích mạng GIS .32 2.2.1 Yêu cầu liệu phân tích mạng 32 2.2.2 Đánh giá cấu trúc mạng 34 2.2.3 Bán kính mạng .35 2.3 Các đối tượng sở liệu GIS (Geodatabase) 35 2.4 Cấu trúc topology topology mạng sở liệu GIS 38 2.4.1 Cấu trúc cung nút (arc - node ) Planar Topology: 38 2.4.2 Cấu trúc polygon – arc: 39 2.4.3 Cấu trúc left – right: 39 2.5 2.5.1 Giới thiệu .40 2.5.2 Mạng hình học - Geometric network 42 2.5.3 Mạng luận lý - Logical network 42 2.6 Cấu trúc Geomertric Network Geodatabase 40 Tóm lược .45 LÝ THUYẾT MỜ, SỐ MỜ 45 3.1 Tập mờ - Một số khái niệm .45 3.2 Biểu diễn tập mờ 48 3.3 Số mờ 52 3.3.1 Giới thiệu .52 3.3.2 Đặc điểm số mờ 53 3.3.3 Các phép toán số mờ 55 SVTH: Trần Vĩnh Trung vi Luận văn thạc sĩ 3.3.4 GVHD: PGS.TSKH Bùi Công Cường Vấn đề so sánh số mờ 56 CHƯƠNG 3: ỨNG DỤNG LÝ THUYẾT MỜ TRONG GIẢI THUẬT “TÌM ĐỐI TƯỢNG GẦN NHẤT” 59 PHÂN TÍCH KHẢ NĂNG ỨNG DỤNG LÝ THUYẾT MỜ TRONG GIẢI THUẬT DIJKSTRA 59 1.1 Giải thuật Dijkstra GIS 59 1.2 Những vấn đề ứng dụng lý thuyết mờ 62 1.2.1 Cộng số mờ 62 1.2.2 So sánh số mờ .63 GIẢI THUẬT DIJKSTRA MỜ 64 GIẢI THUẬT DIJKSTRA MỜ VỚI TOPOLOGY 66 3.1 Vấn đề cộng số mờ 66 3.2 Vấn đề so sánh số mờ .70 3.2.1 Cách - Sử dụng mặt cắt α vị trí cho trước 71 3.2.2 Cách - Sử dụng nhiều mặt cắt α so sánh phần 74 3.2.3 Cách - Sử dụng nhiều mặt cắt α so sánh tổng hợp 76 MƠ HÌNH DỮ LIỆU HỖ TRỢ PHÂN TÍCH MẠNG MỜ 82 4.1 Yêu cầu 82 4.2 Khảo sát thông tin 82 4.3 Mơ hình ý niệm .83 CHƯƠNG 4: KẾT QUẢ ĐỀ TÀI 86 ỨNG DỤNG THUẬT TỐN TRONG GIS GIẢI QUYẾT MỘT SỐ VẤN ĐẾ CHÍNH KHI ỨNG DỤNG LÝ THUYẾT MỜ VÀO GIẢI THUẬT DIJKSTRA .86 MƠ HÌNH DỮ LIỆU HỖ TRỢ PHÂN TÍCH MẠNG MỜ 86 CHƯƠNG TRÌNH PHÂN TÍCH MẠNG MỜ TRONG GIS .87 3.1 3.1.1 Kiến trúc khung nhìn .87 3.1.2 Kiến trúc chức 88 3.2 Thiết kế chương trình .87 Kết xây dựng chương trình 90 KẾT QUẢ CÀI ĐẶT GIẢI THUẬT 91 4.1 Khảo sát dịng chảy có qua điểm xảy kiện 91 4.1.1 Trường hợp số mờ dạng hình tam giác (3 đỉnh) với β = 0.5 92 4.1.2 Trường hợp số mờ dạng khác – đa giác lồi đỉnh 108 4.1.3 Nhận xét kết thử nghiệm 136 SVTH: Trần Vĩnh Trung vii Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường CHƯƠNG 5: KẾT LUẬN .137 NHỮNG NỘI DUNG ĐÃ GIẢI QUYẾT 137 HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI .137 2.1 Phát triển luật mờ cho mạng rõ, trọng số mờ 137 2.2 Truy vấn mạng rõ, trọng số mờ 139 2.3 Phát triển toán “Người bán hàng” mạng rõ trọng số mờ .140 2.4 Phát triển tốn “Phân phối hàng hóa” 140 Tài liệu tham khảo .141 Phụ lục A – Giới thiệu số chức chương trình 1 Bước 1: Mờ hóa .1 Bước 2: Phân tích mạng Bước 3: Xem vị trí đối tượng gần .5 Soạn thảo số mờ Xem thông tin mạng Biểu diễn hướng cạnh .9 Danh mục công cụ 10 Phụ lục B – Một số đoạn mã chương trình 1 Liên quan đến chức Liên quan đến chức Liên quan đến chức 22 Liên quan đến chức 29 Liên quan đến chức 42 Một số module bổ trợ khác 45 SVTH: Trần Vĩnh Trung viii Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường Danh sách hình ảnh CHƯƠNG Hình 1.1: Nhiệm vụ đề tài .2 Hình 1.2: Minh họa vấn đền liên biên mảnh đồ 12 CHƯƠNG Hình 1.1: Đồ thị có hướng 20 Hình 1.2: Đồ thị vơ hướng 21 Hình 1.3: Quãng đường 23 Hình 1.4: Chu trình 24 Hình 1.5: Minh họa liên thơng đồ thị .25 Hình 1.6: Mạng 26 Hình 1.7: Ma trận quan hệ nút cung cho ví dụ mạng Hình 1.6 .26 Hình 1.8: Ma trận quan hệ nút - nút cho ví dụ mạng Hình 27 Hình 1.9: Danh sách liên kết cho ví dụ mạng Hình 29 Hình 2.1: Khoa học thông tin địa lý khoa học liên ngành 32 Hình 2.2: Minh họa cấu trúc mạng 33 Hình 2.3: Minh hoạ cấu trúc mạng 34 Hình 2.4: Mơ tả Point multipoint 36 Hình 2.5: Mơ tả Network junction feature 36 Hình 2.6: Mơ tả Line .37 Hình 2.7: Mơ tả Network edge feature 37 Hình 2.8: Mô tả Simple Network edge feature .38 Hình 2.9: Mơ tả Complex Network edge feature 38 Hình 2.10: Mơ tả cấu trúc arc - node 39 Hình 2.11: Mô tả cấu trúc polygon - arc .39 Hình 2.12: Mơ tả cấu trúc left - right 39 Hình 2.13: Mơ tả mơ hình mạng 40 Hình 2.14: Mơ tả mơ hình mạng hình học 42 Hình 2.15: Mơ tả mơ hình mạng luận lý .43 Hình 2.16: Mơ tả mối quan hệ mạng hình học mạng luận lý 43 Hình 2.17: Mô tả cấu trúc tổ chức mạng luận lý 44 SVTH: Trần Vĩnh Trung ix Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Cơng Cường Hình 3.1: Ví dụ tập mờ 46 Hình 3.2: Ví dụ hàm thuộc 47 Hình 3.3: Ví dụ mặt cắt alpha (α-cut) tập mờ A 48 Hình 3.4: Minh họa đính lý phân rã thứ 50 Hình 3.5: Minh họa định lý phân rã thứ .51 Hình 3.6: Ví dụ số mờ biểu diễn khái niệm “lân cận giá trị r = 1.5” 53 Hình 3.7: Minh họa so sánh số thực, đoạn số thực với số mờ 54 Hình 3.8: Minh họa số mờ biểu diễn cấu trúc topology .55 CHƯƠNG Hình 1.1 Mạng lưới .60 Hình 1.2 Giải thuật Dijkstra GIS 61 Hình 1.3 Minh họa mặt cắt alpha đặc biệt 62 Hình 1.4 Minh họa vấn đề cộng số mờ biểu diễn cấu trúc topology .63 Hình 3.1 Cộng số mờ 67 Hình 3.2 Lưu đồ giải thuật cộng số mờ A B 69 Hình 3.3 Vị trí tương đối số mờ 71 Hình 3.4 Số mờ A B với mặt cắt α 72 Hình 3.5 Giải thuật so sánh số mờ theo cách .73 Hình 3.6 Giải thuật so sánh số mờ theo cách .75 Hình 3.7 Các đoạn thẳng tạo cắt số mờ A B mặt cắt α 77 Hình 3.8 Trường hợp 77 Hình 3.9 Trường hợp 77 Hình 3.10 Trường hợp 78 Hình 3.11 Trường hợp 78 Hình 3.12 Cách tính hệ số ρ(A>B)α 79 Hình 3.13 Giải thuật so sánh số mờ theo cách 81 Hình 4.1 Mơ hình ý niệm liệu hỗ trợ phân tích mạng 84 CHƯƠNG Hình 3.1 Quy trình phân tích mạng tìm đối tượng gần 89 Hình 3.2 Giao diện chương trình phân tích mạng mờ 90 Hình 4.1: Dịng chảy liên quan đến vị trí khảo sát 91 SVTH: Trần Vĩnh Trung x Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường aPointList = aFuzzyNum.AsList.Get(0) for each aAddVertex in aAddVertexList aAddPointIndex = aAddVertex.Get(0) aAlongValue = aAddVertex.Get(1) if (aAddPointIndex >= (aPointList.Count - 1)) then continue end aTempPolyline = Polyline.Make({{aPointList.Get(aAddPointIndex), aPointList.Get(aAddPointIndex+1)}}) aNewVertex = aTempPolyline.Along(aAlongValue) aPointList.Insert(aNewVertex) aPointList.Shuffle(aNewVertex, aAddPointIndex+2) end aFuzzyNum = Polygon.Make({aPointList}) aFNFTab.SetValue(aFNFtab.FindField("Shape"), aFuzzyNumRec, aFuzzyNum) end end if (aDelVertexList.Count > 0) then for each aFuzzyNumRec in aFNBitmap aFuzzyNum = aFNFTab.ReturnValue(aFNFTab.FindField("Shape"), aFuzzyNumRec) aPointList = aFuzzyNum.AsList.Get(0) aBitmapOfPointList = {} for each i in (aPointList.Count-1) aBitmapOfPointList.Add(0) end for each aDelVertex in aDelVertexList aDelPointIndex = aDelVertex.Get(0) aBitmapOfPointList.Set(aDelPointIndex, 1) end aNewPointList = {} for each i in (aPointList.Count-1) if (aBitmapOfPointList.Get(i) = 0) then aNewPointList.Add(aPointList.Get(i).Clone) end end aPointList = aNewPointList.Clone aFuzzyNum = Polygon.Make({aPointList}) aFNFTab.SetValue(aFNFtab.FindField("Shape"), aFuzzyNumRec, aFuzzyNum) end end if (aMoveVertexList.Count > 0) then for each aFuzzyNumRec in aFNBitmap aFuzzyNum = aFNFTab.ReturnValue(aFNFTab.FindField("Shape"), aFuzzyNumRec) aPointList = aFuzzyNum.AsList.Get(0) for each aMoveVertex in aMoveVertexList aMovePointIndex = aMoveVertex.Get(0) aDxValue = aMoveVertex.Get(1) aDyValue = aMoveVertex.Get(2) SVTH: Trần Vĩnh Trung B - 35 Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường aPoint = aPointList.Get(aMovePointIndex) aPoint = aPoint.Move(aDxValue, aDyValue) aPointList.Set(aMovePointIndex, aPoint) end aFuzzyNum = Polygon.Make({aPointList}) aFNFTab.SetValue(aFNFtab.FindField("Shape"), aFuzzyNumRec, aFuzzyNum) end end aFNFTab.SetEditable(FALSE) ' Refresh hop thoai soan thao so mo aDialog.Close aDialog.Open ' **************************************** ' Author: Tran Vinh Trung ' Date: ' Name: vt.dlgEditFuzzyNum.cmdMovePoint.Click ' Title: ' Topic: ' Description: ' Requires: ' Input: Self.aDialog.GetObjectTag = {aEditorView (View), aFuzzyNumGraphic (Graphic Point)} ' Output: ' End ' **************************************** aDialog = Self.GetDialog aTxtID = aDialog.FindByName("txtID") aLstPoints = aDialog.FindByName("lstPoints") aRadCurrentRec = aDialog.FindByName("radCurrentRec") aTxtAlong = aDialog.FindByName("txtAlong") aTxtDx = aDialog.FindByName("txtDx") aTxtDy = aDialog.FindByName("txtDy") aCmdAccept = aDialog.FindByName("cmdAccept") aCmdSkip = aDialog.FindByName("cmdSkip") aCmdAddPoint = aDialog.FindByName("cmdAddPoint") aCmdDeletePoint = aDialog.FindByName("cmdDeletePoint") aCmdMovePoint = aDialog.FindByName("cmdMovePoint") aCmdCancel = aDialog.FindByName("cmdCancel") aCmdOK = aDialog.FindByName("cmdOK") SVTH: Trần Vĩnh Trung B - 36 Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường aCmdAccept.SetEnabled(true) aCmdSkip.SetEnabled(true) aTxtDx.SetEnabled(true) aTxtDy.SetEnabled(true) aTxtDx.SetText(10.AsString) aTxtDy.SetText(10.AsString) aCmdAddPoint.SetEnabled(false) aCmdDeletePoint.SetEnabled(false) aCmdMovePoint.SetEnabled(false) aCmdCancel.SetEnabled(false) aCmdOK.SetEnabled(false) ' **************************************** ' Author: Tran Vinh Trung ' Date: ' Name: vt.dlgEditFuzzyNum.cmdDeletePoint.Click ' Title: ' Topic: ' Description: ' Requires: ' Input: Self.aDialog.GetObjectTag = {aEditorView (View), aFuzzyNumGraphic (Graphic Point)} ' Output: ' End ' **************************************** aDialog = Self.GetDialog aTxtID = aDialog.FindByName("txtID") aLstPoints = aDialog.FindByName("lstPoints") aRadCurrentRec = aDialog.FindByName("radCurrentRec") aTxtAlong = aDialog.FindByName("txtAlong") aTxtDx = aDialog.FindByName("txtDx") aTxtDy = aDialog.FindByName("txtDy") aCmdAccept = aDialog.FindByName("cmdAccept") aCmdSkip = aDialog.FindByName("cmdSkip") aCmdAddPoint = aDialog.FindByName("cmdAddPoint") aCmdDeletePoint = aDialog.FindByName("cmdDeletePoint") aCmdMovePoint = aDialog.FindByName("cmdMovePoint") aCmdCancel = aDialog.FindByName("cmdCancel") aCmdOK = aDialog.FindByName("cmdOK") ' Xu ly xoa vertex -bDeleteIt = msgbox.YesNo("Bạn có ĐồNG ý xoá đỉnh chän kh«ng?", "L-u ý", false) SVTH: Trần Vĩnh Trung B - 37 Luận văn thạc sĩ GVHD: PGS.TSKH Bùi Công Cường if (bDeleteIt = false) then return nil end aTagList = aDialog.GetObjectTag aEditorView = aTagList.Get(0) aFuzzyNumGraphic = aTagList.Get(1) aFuzzyNum = aFuzzyNumGraphic.GetShape aDelVertexList = aTagList.Get(3) anOriginVertexIndexList = aTagList.Get(5) aDelVertex = {} if (aLstPoints.GetList.Count