Môn học cấu trúc dữ liệu & giải thuật báo cáo tiểu luận cuối kỳ

NHẬP ĐỀ2.1 Ý tưởng đề tài Về ý tưởng cho sản phẩm của bài tiểu luận bắt nguồn từ chính môn học Cấu trúc dữ liệu và thuật toán này khi mà trong môn học bọn em đã được học các kiến thức về

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA: TOÁN-CƠ-TIN HỌC

🙦🙧🕮🙥🙤

MÔN HỌC: CẤU TRÚC DỮ LIỆU & GIẢI THUẬT

Báo cáo: Tiểu luận cuối kỳ

Giảng viên hướng dẫn: cô Nguyễn Thị Hồng Minh

thầy Trần Bá Tuấn thầy Đặng Trung Du anh Phạm Bá Thắng

Nhóm 9

Lê Quang Tín - 22001643

Mục lục

PHẦN 1 LỜI MỞ ĐẦU 3

Phần 2 NHẬP ĐỀ 4

2.1 Ý tưởng đề tài 4

2.2 Mục đích 4

2.3 Ý nghĩa của đề tài 4

2.4 Cấu trúc báo cáo 4

Phần 3 Cấu trúc dữ liệu và thuật toán 5

3.1 Mảng và mảng hai chiều 5

3.2 Danh sách liên kết 6

3.3 HashMap 6

3.4 Graph 7

3.5 Priority queue 7

3.6 Thuật toán tìm đường Dijkstra 7

Mô tả thuật toán 8

Phần 4 Triển khai ứng dụng 11

4.1 Xây dựng giao diện cho cửa hàng 11

4.2 Ứng dụng báo cáo chính 12

4.2.1 Xây dựng ứng dụng 12

4.2.2 Logic vận hành của ứng dụng 14

4.2.3 Giao diện 18

PHẦN 1 LỜI MỞ ĐẦU

Trong quá trình nghiên cứu và thực hiện “Báo cáo tiểu luận cuối kỳ” nhóm chúng

em đã nhận được sự chỉ bảo, giúp đỡ nhiệt tình của thầy cô trong việc định hướng cũng như tạo điều kiện cho chúng em tiến hành làm bài tiểu luận cuối kì Chúng em xin chân thành gửi lời cảm ơn tới:

- Cô Nguyễn Thị Hồng Minh là giáo viên chủ nhiệm môn học, giảng dạy phần lý thuyết của bộ môn đã chia sẻ, góp ý cho chúng em về bài báo cáo để có thể thực hiện tốt hơn.

- Thầy Trần Bá Tuấn là giáo viên giảng dạy phần thực hành, giảng dạy cá kiến thức

về bộ môn, định hướng cũng như là đánh giá về bài báo cáo giúp chúng em hoàn thiện tốt hơn.

- Thầy Đặng Trung Du luôn giúp đỡ chúng em giải đáp các thắc mắc của môn học, cũng như là về phần tiểu luận cuối kỳ.

- Anh Phạm Bá Thắng là trợ giảng của môn học đã có góp ý và sửa đổi cho chúng

em về định hướng của bài tiểu luận, cũng như là về kiến thức môn học.

Chúng em xin chân thành cảm ơn tới các thầy cô đã giúp đỡ chúng em để có thể thực hiện và hoàn thành bài tiểu luận này.

Phần 2 NHẬP ĐỀ

2.1 Ý tưởng đề tài

Về ý tưởng cho sản phẩm của bài tiểu luận bắt nguồn từ chính môn học Cấu trúc

dữ liệu và thuật toán này khi mà trong môn học bọn em đã được học các kiến thức về các cấu trúc dữ liệu như: Array, Linked list, Stack, Queue, Và bọn em cảm thấy rằng bọn

em muốn làm một sản phẩm nào đó có khả năng thể hiện được những cấu trúc dữ liệu mà bọn em đã học được ở bộ môn thành các sản phẩm Vậy nên ý tưởng cho một cửa hàng ứng dụng mini với các ứng dụng được xây dựng nhờ các cấu trúc dữ liệu đã ra đời nhằm thể hiện và ứng dụng các ctdl đã học.

2.2 Mục đích

Sản phẩm nhằm mục đích chỉ ra cách mà chúng ta có thể vận dụng các cấu trúc để tạo nên những sản phẩm nhỏ cho nhiều loại mục đích khác nhau Mục tiêu chính của sản phẩm là thông qua các ứng dụng trong cửa hàng người dùng có thể hiểu được cách hoạt động và ứng dụng của các ctdl.

2.3 Ý nghĩa của đề tài

Việc phát triển cửa hàng ứng dụng mini giúp chúng ta hiểu rõ hơn về cách tạo nên các chương trình đơn giản bằng các ctdl và tt được học nhằm hiểu được các vận dụng các tính chất của chúng vào việc xây dựng được các chương trình đơn giản bằng Java.

2.4 Cấu trúc báo cáo

Báo cáo sẽ được trình bày theo thứ tự tuần tự từ bước giới thiệu cho tới nghiệm thu sản phẩm Phần 3 sẽ giới thiệu về các cấu trúc dữ liệu, cũng như là về thuật toán được

sử dụng trong sản phẩm Phần 4 sẽ trình bày phương pháp xây dựng cũng như về sản phẩm Phần 5 sẽ trình bày và kết luận về ý nghĩa của sản phẩm.

Phần 3 Cấu trúc dữ liệu và thuật toán

3.1 Mảng và mảng hai chiều

Cấu trúc dữ liệu mảng hay là mảng là một cấu trúc dữ liệu bao gồm 1 nhóm các phần tử giá trị, mỗi phần tử được xác định bằng 1 chỉ số (index) hoăc khóa (key).

+ Các phần tử trong 1 mảng phải cùng 1 kiểu dữ liệu

Khi đó chúng ta có khái niệm mảng của mảng (hay mảng 2 chiều)

+ Mảng sẽ được khai báo trước với kích thước cố định.

+ Các phần tử trong mảng được lưu vào các ô nhớ liên tiếp nhau trên bộ nhớ Mảng 2 chiều hay còn được gọi là ma trận (matrix), là một trong những khái niệm cơ bản

và quan trọng trong lập trình và toán học Nó cho phép tổ chức dữ liệu dưới dạng một bảng hai chiều, với hàng và cột, giúp mô phỏng hiệu quả các tình huống thực tế dưới dạng 2D.

Mảng 2 chiều sẽ có sự khác biệt so với mảng cơ bản ở chỗ:

1 Hàng và Cột: Nếu so với mảng thông thường mỗi phần tử chỉ sở hữu 1 chỉ số để xác định thì các phần tử của mảng 2 chiều xác định các index của các điểm qua các tọa độ (i,j), với i là chỉ số cửa hàng và j là chỉ số của cột.

2 Kích thước: kích thước trong mảng hai chiều là kích thước của tổng số ô được tạo nên bởi các hàng và cột Kích thước m x n với m là số hàng, n là số cột.

3.2 Danh sách liên kết

Danh sách liên kết là một cấu trúc dữ liệu trong lập trình, mà trong đó mỗi phần tử được liên kết với phần tử tiếp theo thông qua các liên kết Mỗi phần tử trong danh sách liên kết gọi là "nút" và chứa dữ liệu cùng một con trỏ (hoặc tham chiếu) đến nút tiếp theo trong danh sách.

3.3 HashMap

HashMap là một cấu trúc dữ liệu trong lập trình, được sử dụng để ánh xạ giữa các khóa (keys) và giá trị (values) Nó thường cung cấp việc truy xuất, chèn và xóa dữ liệu trong thời gian đồng đều (O(1)) trong trường hợp tốt nhất HashMap thường được sử dụng để giải quyết vấn đề tìm kiếm, thêm, xóa dữ liệu trong một tập hợp lớn.

3.4 Graph

Một đồ thị (đồ thị) là một dạng biểu diễn hình ảnh của một tập các đối tượng, trong đó các cặp đối tượng được kết nối bởi các link Các đối tượng được nối liền nhau được biểu diễn bởi các điểm được gọi là các đỉnh (vertices), và các link mà kết nối các đỉnh với nhau được gọi là các cạnh (edges).

3.5 Priority queue

Là một dạng cấu trúc dữ liệu cho phép ta lưu trữ dữ liệu đầu vào được sắp xếp theo mức độ ưu tiên của chúng nhờ đó mà việc kiểm soát cũng như truy xuất tới phần tử cần tìm có tính hiệu quả.

3.6 Thuật toán tìm đường Dijkstra

Thuật toán Dijkstra là một trong những thuật toán cổ điển để giải quyết bài toán

tìm đường đi ngắn nhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồ thị có trọng số Và ở trong báo cáo Dijkstra được sử dụng ứng dụng tìm bus.

Mô tả thuật toán

Để dễ hình dung cách hoạt động của thuật toán, ta xét ví dụ sau.

Cho đồ thị như hình trên

Nguồn ảnh: https://www.codingame.com

Hãy tìm đường đi ngắn nhất giữa đỉnh và các đỉnh còn lại trong đồ thị C

Ta sẽ áp dụng thuật toán Dijkstra cho đồ thị trên, hãy nghiên cứu thật kĩ từng công đoạn một vì nếu chỉ bỏ qua một chi tiết nhỏ ta sẽ không thể hiểu thuật toán được:

1 Trong toàn bộ quá trình thực thi thuật toán, ta sẽ đánh dấu tất cả các đỉnh bằng khoảng cách nhỏ nhất từ đỉnh tại các đỉnh đó Với đỉnh , khoảng cách sẽ là 0 Với các C C

đỉnh còn lại, ban đầu chưa biết khoảng cách nhỏ nhất nên ta sẽ đánh dấu mỗi đỉnh bằng giá trị vô cùng (∞).

Chúng ta cũng đánh dấu đỉnh hiện tại đang xét (ban đầu là đỉnh nguồn ) Ở đồ thị trên, C

ta đánh dấu bằng một chấm đỏ ở đỉnh (đỉnh hiện tại đang xét) C

2 Giờ chúng ta kiểm tra các đỉnh kề với đỉnh hiện tại đang xét (đỉnh - current C

node) đó là đỉnh A, B, D (không cần theo thứ tự cụ thể) Hãy bắt đầu với đỉnh Ta B

sẽ lấy giá trị dùng đánh dấu ở đỉnh (giá trị 0) cộng với trọng số của cạnh nối đỉnh C

đang xét (đỉnh ) với đỉnh (trong trường hợp này là 7), ta được 0+7=7 Sau đó ta sẽ C B

so sánh giá trị vừa tính được với giá trị dùng đánh dấu ở đỉnh (vô cùng) Ta sẽ đánh B

dấu đỉnh nhận giá trị nhỏ hơn là 7 (7 nhỏ hơn vô cùng) B

Đỉnh đã xong, giờ ta kiểm tra đỉnh kề Ta cộng 0 (giá trị dùng đánh dấu ở đỉnh ) B A C

với 1 (trọng số của cạnh nối đỉnh với đỉnh ) và được 0+1=1 Dễ thấy giá trị 1 nhỏ hơn C A

vô cùng (giá trị dùng đánh dấu ở đỉnh ) Do đó ta sẽ đánh dấu đỉnh nhận giá trị 1 A A

Tương tự với đỉnh : D

Ta đã xét xong các đỉnh kề với đỉnh đang xét (đỉnh ) Ta sẽ đánh một dấu tick ở C

đỉnh để thể hiện rằng các đỉnh kề nó đã được xét xong C

3 Giờ ta sẽ xét sang một đỉnh mới (gọi là đỉnh hiện tại đang xét - current node) Đỉnh này phải thỏa mãn điều kiện là chưa được xét và được đánh dấu với giá trị nhỏ nhất đó là đỉnh A Tương tự như đỉnh , ta sẽ đánh dấu đỉnh C A bằng một dấu chấm

đỏ.

Bây giờ ta lặp lại thuật toán như đã làm với đỉnh Chúng ta kiểm tra các đỉnh kề với C

đỉnh (Current node), nhớ rằng A không kiểm tra những đỉnh đã xét rồi (đỉnh C) Vậy

là ta chỉ cần kiểm tra đỉnh B

Lặp lại thuật toán nhờ việc triển khai hàng đợi ưu tiên ta sẽ thu được đường đi ngắn nhất cần tìm

Phần 4 Triển khai ứng dụng

4.1 Xây dựng giao diện cho cửa hàng

Giao diện sẽ được xây dựng bằng Java Swing là một bộ công cụ GUI (Graphical User Interface) được cung cấp bởi Java để phát triển giao diện người dùng đồ họa cho ứng dụng Java Swing cung cấp một loạt các thành phần UI như nút, hộp văn bản, danh sách, bảng, và cả các thành phần phức tạp như bảng điều khiển và cửa sổ đối thoại.

Khởi động cửa hàng ứng dụng

4.2 Ứng dụng báo cáo chính

Để cân bằng cho thời gian thuyết trình báo cáo nhóm chúng em đã quyết định chọn một sản phẩm chính cho việc báo cáo là ứng dụng tìm bus Hà Nội làm sản phẩm báo cáo chính.

4.2.1 Xây dựng ứng dụng

Lớp station được hiểu là trạm dừng xe bus bao gồm các thuộc tính là address tương ứng với địa chỉ của trạm trên bản đồ, thuộc tính id lưu trữ tọa độ của trạm, và thuộc tính kiểu LinkedList để lưu trữ những tuyến xe bus đi qua trạm.

4.2.2 Logic vận hành của ứng dụng

Ở đây chúng em xây dựng 2 lớp là StationManage và Journey, với:

 Lớp StationManage để quản lý các tuyến xe bus và các trạm

 Lớp Journey nhận dữ liệu về đường đi ngắn nhất và xử lý dữ liệu đó để trả về tuyếnđường đi tối ưu nhất

Đầu tiên, ở lớp StationManage:

*Phương thức insertBus() để thêm dữ liệu về những tuyến xe Bus hiện có

*Phương thức insertStation() để thêm dữ liệu về những trạm xe Bus hiện có

*Phương thức insertWay() để thêm dữ liệu về đường đi giữa các trạm

Lớp Journey:

Đầu tiên, ta sẽ lưu trữ một số lượng Station nhất định Vào Graph và cài đặt trọng số là khoảng cách giữa location của các trạm-Station Người dùng sẽ chọn ra 2 trong số các trạm có sẵn tương ứng là điểm xuất phát và đích đến

Sau khi nhận được điểm xuất phát và đích đến, ứng dụng sẽ thực hiện tìm đường đi ngắn nhất giữa 2 trạm và lưu những trạm ở giữa cần đi qua cùng với trậm đầu và cuối vào 1 List*

*Phương thức shortestPath() sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ trạm Startđến trạm End

*Phương thức tìm đường đi ngắn nhất được cài đặt trong kiểu dữ liệu đồ thị

Sau khi có lộ trình là List lưu trữ các trạm, ứng dụng sẽ duyệt qua tất cả những tuyến xe bus đi qua mỗi trạm Trong phương thức getJourney() sẽ khởi tạo một map với key là Bus

và value là LinkedList lưu trữ các Station Thuật toán sẽ trả về map với key là những tuyến xe bus cùng với những trạm được lưu trong List* mà tuyến xe bus đó đi qua

Sau khi có được Map, phương thức getOptimalJourney() sẽ thực hiện tìm lộ trình tốt nhất để đi từ điểm xuất phát đến đích với mức độ ưu tiên dựa vào:

1 Đi từ trạm đầu đến trạm cuối cần lên số xe bus là ít nhất

2 Mỗi chặng trước khi chuyển xe sẽ đi được qua số trạm nhiều nhất mà xe đó có thể đi

4.2.3 Giao diện

Sau khi có được danh sách lộ trình tốt nhất, với mỗi lộ trình, ta sẽ có được tọa độ của từng trạm và tuyến xe bus để đi qua những trạm đó.

Lớp MyWayPoint àv MyWaypointRender sẽ lưu dữ liệu về thông tin của 1 điểm trên bản

đồ và giao diện hóa điểm đó

Lớp RountingData sẽ lưu dữ liệu về đường đi được lấy từ API

Lớp JXMapViewerCustom sẽ thừa kế lớp JXMapViewer để thực hiện lưu dữ liệu về đường đi và vẽ đường đi

index trong colors sẽ ứng với giá trị trong buses với index đó, có nghĩa là với cùng 1 tuyến xe bus sẽ có màu giống nhau và ngược lại

Lớp Main sẽ kế thừa JFrame để thực hiện giao diện hóa Trong đó, action cmdAddActionPerformed sẽ thực hiện lấy dữ liệu về đường đi tối ưu, sau đó thêm các trạm là các waypoint, từ đó vẽ các chặng đường giữa các trạm

Với mỗi tọa độ của mỗi trạm, ta sẽ đánh dấu trên bản đồ, đồng thời vẽ đường đi giữa các trạm đó, mỗi tuyến xe bus sẽ được vẽ bằng 1 màu riêng.

Ví dụ như ở đây, đi từ bến xe Gia Lâm đến Bến xe Giáp Bát sẽ cần đi 2 tuyến xe và 1 trạm trung gian Người dùng có thể bấm vào biểu tượng trạm hoặc xe bus để biết thông tin về trạm hoặc xe bus đó.

Như ở đây, trạm trung gian sẽ là bến xe Lương Yên.

Ứng dụng cũng sẽ cung cấp cho người dùng tổng số tiền cần phải trả để hoàn thành chuyến đi

Với mỗi tuyến xe sẽ có giá là 7.000vnd, tương ứng trong ví dụ sẽ là 14.000vnd ứng với 2 tuyến xe

4.2.4 Cải tiến cho ứng dụng

Thuật toán Dijkstra có độ phức tạp là O(N^2)(N là số đỉnh của đồ thị), trong một bài toán nếu ta chạy Dijkstra chỉ một hoặc vài lần thì thời gian không phải là vấn

đề, tuy nhiên khi cần chạy Dijkstra rất nhiều lần thì ta phải cài đặt lại Dijkstra sao cho tốc độ của nó được nhanh hơn Từ đó, chúng em đã tìm hiểu cách cải tiến thuật toán Dijkstra bằng Heap

 mark: array[1 N] of boolean — dùng để đánh dấu xem một đỉnh đã có nhãn cố định hay chưa

 d: array[1 N] of integer — d[i] là nhãn của đỉnh i, nó là độ dài đường đi ngắn nhất hiện thời từ S đến i

 dad: array[1 N] of integer — dùng để ghi nhận đỉnh đi kề trước trên đường đi

 đánh dấu K thành nhãn cố định (mark[K] = false)

 tìm xem có đỉnh V nào nhãn chưa cố định, có cạnh nối tới K và d[V] > d[K] + a[K, V] thì d[V] = d[K] + a[K, V] và dad[V] = K

Thuật toán Dijkstra cải tiến

Chúng ta hãy để ý tới bước (*), để tìm ra đỉnh K như vậy bình thường ta phải duyệt qua N đỉnh Tại sao ta không dùng cấu trúc Heap, như vậy ta sẽ lấy ra được ngay K

ở đầu Heap, đưa đuôi của Heap lên đầu và vun lại Heap, thao tác vun chỉ mất cỡ logarith cơ số 2 của độ dài Heap Tốc độ sẽ được cải thiện đáng kể.

Điểm qua chút về tính chất của Heap: Heap là một cấu trúc cây nhị phân trong đó giá trị ở nút cha luôn bé hơn hoặc bằng giá trị ở mỗi hai nút con Dễ thấy nút ở đầu Heap (nút gốc) là có giá trị bé nhất trong toàn Heap Trong quá trình sử dụng, vài nút trong Heap bị thay đổi giá trị (gọi là nút k), khi đó tính chất Heap bị phá vỡ và

ta phải hiệu chỉnh lại Heap, có hai thủ tục cơ bản để làm điều này

là downheap(k) và upheap(k)

Trở lại Dijkstra cải tiến, phần khởi tạo có thêm phần tạo Heap, chú ý rằng lúc này mảng d đã bị xáo trộn, d[i] không còn là nhãn của đỉnh i nữa mà là nhãn của

chỉ có các phần tử trong Heap thì mới có nhãn chưa cố định Và thuật toán Dijkstra viết lại như sau:

Lặp lại N lần các công việc sau:

 đỉnh K = index[1] trở thành có nhãn cố định, sao lưu d[1]: tmp = d[1]

 loại bỏ nút 1 (nút gốc) ra khỏi Heap bằng cách đưa nút cuối Heap lên thay thế và giảm kích thước Heap đi 1 đơn vị, hiệu chỉnh Heap bằng cách gọi downheap(1)

 tìm xem có đỉnh V nào trong Heap, có cạnh nối tới K và d[V] > tmp + a[K, index[V]] thì:

Ứng dụng trong hệ thống thông tin di động điện tử

Ngoài việc tìm đường đi thực tế, một số hệ thống thông tin di động còn ứng dụng thuật toán này để có thể truyền tải thông tin nhanh hơn khi có kết nối nội bộ giữa các đỉnh, các đỉnh này có thể là GPS hay Airdrop, miễn là có kết nối thì thuật toán

sẽ tìm được đường nhanh nhất để truyền tải thông tin bạn muốn.

Bên cạnh đó, việc sử dụng internet cũng là điều kiện để các hacker sử dụng dấu vết của bạn, kết nối các đỉnh và truy tìm ra những thông tin được kết nối cũng như đường chính xác và ngắn nhất đến địa điểm mà bạn đang truy cập mạng.

Ứng dụng trong kỹ thuật của ngành hàng không vũ trụ

Tương tự hệ thống giao thông vận tải mặt đất, thuật toán Dijkstra cực kỳ hữu dụng khi các phi công phải dựa trên bản đồ hiển thị trong quá trình lái máy bay được tích hợp thông qua thuật toán, tránh việc tìm đường dựa trên cảm quan gây ra những sai sót nghiêm trọng đến tính mạng cũng như các hệ lụy nặng nề khác Tính chất của ngành hàng không là phải bay theo quỹ đạo được định sẵn bởi thuật toán, nếu bạn cố ý bay chệch đường bay được định sẵn, thuật toán sẽ trở nên lộn xộn và dễ vượt ngoài tầm kiểm soát.