KHOA CNTT – ĐH KHTN - 1 -
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM

TRẮC NGỌC ĐĂNG - 0012029
BÙI THẾ TÀI - 0012086

Đề tài:
- 2 -
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM

TRẮC NGỌC ĐĂNG - 0012029
BÙI THẾ TÀI - 0012086
Đề tài:KẾT HỢP CHUẨN OPENGIS VÀ HỆ QUẢN TRỊ CƠ
SỞ DỮ LIỆU ĐỂ GIẢI QUYẾT MỘT SỐ BÀI TOÁN
TỐI ƯU TRÊN MẠNG GIAO THÔNG THÀNH PHỐ.
- 3 -

Lời cảm ơn
Chúng em xin chân thành cảm ơn toàn thể quý thầy cô khoa Công Nghệ
Thông Tin trường Đại học Khoa học Tự nhiên TP.HCM đã tận tình giúp đỡ
và truyền đạt những kiến thức quý báu cho chúng em trong suốt thời gian
học tập tại trường.
Đặt biệt, chúng em xin dành sự biết ơn trân trọng nhất gởi đến thầy Th.Sĩ
NGUYỄN MINH NAM, là người đã trực tiếp hướng dẫn và độ
ng viên chúng
em trong suốt thời gian thực hiện luận văn tốt nghiệp này.
Cuối cùng, chúng tôi xin cám ơn tất cả các bạn học đã giúp chúng tôi giải
quyết những vướng mắc nho nhỏ trong quá trình làm việc.
Xin cảm ơn tất cả.
-Trắc Ngọc Đăng – Bùi Thế Tài


3.2. Bài toán TSP ....................................................................................................74
3.3. Thuật giải Lin-Kernighan nguyên thuỷ (1971)................................................77
3.4. Thuật giải Lin-Kernighan cải tiến (2002)........................................................87
3.5. Các thủ thuật cải tiến thuật giải L-K trong quá trình cài đặt .........................108
3.6. Các cấu trúc dữ liệu quan trọng của thuật giải Lin-Kernighan......................110
3.7. Kết chương.....................................................................................................112
THUYẾT MINH CHƯƠNG TRÌNH THỬ NGHIỆM.........................................113
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN............................................................1
19

PHỤ LỤC..............................................................................................................121
A. BÀI TOÁN TÌM ĐƯỜNG ĐI NGẮN NHẤT GIỮA 2 ĐIỂM .......................122
B. BÀI TOÁN XỬ LÝ ĐIỀU PHỐI CẤP THỜI (EMERGENCY).....................123

KHOA CNTT – ĐH KHTN - 5 -
C. GI
ỚI THIỆU VỀ NÚT ẢO. .......................................................................................124
TÀI LIỆU THAM KHẢO ....................................................................................127
- 6 -
Lời mở đầu
Trong cuộc sống hiện nay, khi xã hội phát triển, con người luôn bị đòi
hỏi cao về thời gian. Do đó, yếu tố thời gian được xem là yếu tố quyết định
trong mọi sinh hoạt hằng ngày. Điều này đã cho chúng ta thấy thời gian đã
quý nay lại càng quý hơn.
Thực tế đã cho chúng ta thấy, có những việc đòi hỏi rất nghiêm khắc
về thời gian, mà nếu không
đáp ứng được có thể sẽ có một hậu quả nghiêm
trọng, ảnh hưởng đến tính mạng con người cho đến tiêu hao về của cải vật
chất. Ví dụ như: các hoạt động phòng cháy chữa cháy, cảnh sát phản ứng
nhanh 113, đề xuất một lộ trình thích hợp cho một lần phân phối sản phẩm
từ công ty mẹ đến các đại lý, lập lịch cho một thiết bị vận hành...Như
ng làm
sao để ta biết phải điều phối các hoạt động đó thế nào thì hợp lý nhất; làm
sao ta có được một lộ trình tối ưu với rất nhiều điểm phải đến trong một
khoảng thời gian tương đối ngắn mà ta không phải đợi dài cổ tính, toán suy
nghĩ cho mệt óc. Đây rõ ràng là các vấn đề nan giải.
Hiện nay, với sự phát triển vũ bão của khoa học công nghệ, đặ
c biệt là
ngành Công Nghệ Thông Tin, thì người ta phần nào được hệ thống máy tính
trợ giúp giải quyết những vấn đề trên. Với hệ thống GIS (hệ thống thông tin
địa lý), cùng GPS (hệ thống định vị toàn cầu) thì các vấn đề điều phối xử lý
cấp thời dường như có thể thực hiện một cách tốt đẹp.
Xuất phát từ những yêu cầu trên, nhằm hạn chế mọi chi phí không
đáng có,
những khoảng thời gian quý báu sẽ không phải mất đi nhiều, chúng em đã
thử nghiệm và áp dụng các chuẩn của OpenGIS (xu thế của ngày nay khi các
KHOA CNTT – ĐH KHTN - 8 -
1.1 Hệ thống thông tin điạ lý (GIS – Geographic Information
System) là gì ?
Hệ thống thông tin điạ lý (Geographical Information System – GIS) là sự
kết hợp giữa công nghệ bản đồ số hoá với công nghệ quản trị cơ sở dữ liệu cho
phép việc truy xuất, xử lý thống kê một khối lượng lớn thông tin khổng lồ, đa
dạng nhanh chóng và rất trực quan ….. Công nghệ GIS với khả năng phân tích
không gian một cách chính xác, nhanh chóng đã được ứng dụng trong rất nhiều
ngành khác nhau phục vụ cho việc quản lý vĩ mô.
Hệ
thống thông tin điạ lý đóng vai trò như một kỹ thuật tổ hợp. Hệ thống
thông tin điạ lý đã tiến hoá bởi sự liên kết một số các kỹ thuật tổ hợp rời rạc vào
thành một tổng thể hơn là sự cộng các thành phần của chúng lại.

liệu được cấu thành từ thông tin, các thông tin thường không sử dụ
ng được trực
tiếp mà phải thông qua một hệ thống các công cụ truy xuất, tái tạo lại đối tượng
thế giới thực mà người dùng quan tâm. Một đối tượng được lưu trữ trong cơ sở dữ
liệu dưới dạng các thực thể hình học, người dùng sẽ dùng phải tái tạo lại đối tượng
ấy thông qua các dữ liệu hình học này.
Như vậy dữ liệu là rất
đa dạng, chúng có mang tính không gian, thời gian,
được gọi là dữ liệu địa lý.
Định nghĩa: Dữ liệu địa lý là các dữ liệu số mô tả các đối tượng trong thế
giới thực.
Dữ liệu điạ lý được tổ chức thành hai nhóm thông tin chính, đó là:
1/ Nhóm thông tin về phân bố không gian.
2/ Nhóm thông tin về thuộc tính của đối tượng.
1.2.2 Mô hình bản đồ chồng xếp:

Một trong những phương pháp chung nhất của tổ chức dữ liệu điạ lý là tổ
chức theo bản đồ và các lớp thông tin. Mỗi lớp thông tin là một biểu diễn của dữ
liệu theo một mục tiêu nhất định, do vậy nó thường là một hoặc một vài dạng của
thông tin. Ví dụ để nghiên cứu nguồn tài nguyên thiên nhiên, điạ chất, các điều
kiện vật lý lớp dướ
i đất, sử dụng đất, kênh rạnh……Người ta tách chúng thành các
lớp.

KHOA CNTT – ĐH KHTN KHOA CNTT – ĐH KHTN - 11 -
3. Thành phần phi không gian.
4. Thành phần không gian.
Khoá :
là mã số duy nhất cho thực thể để phân biệt thực thể này với thực thể
khác.
Định vị:
Chỉ ra vị trí của thực thể.
Thành phần phi không gian:
Là những thuộc tính riêng cho từng thực thể như
tỷ lệ, khoảng, định danh ….
Thành phần không gian :
Các đối tượng tư nhiên bên ngoài được chuyển vào
máy tính để quản lý theo hai cách sau :
1. Raster.
2. Vectơ.
Mô hình vectơ
: tường được biểu diễn duới dạng điểm, đường và vùng . Vị
trí không gian của một thực thể được xác định bởi một hệ toạ độ thống nhất toàn
cầu. Một thực thể được xác định bởi cặp toạ độ (X,Y) và các thuộc tính khác như :
kiểu điểm, màu, hình dạng .


các máy tính cá nhân hay của công ty. Máy quét sẽ lưu trữ lại các hình ảnh của
bản đồ giấy dưới hình thức số và hiển thị chúng trở lại màn hình. Việc quét hình
ảnh từ bản đồ giấy tương đối đơn giản và nhanh chóng, tuy nhiên phương pháp
này lại không thể cung cấp thuộc tính của các đối tượng tự nhiên như đi
ạ chỉ của
một toà nhà hay ngày thành lập cuả một sân vận động nào đó. Dữ liệu có được từ
những phương pháp này thường dưới dạng raster cho kích thước rất lớn.
Phương pháp số hoá:

Kỹ thuật này đòi hỏi phải cung cấp các thiết bị chuyên ngành. Bản đồ
nguồn sẽ được trãi bề mặt ngang, một con trỏ sẽ xác định tọa độ các điểm tạo nên
hình dạng bản đồ, sau quá trình số hoá, thuộc tính của các đối tượng mới được
thêm vào. Phương pháp này đòi hỏi nhiều thời gian và nguồn dữ liệu có được từ
kỹ thuật này dưới hình thứ
c Vectơ.
Phương pháp vectơ hoá : KHOA CNTT – ĐH KHTN - 13 -
Một vài hệ thống máy tính chuyên nghiệp có thể chuyển đổi dữ liệu Raster
sang dạng dữ liệu Vectơ. Phương pháp này cho tốc độ nhanh do tính tự động KHOA CNTT – ĐH KHTN - 14 -

CHƯƠNG 2
GIỚI THIỆU OPENGIS


thuật số nào sử dụng geodata, lập mô hình, phiên dịch và sử dụng thông tin Trái
Đất gồm hệ thống thông tin địa lý (GI), hệ thống thông tin đất đai (LIS), việc xử lý
ảnh và tạo ảnh Trái đấ
t, việc chứa geodata trong tất cả các loại cơ sở dữ liệu,
những phương thức khảo sát dạng kĩ thuật số, sự định hướng, khí tượng học, địa
chấn học,v v..
“Interoperable geoprocessing” chỉ khả năng của một hệ thống kĩ thuật số để
:
- Tùy thích trao đổi tất cả các loại thông tin không gian về Trái đất
,về các đối tượng và hiện tượng
ở trên ,bên trên và dưới bề mặt Trái đất .
- Chạy các phần mềm có khả năng thao tác các thông tin như vậy
qua mạng một cách hợp tác.
2.2. TỔNG QUAN VỀ OPENGIS :
2.2.1. Làm quen với OpenGIS Specification :
2.2.1.1. Khái niệm:

Đặc tả OpenGIS (OpenGIS Specification) , một đặc tả toàn diện của một bộ
khung phần mềm cho các truy cập phân tán đến geodata và những tài nguyên
geoprocessing . Đặc tả này cung cấp cho các nhà phát triển phần mềm trên thế giới
một khuôn mẫu giao diện chung cặn kẽ để viết các phần mềm hoạt động chung với

KHOA CNTT – ĐH KHTN


2.2.1.2.
Ưu điểm:
Người phát triển ứng dụng có thể dễ dàng và linh hoạt hơn để:
• Viết phần mềm để truy cập geodata.
• Viết phần mềm để truy cập những tài nguyên geoprocessing .

KHOA CNTT – ĐH KHTN - 17 -
• Sửa đổi những ứng dụng theo nhu cầu người dùng cụ thể, tích hợp phi
không gian và không gian.
• Chọn một môi trường phát triển.
• Cung cấp những ứng dụng trên những nền tảng đa dạng.
• Sử dụng lại mã geoprocessing
Nhà quản lý thông tin linh hoạt hơn đối với:
• Truy cập và / hoặc phân phối geodata
• Cung cấp những khả năng geoprocessing tới những khách hàng
•
Tích hợp Dữ liệu địa lý và sự xử lý vào một kiến trúc tính toán liên hợp
• Chọn những nền thích hợp - kiểu máy tính cá nhân, kiểu máy chủ, và kiểu
nền tính toán phân tán ( CORBA, OLE / COM, DCE, ….)
• Phù hợp với người dùng với những công cụ geoprocessing đúng (và được
địng cỡ đúng)

những dịch vụ được cần để :
- Truy nhập và xử lý những kiểu định nghĩa đồ họa địa lý trong Mô
hình Geodata Mở.
- Cung cấp những khả năng để chia sẻ geodata bên trong những cộng
đồng người dùng mà sử dụng một tập hợp chung những định nghĩa đặc tính
địa lý và biên dịch giữa những cộng đồng khác nhau những ngườ
i sử dụng
những tập hợp định nghĩa đặc tính địa lý khác nhau.
2.2.2.3. Một mô hình những cộng đồng thông tin (Information
Communities Model ) : Dùng Mô hình Geodata Mở và những dịch vụ
OpenGIS trong một sơ đồ để thiết lập :
- Một cách thức cho một cộng đồng những nhà sản xuất geodata và
những người dùng đã chia sẻ một tập hợp chung những định nghĩa đặc tính địa lý
nhằm bảo trì thực s
ự có hiệu quảnh định nghĩa này và để lập danh mục, chia sẻ
những tập dữ liệu thích ứng những định nghĩa đó.
- Mét cách chính xác tối ưu và hiệu quả cho những cộng đồng khác
nhau những người dùng và những nhà sản xuất geodata để chia sẻ geodata mặc
những tập hợp định nghĩa đặc tính địa lý khác nhau của họ. Cho ví dụ, những kĩ s-
ư, những nhà địa chấ
t, nhà nông học có thể tìm kiếm để chia sẻ dữ liệu đất dù họ
mô tả đặc điểm các kiểu đất khác nhau theo những mục tiêu nghề nghiệp khác
nhau. Những mô hình cộng đồng thông tin định nghĩa một sơ đồ nhằm tự động
biên dịch giữa những từ điển đặc tính địa lý khác nhau.
2.2.3. Đặc điểm :

OpenGIS Specification thiết lập một nền tảng công nghệ chung trên
đó ngành công nghiệp phần mềm có thể xây dựng những thành phần phần mềm và
ứng dụng geoprocessing có tính :
Interoperable (Hoạt động liên hợp)- OpenGIS Specification cung cấp

sử dụng những quy tắc và những thủ tục chắc chắn và logic cho việc sử dụng
geodata và các dịch vụ geoprocessing. Geodata không cần thiết và sự phức tạp
geoprocessing được dấu bởi người phát triể
n ứng dụng.
Portable (Khả chuyển) - OpenGIS Specification là sự độc lập của môi
trường phần mềm, nền tảng phần cứng và mạng.
Cooperative (Hợp tác) - OpenGIS Specification hỗ trợ tính toán dùng
chung và những tài nguyên dữ liệu dùng chung. Công nghệ OpenGIS có thể dễ
dàng được kết hợp với công nghệ thông tin khác.
Scalable (Biến đổi được) – Phần mềm trên nền OpenGIS Specification th-
ường gồm có những thành phần phần mềm geoprocessing "cắm vµ chạy" mà có
th
ể được cấu hình cho bất kì ứng dụng geoprocessing nào hoặc môi trường tính
toán chuẩn, bất chấp kích thước cơ sở dữ liệu.

KHOA CNTT – ĐH KHTN - 20 -
Extensible (Dể mở rộng) - OpenGIS Specification có thể đồng hóa những
phần mềm geoprocessing và kiểu geodata mới, và có thể điều tiết những công
nghệ mới mà OpenGIS Specification phụ thuộc trên đó , như những nền tính toán
phân tán, khi chúng trở thành sẵn có.
Compatible (Tương thích) - OpenGIS Specification giữ gìn sự đầu tư của


KHOA CNTT – ĐH KHTN - 21 -
OpenGIS Implementation Specification : Những Implementation
Specification là những đặc tả nền tảng công nghệ rõ ràng cho sự cài đặt những
giao diện lập trình ứng dụng phần mềm chuẩn công nghiệp. Đó là những đặc tả
phần mềm chi tiết để cài đặt các bộ phận của OpenGIS Abstract Specification trên
những hệ tính toán phân tán đặc biệt như OLE / COM và CORBA. Ủy ban Kỹ
thuật OGC phát hành Những yêu cầu cho những đề nghị ( RFPs), và đáp lại những
đi
ều đó, những thành viên hợp thành đội để trình bày OpenGIS Implementation
Specification cho Ủy ban kỹ thuật và Ủy ban quản lý OGC xem lại. Ngoài việc
cho phép Tính vận hành với nhau (Interoperability) với mỗi DCP, những nhóm
này cố gắng cung cấp tính năng Interoperability cực đại giữa các DCPs.
2.3. OPENGIS ABSTRACT SPECIFICATION :
Gồm hai mô hình bắt nguồn từ phương pháp phân tích và thiết kế đối tượng
Syntropy [1] :
- Mô hình đầu tiên đơn giản hơn được gọi là Mô hình bản chất (Essential
Model) và mục đích của nó là thiết lập sự kết nối khái niệm của việc thiết kế hệ
thống hoặc phần mềm tới thế giới thực. Essential Model là sự mô tả thế giới thực
hoạt động ra sao. Nó giải thích những thu
ật ngữ thế giới thực : các đối tượng, giao
diện, hành vi, giới hạn,..Các lược đồ, phân tích trường hợp sử dụng (use-case
analysis), các mô hình từ ngữ hay đồ họa có cấu trúc được sử dụng để giúp cho
việc hiểu rõ những thông điệp.

bản bằng việc geoprocessing, mô tả chín cấp độ trừu tượng hóa :
 Real World (Thế giới th
ực). Đây là thế giới thực sự với tất cả sự phức
tạp và hỗn loạn của nó.
 Conceptual World (Thế giới khái niệm). Là thế giới các thứ chúng ta
biết và đặt tên.
 Geospatial World (Thế giới không gian địa lý). ỳa thế giới của những
bản đồ và GIS (Hệ thống thông tin địa lý), trong đó chúng ta lựa chọn
các thứ cụ thể trong thế giới khái niệm để
biểu diễn theo một cách có
tính chất tượng trưng và trừu tượng trong những bản đồ và geodata.
 Dimensional World (Thế giới có kích thước). Đây là thế giới
Geospatial sau khi nó đã được đo đạc để có sự chính xác về vị trí và
hình học.
 Project World (Thế giới đề án). Là một mảnh được chọn của thế giới
geospatial hữu hướng – cho ví dụ, những lớp thuộc chủ đề nhất
định bên
trong một GIS – mà được lập cấu trúc ngữ nghĩa và nói cách khác cho
một mục đích, nghề nghiệp, qui định, hoặc miền công nghiệp đặc thù.
 OpenGIS Points (Điểm OpenGIS). Làm sao những điểm được định
nghĩa, tổng quát và cho một Project World đặc biệt, theo một cách mà
tất cả các hệ thống phần mềm có thể liên quan đến.

KHOA CNTT – ĐH KHTN
- 24 -
chia sẻ những thông tin không gian địa lý diễn ra trong đó ỏ một mức tự nhiên,
không khó khăn gì vế mặt ngữ nghĩa .
2.3.1.1. Các khái niệm :
 Open Geodata Model : Mỗi hệ thống geoprocessing đều có một mô
hình geodata phục vụ như là một chỉ dẫn cho việc thể hiện những
đặc điểm và hiện tượng của Trái Đất dưới dạng kĩ thuật số. Open
Geodata Model là một mô hình geodata vũ trụ cho phép nhữ
ng giao
diện interoperability được xác định, ám chỉ những phần của
Essential Model tập trung vào dữ liệu : hình học, những hệ thống
tham chiếu không gian, những sự biến đổi, những hình dạng, những
cấu trúc hình học vị trí, địa thế học topology, những cấu trúc nổi
tiếng từ đó những hình học đặc tính được xây dựng, những quy mô
bao phủ, những hàm phạm vi giản đồ, những hàm phát sinh bao phủ,
…. OpenGIS Specification chuẩn hóa cách mà các hệ thống đó
truyền thông những loại thông tin này.

 Features and Feature Collections ( Tính năng và Tập hợp tính năng
): Là cấp độ cuối cùng của Essential Model.
9 Một Feature Collection là đơn vị cơ bản, nguyên tử của quan hệ
geospatial trong một môi trường hệ thống máy tính nối mạng, là
đơn vị thương mại trong một giao dịch chia sẻ thông tin
geospatial, khoản mục geospatial nhỏ nhất mà được trao đổi qua
sự quản lý của quan hệ geospatial, là đối tượng nguyên thuỷ của
thao tác và sự khai thác bên trong một môi trường xử lý phần
mềm geospatial. Một Feature Collections có thể chứa một
Feature đơn lẻ hay nhiều Feature .

ủa việc lập mô hình dữ liệu địa lý. Những thực thể và hiện tượng
không đầy đủ ý nghĩa trong một ngữ cảnh geoprocessing trừ phi
chúng được biểu diễn dướí dạng một mô hình cố định chúng vào
thời gian và đặt chúng trong mối liên hệ với bề mặt của Trái đất.
Những hệ thống tham chiếu không gian định nghĩa làm sao những
tọa độ được thể hiện bên trong dạng hình h
ọc của một đặc tính.
 Features and Coverages (Những đặc tính và phạm vi che phủ):
Những yếu tố địa lý chia thành hai phạm trù rộng, là những thực thể
và hiện tượng :
- Những thực thể là những đối tượng rời có thể nhện ra được,
có những ranh giới được xác định tương đối rõ hoặc phạm vi không gian. Ví dụ :
những tòa nhà, dòng sông, ...
- Hiện tượng thay đổi qua không gian và không có phạm vi
cụ thể
. Ví dụ : nhiệt độ, thành phần đất …. Một giá trị hoặc sự mô tả của một hiện
tượng chỉ có ý nghĩa tại một điểm cụ thể trong không gian ( và có thể cả thời gian
). Ví dụ : Hiện tượng được gọi là nhiẹt độ chỉ có giá trị cụ thể tại vị trí xác định.