Thạc Sĩ Tìm kiếm thông tin dựa vào cấu trúc dữ liệu Heap

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


iv
MỤC LỤC

Lời cam đoan . i
Lời cảm ơn . iii
Mục lục iv
Danh mục các bảng . vi
Danh mục các hình vii
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
2. Đối tượng và phạm vi nghiên cứu 2
3. Những nội dung nghiên cứu chính . 2
4. Phương pháp nghiên cứu 3
5. Ý nghĩa khoa học của đề tài 3
Chương 1. KHÁI QUÁT VỀ TÌM KIẾM VÀ VẤN ĐỀ TỔ CHỨC DỮ LIỆU 4
1.1. Khái quát về tìm kiếm . 4
1.1.1 Thông tin 4
1.1.2. Một số loại tìm kiếm thông tin 7
1.1.2.1. Tìm kiếm trên danh sách 7
1.1.2.3. Tìm kiếm đường đi . 11
1.2. Tổ chức dữ liệu trong tìm kiếm thông tin 13
1.2.1. Giới thiệu 13
1.2.2. Một số cấu trúc dữ liệu 15
1.2.2.1. Stack 15
1.2.2.2. Queue 15
1.2.2.4. Heap 16
Chương 2. MỘT SỐ THUẬT TOÁN THAO TÁC TRONG HEAP . 18
2.1. Biểu diễn Heap 18
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


v
2.2. Khởi tạo Heap rỗng . 19
2.3. UpHeap . 19
2.4. DownHeap 27
2.5. Thêm một phần tử vào Heap . 36
2.6. Đọc một phần tử đỉnh Heap 37
2.7. Lấy một phần tử ở gốc khỏi Heap . 38
2.8. Cập nhật một phần tử trong Heap 40
2.9. Tìm kiếm đường đi theo lựa chọn tốt nhất . 42
Chương 3. XÂY DỰNG CHƯƠNG TRÌNH TÌM ĐƯỜNG ĐI TRONG THÀNH
PHỐ THANH HÓA . 46
3.1. Phân tích yêu cầu bài toán . 46
3.2. Phân tích, lựa chọn công cụ . 48
3.2.1. Mô tả dữ liệu 48
3.2.2 Thiết kế các bước thực hiện . 48
3.2.3. Ngôn ngữ lập trình 51
3.3. Một số kết quả chương trình 51
KẾT LUẬN . 55
TÀI LIỆU THAM KHẢO 56
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


vi
DANH MỤC CÁC BẢNG
Trang
Bảng 2.1. Biểu diễn Heap bằng mảng 1 chiều 18
Bảng 2.2. Bảng kết quả tính toán theo thuật toán . 44
Bảng 3.1. Trọng số các cạnh của đồ thị 49

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


vii
DANH MỤC CÁC HÌNH
Trang
Hình 1.1. Thông tin dạng văn bản . 5
Hình 1.2. Thông tin dạng hình ảnh . 6
Hình 1.3. Thông tin dạng âm thanh 6
Hình 1.4. Mô hình Stack trong thực tế 15
Hình 1.5. Mô hình Queue trong thực tế 16
Hình 1.6. Heap Max chứa các phần tử có thể giống nhau 17
Hình 2.1. Chỉ số con trái và con phải một nút trong Heap . 18
Hình 2.2. Heap Max trong quá trình UpHeap . 20
Hình 2.3. Vị trí cần UpHeap . 21
Hình 2.4. Gán giá trị Heap[9] = 7 . 21
Hình 2.5. Gán giá trị Heap[4] = 8 . 22
Hình 2.6. Gán giá trị Heap[2] = 9 và kết thúc . 22
Hình 2.7. Sơ đồ thuật toán UpHeap 23
Hình 2.8. Đổi chỗ 2 giá trị Heap[9] và Heap[4] cho nhau 25
Hình 2.9. Đổi chỗ 2 giá trị Heap[4] và Heap[2] cho nhau 25
Hình 2.10. Sơ đồ thuật toán UpHeap dùng đệ qui 26
Hình 2.11. Heap Max trong quá trình UpHeap . 28
Hình 2.12. Heap[1] bị thay đổi giá trị . 28
Hình 2.13. Gán giá trị mới cho Heap[1] . 29
Hình 2.14. Gán giá trị mới cho Heap[2] . 29
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


vii
i
Hình 2.15. Gán giá trị mới cho Heap[4] . 30
Hình 2.16. Gán giá trị mới cho Heap[9] . 30
Hình 2.17. Sơ đồ thuật toán DownHeap . 31
Hình 2.18. Heap[1] bị thay đổi giá trị trong UpHeap đệ qui 33
Hình 2.19. Đổi chỗ Heap[2] và Heap[1] cho nhau . 33
Hình 2.20. Đổi chỗ Heap[4] và Heap[2] cho nhau . 34
Hình 2.21. Đổi chỗ Heap[9] và Heap[4] cho nhau . 34
Hình 2.22. Sơ đồ thuật toán DownHeap dùng đệ quy 35
Hình 2.23. Sơ đồ thuật toán thêm một phần tử vào Heap . 37
Hình 2.24. Sơ đồ thuật toán đọc một phần tử ở đỉnh Heap . 38
Hình 2.25 Sơ đồ thuật toán lấy một phần tử ở đỉnh Heap 39
Hình 2.26. Cập nhật Heap . 40
Hình 2.27. Sơ đồ khối thuật toán cập nhật một phần tử trong Heap 41
Hình 2.28. Minh họa đường đi 43
Hình 3.1. Bản đồ giao thông thành phố Thanh Hóa . 47
Hình 3.2. Một vùng bản đồ giao thông của thành phố Thanh Hóa . 49
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


1
MỞ ĐẦU
1. Lý do chọn đề tài
Hiện nay, công nghệ thông tin với tốc độ phát triển rất nhanh. Các nhà
khoa học khẳng định rằng chưa có một ngành khoa học – công nghệ nào lại
có nhiều ứng dụng rộng rãi như công nghệ thông tin. Việc ứng dụng công
nghệ thông tin trong giáo dục đã trở thành mối ưu tiên hàng đầu của nhiều
quốc gia, trong đó có Việt Nam. Sự tiến bộ về công nghệ và sự phổ cập của
các hệ thống phần mềm tiên tiến đã đưa đến những sự thay đổi cách đào tạo
chuyên gia trong lĩnh vực tin học. Các kiến thức giải thuật được coi là đỉnh
cao trước đây bây giờ đã trở thành “bảng cửu chương” mà ai cũng phải biết
và phải thuộc. Những giải thuật ít dùng và phức tạp thì không nhất thiết phải
biết hoặc nhớ vì bất cứ ai và lúc nào cũng có thể tra cứu, tìm kiếm chúng trên
internet khi cần thiết. Thử thách bây giờ là ở chỗ ta có thể tìm ra những giải
pháp hữu hiệu giải quyết một cách có hiệu quả các bài toán, các vấn đề có mô
hình toán học đơn giản nhưng có kích thước lớn hay không?
Để đạt được mục đích đó, người lập trình phải tận dụng tối đa khả năng
mà phần cứng và hệ điều hành cung cấp, khai thác tối đa khả năng của công
cụ lập trình, sử dụng linh hoạt các cấu trúc dữ liệu. Trong đó, Heap là một cấu
trúc dữ liệu quan trọng, có nhiều ứng dụng trong tính toán, truy vấn cơ sở dữ
liệu và xử lí tín hiệu. Bên cạnh đó, việc tìm kiếm đường đi tối ưu bằng các
phương pháp của khoa học tính toán với nguồn dữ liệu khổng lồ để cho ra kết
quả nhanh và chính xác nhất.
Trong khuôn khổ luận văn thạc sĩ, tôi chọn đề tài nghiên cứu: “Tìm
kiếm thông tin dựa vào cấu trúc dữ liệu Heap”, nghiên cứu về Heap và thực
hiện một phương pháp tiếp cận mới, nhanh chóng và linh hoạt để tìm đường
đi tối ưu trong thành phố Thanh Hóa.
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


2
2. Đối tượng và phạm vi nghiên cứu
Đối tượng và phạm vi nghiên cứu của luận văn tập trung vào tìm hiểu
về Heap và từ đó xây dựng ứng dụng tìm đường đi trong thành phố thành phố
Thanh Hóa.
3. Những nội dung nghiên cứu chính
Chương 1. Khái quát về tìm kiếm và vấn đề tổ chức dữ liệu
Trong ngành khoa học máy tính tìm kiếm là một thuật toán lấy đầu vào
là một bài toán và trả về kết quả là một lời giải cho bài toán đó, thường là sau
khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuật toán được
nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toán đều là
các thuật toán tìm kiếm.
Vấn đề tổ chức dữ liệu là công việc hết sức quan trọng, khi ta có một
thuật toán tốt và chọn lựa cấu trúc dữ liệu phù hợp để lưu trữ thì bài toán được
giải quyết một cách nhanh chóng. Đôi khi một bài toán có thuật toán tốt
nhưng chúng ta lại chọn lựa cấu trúc dữ liệu không phù hợp thì có thể dẫn đến
việc giải quyết bài toán đó trở nên khó khăn và phức tạp hơn.
Chương 2. Một số thuật toán thao tác trong Heap
Khi làm việc với Heap, thì trên Heap có một số thao tác nhưng nó có hai
thao tác rất quan trọng là DownHeap và UpHeap.
Chương 3. Xây dựng chương trình tìm đường đi trong thành phố
Thanh Hóa
Đây là chương trình ứng dụng tìm đường đi ngắn nhất giữa hai địa điểm
bất kỳ trong thành phố Thanh Hóa. Nó giúp người sử dụng chọn nhanh và chính
xác được đường đi tối ưu nhất.
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


3
4. Phương pháp nghiên cứu
Phương pháp nghiên cứu lí thuyết: Tổng hợp tài liệu, suy diễn, quy
nạp, các phương pháp hình thức, .
Phương pháp thực nghiệm: xử lí thống kê, đối sánh, .
Phương pháp trao đổi khoa học, tổng hợp các kết quả của các nhà
nghiên cứu liên quan đến lĩnh vực nghiên cứu, lấy ý kiến chuyên gia.
5. Ý nghĩa khoa học của đề tài
Đề tài đưa ra một phương pháp nhanh chóng, hiệu quả và linh hoạt để
tìm Min, Max trong một tập hợp động. Điều này mang ý nghĩa thiết thực
trong việc hỗ trợ tìm đường đi tối ưu trong thành phố Thanh Hóa.