Trang 0 ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
LÊ QUANG LỢI
ỨNG DỤNG CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI
TRONG HỆ THỐNG THÔNG TIN ĐỊA LÝ LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2013
HỌC VIÊN: LÊ QUANG LỢI
HƯỚNG DẪN KHOA HỌC:
PGS.TS. NGUYỄN HẢI CHÂU HÀ NỘI - 2013
Trang 2 Mục lục
Lời mở đầu 5
Chương 01: Giới thiệu bài toán tìm đường đi 7
1.1 Giới thiệu bài toán TSP 7
1.1.1 Bài toán TSP 7
1.1.2 Một số giải thuật giải quyết bài toán TSP 8
1.2 Giải thuật Genertic TSP 11
1.2.1 Giới thiệu giải thuật GA 11
1.2.2 Giải thuật GA TSP 14
1.3 Ứng dụng của TSP trong hệ thống thông tin địa 15
Chương 02: Hệ quản trị CSDL không gian 16
2.1 Hệ thống thông tin địa lý 16
2.1.1 Giới thiệu về hệ thống thông tin địa lý 16
2.1.2 Kiến trúc cơ bản một hệ thống thông tin địa lý 17
2.2 CSDL không gian PostGres và PostGIS 19
2.2.1 Giới thiệu 19
2.2.2 Kiến trúc PostGres 20
2.2.3 Kiểu dữ liệu không gian 21
2.2.4 Hàm hỗ trợ xử lý dữ liệu trong Gis 22
2.2.5 Truy vấn dữ liệu không gian 22
Extended Markup Language
3
GEOS
Geometry Engine - Open Source
4
GIS
Geographic Information System
5
WKT
Well-Know Text
6
HQT CSDL
Hệ quản trị CSDL
7
SQL
Structed Query Language
8
TSP
Traveling Salesman Problem
9
GA
Genetic Algorithm
10
OSM
Open Street Map
Danh mục bảng
TT
Tên bảng
Trang
1
5
Hình 2.5 Kiến trúc PostGres
19
6
Hình 2.6 Dữ liệu Raster và cách số hóa.
20
7
Hình 3.1 bản đồ dữ liệu mẫu
34 Trang 4
Lời cam đoan
Tôi xin cam đoan luận văn “ỨNG DỤNG CÁC THUẬT TOÁN TÌM ĐƯỜNG ĐI
TRONG HỆ THỐNG THÔNG TIN ĐỊA LÝ” được thực hiện của tác giả dưới sự hướng
dẫn của thầy PGS.TS Nguyễn Hải Châu. Toàn bộ nội dung được trình bày không hề có sự
sao chép từ các luận văn khác. Các kiến thức, hình ảnh, trích dẫn để được chỉ rõ nguồn tài
liệu tham khảo một cách cụ thể và rõ ràng.
Nếu có nội dung nào trong luận văn vi phạm các quy định đề ra của nhà trường tôi xin
hoàn toàn chịu trách nhiệm theo đúng các quy định đề ra.
Hà nội, ngày … Tháng … năm 2013
Người cam đoan Lê Quang Lợi
Trang 5
Sau một thời triển khai luận văn tác giả đã hoàn thành được các hạng mục đã thống nhất
với giảng viên hướng dẫn với kết quả tốt và đúng tiến độ đề ra.
Trang 6
Tóm tắt kết quả đạt được của luận văn
- Về Cơ sở lý thuyết: Luận văn đã thực hiện
o Tìm hiểu được các nội dung cơ sở lý thuyết theo mục tiêu đề ra và phần lý
thuyết do Giảng viên hướng dẫn giao phó.
o Xây dựng cuốn báo cáo toàn văn và cuốn báo cáo tóm tắt luận văn
- Về Thực nghiệm: Luận văn đã thực hiện được
Cài đặt thành công các thư việc xây dựng nên môi trường của một hệ thống
thông tin địa địa lý cho thực nghiệm bài toán
Cấu hình CSDL cho phép triển khai dữ liệu mẫu
Triển khai dữ liệu mẫu: dữ liệu OSM từ hệ thống OpenStreetMap
Thực nghiệm thành công các hàm cài đặt bài toán TSP trong thư viện
pgRouting
Xây dựng được ứng dụng web nhỏ cho truy vấn dữ liệu mẫu Trang 7
Chương 01: Giới thiệu bài toán tìm đường đi
1.1 Giới thiệu bài toán TSP
1.1.2 Một số giải thuật giải quyết bài toán TSP
a) Các thuật toán cơ bản giải quyết TSP:
- Thuật toán Branch-Bound [3]: Duyệt đồ thị theo chiều sâu (đi theo một nhánh),
chuyển nhánh mới khi gặp trường hợp giải quyết bài toán hoặc vượt giá trị ngưỡng (cận).
Luôn duy trì đường đi ngắn nhất và chỉ cập nhật khi tìm ra trường hợp giải quyết(đường
đi có chi phí thấp hơn) có đường đi tốt hơn.
Giải thuật:
T(k) = một tour với k thành phố;
Search(k,T(k-1));
if ( k = = n) { Ghi lại tour với cận B=độ dài tour; /*cập nhật cận*/ }
else {
Tìm k-1 khả năng để thêm k cho tất cả vị trí có thể có trong tour
Trong tất cả các tour tìm ra một tour sao cho độ dài < B hiện tại
Search(k+1,T(k)); /*tìm nhánh mới*/
}
Bản chất của thuật toán Branch-Bound là chuyển tìm kiếm trên đồ thị thành việc
tìm kiếm theo nhánh dựa trên cây tìm kiếm (Branch), với phương pháp tìm kiếm theo độ
sâu (bound) nhất định. Mỗi một nhánh là một trường hợp giải quyết bài toán. Nếu vượt
quá ngưỡng hoặc tìm thấy lời giải cho bài toán thì chuyển sang nhánh mới. Việc xây dựng
hàm đánh giá độ sâu quyết định đến thời điềm dừng thuật toán hoặc chuyển sang nhánh
mới để tìm lời giải tiếp theo. Từng bài toán cụ thể có thể cài đặt hàm đánh giá. Khi xây
dựng cần phải kiểm soát được độ sâu trong quá trình tìm kiếm. Nếu không kiểm soát
được hoặc để độ sâu không hợp lý sẽ làm cho thuật toán có lời giải kém hiệu quả, thậm trí
là không thể tìm ra được lời giải. Nếu để độ sâu lớn thì có nghĩa làm việc tìm kiếm sẽ có
chi phí tốn kém hơn như bùng nổ không gian bộ nhớ hoặc tăng các thao tác tính toán khi
thực hiện theo nhánh hiện tại. Thông thường các thuật toán tìm theo độ sâu được cài đặt
dễ nhất bằng chiếm lược dùng đệ qui.
C(r) ← j;
C(n) = 1; cost = cost + c (e, 1) Trang 10
Giải thuật: Nearest Neighbor Algorithm cho phép cài đặt bài toán TSP
Giải thuật cố gắng bổ xung một node mới vào trong tập các node hiện tại sao cho
đường đi tới nó là nhỏ nhất, sau đó kiểm tra tập node mới tạo ra có phải là một lời giài(
kết quả) hay không. Nếu không phải thì tiếp tục bổ sung node mới (node này chưa được
bổ sung). Thuật toán chỉ dừng khi hết node được bổ xung hoặc đã tìm ra lời giải. Thao tác
quan trọng là tìm ra node được bổ sung với đường đi tới nó là nhỏ nhất. Với bước đầu để
tìm ra node này sẽ gặp khó khăn với số lượng lớn các node chưa được bổ sung.
Bước 1 Bắt đầu với vector trọng số trong đồ thị G
Bước 2 Thêm node mới với đường đi tới nó là nhỏ nhất (cung) và node này chưa
được thêm.
Bước 3 Tiếp tục bước 02 cho tới khi có chu trình Hamilton.
- Thuật toán GA: là một trong các thuật toán được cài đặt và giải quyết bài toán TSP một
các rất hiệu quả. Với độ phức tạp thời gian và lưu trữ chấp nhận được. GA dựa trên ý
tưởng tiến hóa tự nhiên. Cho phép giải quyết bài toán TSP. GA được trình bày cụ thể
trong phần 1.2 của chương này.
b) So sánh giữa các thuật toán
Một số giải thuật giải quyết bài toán TSP với độ phức tạp thuật toán tương ứng được trình
bày trong bảng 1.1.
Bảng 1.1 Một số thuật toán và độ phức tạp tính toán [1]
tt
Thuật toán
1.2 Giải thuật Genertic TSP
1.2.1 Giới thiệu giải thuật GA
- Giới thiệu: Thuật toán GA (Genetic Algorithm) được ra dựa trên học tuyết tiến
hóa của Charles Darwin. Theo thuyết này con sinh ra được thừa hưởng các ưu điểm (gen)
vượt trội của cha và mẹ.
- Ý tưởng: Dựa trên tập dân số cha mẹ. Tiến hành lai tạo hai cá thể cha mẹ theo
gen để tạo ra thế hệ mới (đột biến). Thay thế thế hệ mới cho cha và mẹ nếu có đặc tính tốt
hơn cha mẹ, lặp lại quá trình lai tạo cho tới khi tìm ra tập dân số hoàn toàn mới. Đột biến
thể hiện thế hệ sau tốt hơn thế hệ trước.
- Thuật toán: [2]
B1[initial] Tạo ra dân số ngẫu nhiên của n nhiễm sắc thể.
B2 [Huấn luyện/fitness] Đánh giá hàm huấn luyện f(x) cho mỗi nhiễm sắc thể X cho tập
dân số.
B3 [Tạo dân số mới] Tạo tập dân số mới bằng các lặp đi lặp lại các bước sao cho tạo ra
tập dân số hoàn toàn mới
B3.1 [Lựa chọn/Selection] Chọn hai nhiễm sắc thể từ nhiễn sắc thể cha/mẹ từ tập
dân số với f(x) (Thể lực tốt hơn, cơ hội lựa chọn cao hơn)
B3.2 [Chéo hóa/Crossover] Chéo hóa nhiễn sắc thể từ cha mẹ để tạo ra con mới. Nếu
chéo hóa không được thực hiện thì con sẽ được sao y hệt đặc tính cha mẹ.
B3.3 [Đột biến/mutivation] xác xuất đột biến khi con được sinh ra (Tại vị trí nhiễn
sắc thể x).
B3.4 [Chấp nhận/acception] Đặt con mới vào tập dân số mới
B4 [Thay thế/Replation] Sử dụng dân số mới cho hoạt động tiếp theo của thuật toán
B5 [Thử] Nếu điều kiện cuối cùng là hài lòng, dừng lại, quay trở lại với giải thuật tốt nhất
cho dân số hiện tại.
B6 [Lặp lại] trở lại bước B2
Trang 12
bội phụ thuộc chia số lượng các thành phần chéo hóa và vị trí chéo hóa. Nếu số thành
phần càng lớn thì tạo con chung càng lớn và như vậy thao tác chéo hóa sẽ diễn ra với
nhiều thao tác hơn mới có thể kết thúc.
Hình 2.2: Chéo hóa bội
- Tính xác xuất đột biến: xây dựng hàm tính toán để xác định con chung sau khi
chéo hóa có đặc tính tốt hơn( trường hợp tốt hơn) để lựa chọn vào thay thế cha/mẹ trong
tập dân số ban đầu. Tiến trình thao tác đột biến sẽ thực hiện ngay sau tiến trình chéo hóa.
Việc xây dựng thao tác đột biến cần phải chú ý tới các yêu cầu nhỏ như
+) Trong quá trình chạy cho phép đạt tới bất kỳ điểm mong muốn nào.
+) Kiểm soát được kích thước nhiễn sắc thể và số lượng đem chéo hóa
+) Kiểm tra sự hợp lệ của gen: Gen được tạo thành phải được kết hợp từ gen
cha/mẹ và có độ dài bằng độ dài cha mẹ.
+) Xác suất đột biến phải được chạy từ mức thấp
b) Các thao tác phụ
- Biểu diễn tập dân số: Dựa trên các đặc tính cha mẹ sẽ đưa ra phương pháp biểu
diễn nhằm thuận tiện cho quá trình lựa chọn, lai tạo có kết quả tốt. Có thể biểu diễn dân
số theo các phương pháp dùng chuỗi nhị phân, các số nguyên hoặc chuỗi ký tự để biểu
diễn.
- Lựa chọn: lấy cặp cá thể cha mẹ ngẫu nhiên thực hiện thao tác lai tạo (chéo hóa).
- Hàm huấn luyện: thể hiện việc xây dựng hàm cho phép tỉ lệ lựa chọn cặp cha mẹ
thực hiện lai tạo gây đột biến với xác xuất thành công là cao nhất có thể. Hàm quyết định
Trang 14
tới số lượng thao tác lựa chọn cặp dân số cha/mẹ. Hàm huấn luyện sẽ được điều khiển bởi
+ Chéo hóa: Thực hiện lấy ra hai tuyến đường trong tập các tuyết đường ngẫu
nhiên.Coi các tuyến đường này như một Gen. Sau đó thực hiện thao tác chéo hóa
giữa hai tuyến đường để tạo ra các tuyến đường mới từ hai tuyến đường ngẫu
nhiên ở trên
+ Tính toán đột biến: Sau khi thực hiện chéo hóa xong. Tính lại độ dài đường đi
và thực hiện thay thế nếu có đường đi ngắn hơn.
1.3 Ứng dụng của TSP trong hệ thống thông tin địa
Trong thệ thống thông tin địa lý cụ thể là ứng dụng giải quyết một số bài toán liên quan
đến bản đồ. Bài toán TSP cho phép tìm ra đường đi (tour) tối ưu giữa các các điểm được
đánh dấu trên bản đồ. Có thể kể ra các bài toán có thể giải quyết.
- Tìm lộ trình ngắn nhất giữa các nơi giao hàng trên bản đồ cho nhân viên đi giao hàng
với chi phí (theo khoảng cách) là nhỏ nhất.
- Tìm ra lộ trình cho các tuyến xe bus trong một thàng phố.
- Tìm ra lộ trình lái xe cho các lái xe qua các điểm giao thông.
Trang 16
Chương 02: Hệ quản trị CSDL không gian
2.1 Hệ thống thông tin địa lý
2.1.1 Giới thiệu về hệ thống thông tin địa lý
- Hệ thống thông tin: là một thệ thống bao gồm phần cứng, phần mềm và mạng
máy tính được tổ chức theo kiến trúc nhất định nhằm giải quyết một vấn đề cụ thể một
cách hiệu quả. Một hệ thống tin có thể bao gồm thêm yếu tố con người thao tác trên hệ
thống. Một số hệ thống thông tin thể hiện về bản đồ địa lý, địa chất, không gian …
Đặc điểm hệ thống thông tin:
o Hệ thống thường lớn về khả năng tính toán, lưu trữ, xử lý, khả năng đáp ứng
nhanh, có thể mở rộng kiến trúc.
ích di động.
Hình 2.3 Kiến trúc hệ thống thông tin địa lý
Trang 18
2.1.3 Bản đồ
- Bản đồ (map): thể hiện đối tượng dữ liệu được biểu diễn một cách trực quan
thông qua vị trí của đối tượng. Các đối tượng luôn chứa các thông tin của nó và thông tin
về vị trí. Các phầm mềm hiển thị dữ liệu bản đồ cung cấp giao diện trực quan bằng hình
ảnh để biểu diễn dữ liệu như GoogleMap, BingMap, YahooMap…
- Dữ liệu bản đồ: là dữ liệu được tích hợp từ nhiều loại dữ liệu khác nhau. Để lưu
trữ người ta xếp dữ liệu cùng mục đích vào cùng một layer (tầng dữ liệu). Hình 2.2 Mô tả
biểu diễn dữ liệu bản đồ được theo các layer. Hình 2.4: Layer cơ bản trong dữ liệu bản đồ
o Realworld: bản đồ thật. Sự kết hợp của các layer khác
o Land: bản đồ thể hiện dữ liệu về đất đai và vùng miền theo biên giới
o Elevation: thể hiện vùng đất cao thấp theo độ cao.
o Parcels: thể hiện bản đồ theo lô đất/ vùng đất.
o Stresst: thể hiện đường đi trên bản đồ
Trang 19
- Khối Client: thiết lập giao diện tương tác người dùng, kết nối tới khối server và
chuyển tương tác với csdl thông qua server, hiển thị kết quả thông qua giao diện người
dùng.
- Khối server: Xử lý trên khối sever bao gồm các hoạt động như tạo môi trường,
giao diện quản lý dữ liệu, chấp nhận và quản lý các kết nối từ khối Client Hình 2.5 Kiến trúc PostGres
Trang 21
2.2.3 Kiểu dữ liệu không gian
a) Kiểu dữ liệu GIS [5]: Dữ liệu Vector và dữ liệu Raster là hai kiểu dữ liệu chính được
hỗ trợ trong PostGis. Kiểu dữ liệu thông thường trong PostGres mô tả thuộc tính dữ liệu
GIS.
- Vector: GIS hỗ trợ kiểu POINTS, LINES, POLYLINES,
o Point: Chỉ vị trí trên bản đồ theo chiều X, chiều Y
o Line: Đường đi gồm điểm đầu, điểm cuối
o Polylines: Tập các đường
o Region: Vùng dữ liệu là các đường liên tiếp và đóng kín
Chú ý: Vị trí trong bản đồ địa lý toàn cầu thể hiện kinh độ (lon), vĩ độ (lat)
- Kiểu dữ liệu Raster: bao gồm các cell, mỗi cell diễn tả một vị trí trong Raster với giá trị
nguyên các thuộc tính về màu sắc và vị trí. Khi xuất dữ liệu thành dạng dữ liệu ảnh. Hình 2.6 Dữ liệu Raster và cách số hóa.
b) Geomtry Colum: lưu trữ thuộc tính đối tượng dữ liệu không gian. Giá trị dữ liệu được
lưu trữ dưới dạng số hoặc dạng chuỗi các số được số hóa. Vì vậy việc thao tác đến các
vấn SQL với tên gọi psql. Đặc tính truy vấn phức được cài đặt cho phép truy vấn dữ liệu
thông thường mà còn cho phép truy vấn dữ liệu không gian và xây dựng câu lệnh truy vấn
phức tạp.
Trang 23
a) Cú pháp chung:
Select <trường dữ liệu> [from <nguồn dữ liệu>
[ where (<điều kiện>)] ]
- Select, from, where là các từ khóa của ngôn ngữ sql.
- Trường dữ liệu: cột dữ liệu trong các bảng, hoặc các trường là kết quả của biểu thức
tính toán. Nếu trường là * thì đại diện cho toàn bộ trường dữ liệu trong bảng. Các trường
được phân biệt bởi dấu phẩy.
- Nguồn dữ liệu: thể hiện nơi lưu trữ dữ liệu. Nguồn có thể là một bảng hoặc nhiều bảng,
thậm trí là function trong postres.
- Điều kiện: biểu thức trả về giá trị true/false. Thể hiện điều kiện lọc dữ liệu. Những dữ
liệu sánh đúng sẽ được trả về.
Ví dụ
TSPTest# Select * from Ways;
Select id, name, x, y from nodes where (id <6);
Chú ý: các thành phần from hoặc where có thể không xuất hiện trong câu lệnh Select. Ví
dụ select (6+7) as add; # kết quả 13.
b) Câu lệnh truy vấn dữ liệu select cơ bản
- Truy vấn dữ liệu từ bảng dữ liệu.
Select * from nodes;
Select id, name from nodes limit 10;
ST_GeomFromEWKT('SRID=4326;
LINESTRING(-73 41, -72 42)'), 32618));
Kết quả :
SRID=32618;LINESTRING(668207.88519421 4540683.52927698,
748464.920715711 4654130.89132385)
- Truy vấn sử dụng hàm trong pgRouting: các hàm trong pgrouting được trình bày cụ thể
trong chương 03. Ví dụ: gọi hàm pgr_tsp trong psql:
Câu lệnh thực hiện bài toán TSP cho 2 node 2 và 3.
TSPTest=# select seq, id1, id2, round (cost:: numeric) as cost from pgr_tsp('select id,x,y
from vertex_table',2,3);
Kết quả
seq | id1 | id2 | cost
+ + +
0 | 1 | 2 | 1
1 | 0 | 1 | 3
2 | 4 | 5 | 1
3 | 5 | 6 | 1
4 | 6 | 7 | 1
5 | 9 | 10 | 1
6 | 12 | 13 | 1
7 | 10 | 11 | 1
(13 rows)
Copyright: Tài liệu đại học ©