<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b> ĐẠI HỌC BÁCH KHOA HÀ NỘITRƯỜNG ĐIỆN- ĐIỆN TỬ</b>

<b>--Báo cáo bài tập lớn cuối kỳ</b>

<b>Cấu trúc dữ liệu và giải thuật</b>

<b> </b>

<i><b> ĐỀ TÀI:</b></i>

<b>HỖ TRỢ GIAO THÔNG</b>

<b> </b>

<b>Giáo viên hướng dẫn : Phạm Doãn Tĩnh</b>

<b>Sinh viên thực hiện </b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

Mục lục

I. Xác định bài toán...3

1. Đặt vấn đề...3

2. Giới thiệu chung...3

3. Định nghĩa bài toán...3

II. Các cấu trúc dữ liệu được sử dụng...3

1. Đồ thị...3

2. Mảng( vectors)...4

3. Hàng đợi ưu tiên( priority queue)...4

4. Kiểu dữ liệu Pair...4

III. Thuật toán Dijkstra...5

1. Ý tưởng...5

2. Minh họa thuật toán...5

IV. Cài đặt chương trình...6

1. Lớp Street...6

2. Đồ thị...8

3. Thuật toán Dijkstra...12

4. Hàm main...14

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

<b>I. Xác định bài toán:</b>

1. Đặt vấn đề:

- Ùn tắc giao thông là một vấn đề nan giải đối với hầu hếtcác thành phố lớn trên thế giới, kể cả các quốc gia phát triểncũng như các quốc gia đang phát triển. Hệ lụy của ùn tắc giaothông ảnh hưởng tiêu cực tới nhiều mặt của đời sống xã hội nhưlàm tăng thời gian đi lại, tăng tiêu hao nhiêu liệu và hao mònphương tiện, tăng chi phí đi lại, tăng lượng khí thải và tiếng ồn,làm giảm sự cơ động của giao thông đô thị, giảm chất lượngmơi trường sống đơ thị, kìm hãm sự phát triển của kinh tế đơthị…

=> Cần có một ứng dụng giúp định vị và tìm kiếm các tuyếnđường hiệu quả về mặt thời gian.

2. Giới thiệu chung:

- Hệ thống được tạo ra nhằm giúp người dùng tìm được nhưngcon đường đi phù hợp với bản thân về không gian và thời gian. * Có 3 chức năng chính:

- Hiện thị thơng tin các tuyến đường đơ thị

- Tìm đường đi từ điểm ban đầu đến điểm kết thúc theo 2 chức năng

+ Con đường ngắn nhất

+ Con đường có thời gian di chuyến ngắn - Thêm vị trí người dùng lên bản đồ để từ đó tìm đường

đi đến các vị trí khác. 3. Định nghĩa bài toán:

- Cần 1 lớp Street để lưu trữ các thuộc tính của con đường + Gồm : Điểm bắt đầu, điểm kết thúc, độ dài con đường, vận tốc tối đa cho phép, số làn xe

-Xây dựng hàm in thông tin con đường để thực hiện chức năng hiển thị thông tin.

-Xây dựng các hàm liên quan để thực hiện chức năng tìm đường đi tiết kiệm thời nhât và con đường ngắn nhất. -Xây dựng hàm để thêm một vị trí người dùng chọn vào bản đồ.

<b>II. Các cấu trúc dữ liệu được sử dụng:</b>

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

1. Đồ thị:

- Là một dạng cấu trúc dữ liệu khơng tuyến tính biểu diễn một tập các đối tượng, trong đó các đối tượng được kết nối với nhau.

- Các đối tượng được biểu diễn bởi các đỉnh( vertices/nodes), và được nối với nhau bởi các cạnh( edges).

- Nói chung đồ thị G(V,E) là một cặp các tập hợp (V,E), trong đó V là tập các đỉnh , E là tập các cạnh.

- Hai đỉnh được gọi là kề nhau( adjacent) nếu chúng được kết nối với nhau thông qua một cạnh.

2. Mảng( vectors):

- Trong dự án, ta sử dụng vector(mảng động) trong C++ STL.- Vectors có thể tự động thay đổi kích thước khi xóa hoặc thêmphần tử.

- Có thể được truy cập ngẫu nhiên và duyệt như mảng tĩnhbình thường hoăc dùng Iterators.

- Thêm 1 phần tử vào vectors bằng hàm push_back().- Xóa 1 phần tử bằng hàm pop_back().

3. Hàng đợi ưu tiên( priority queue):

-Hàng đợi ưu tiên (priority queue) là một hàng đợi trong đómỗi phần tử được gắn với một con số được gọi là độ ưu tiên.

- Độ ưu tiên do ứng dụng xác định.

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

- Việc lấy một phần tử ra khỏi hàng đợi dựa trên độ ưu tiên vàquy tắc FIFO. Nghĩa là phần tử nào có độ ưu tiên cao nhất sẽđược lấy ra trước nhất. Trường hợp các phần tử có mức độ ưutiên như nhau thì sử dụng quy tắc FIFO.

4. Kiểu dữ liệu Pair:

 Kiểu dữ liệu pair được định nghĩa trong thư viện STL của C++, cho phép lưu 2 giá trị cùng lúc và được sử dụng trong nhiều trường hợp khác nhau

 Pair<T1, T2> pair_name(value1, value2);

T1, T2 là kiểu dữ liệu của hai giá trị trong pair pair_name là tên của pair

value1, value2 là giá trị hai phần tử trong pair Truy cập các phần tử trong pair bằng cách sử dụng thuộc

tính first và second

<b>III. Thuật toán Dijkstra:</b>

- Được tạo ra bởi nhà khoa học máy tính người Hà LanW.Dijkstra vào năm 1956.

- Là một trong những thuật tốn cổ điển để tìm đường đi ngắnnhất từ một điểm cho trước tới tất cả các điểm còn lại trong đồthị khơng có trọng số âm.

1. Ý tưởng:

- thuật toán Dijkstra tối ưu hóa đường đi bằng cách xét cáccạnh (u,v),so sánh hai đường đi S→v sẵn có với đường đi S→u→v - Thuật tốn hoạt động bằng cách duy trì một tập hợp các đỉnh trong đó ta đã biết <b>chắc chắn</b> đường đi ngắn nhất. Mỗi bước, thuật toán sẽ chọn ra một đỉnh u mà chắc chắn sẽ không thể tối ưu hơn nữa, sau đó tiến hành tối ưu các đỉnh v khác dựa trên các cạnh (u,v) đi ra từ đỉnh u. Sau N bước, tất cả các đỉnh đều sẽ được chọn, và mọi đường đi tìm được sẽ là ngắn nhất. - Cụ thể hơn, thuật tốn sẽ duy trì đường đi ngắn nhất đến tất cả các đỉnh. Ở mỗi bước, chọn đường đi S→ucó tổng trọng số nhỏ nhất trong tất cả các đường đi đang được duy trì. Sau đótiến hành tối ưu các đường đi S→v bằng cách thử kéo dài thành S→u→v như đã mô tả trên.

2. Minh họa thuật toán: - B1: Khởi tạo:

+ Chọn đỉnh nguồn ban đầu.

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

+ Gán giá trị 0 cho đỉnh nguồn và vô cùng (hoặc giá trị lớn nhất có thể) cho các đỉnh cịn lại.

+ Đánh dấu tất cả các đỉnh là chưa được duyệt.

- B2: Lặp lại cho tất cả các đỉnh: a. Tìm đỉnh v có giá trị nhãn nhỏ nhất (đỉnh gần nhất) chưa được duyệt. b. Đánh dấu đỉnh v

<b>là đã duyệt.</b>

<b> - B3: Duyệt qua tất cả các đỉnh kề của đỉnh v: a. Nếu đỉnh kề </b>

chưa được duyệt và có giá trị nhãn hiện tại lớn hơn giá trị nhãn của đỉnh v cộng với trọng số của cạnh với đỉnh kề, cập nhật giá trị nhãn của đỉnh kề. b. Lưu đỉnh v là đỉnh trước đỉnh kề. - B4: Lặp lại từ bước 2 cho đến khi tất cả các đỉnh đều đã được duyệt hoặc giá trị nhãn của đỉnh tiếp theo là vô cùng.

<b>IV. Cài đặt chương trình:</b>

1. Lớp Street#include<bits/stdc++.h>#pragma once

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

pair<char, pair<char, double>> name; // pair<'A', pair<'B', 2.5>> = con đường bat dau tai A và ket thuc tai B => AB=2.5;

int maxspeed; // Toc do cho phep int numLanes; // So lan xe

Street(pair<char, pair<char, double>> name, int maxspeed, int numLanes) // Hàm khởi tạo

{

this->name = name; this->maxspeed = maxspeed; this->numLanes = numLanes; }

int Check(); // Hàm kiểm tra loại đường void Print(); // Hàm in thông tin đường};

int Street::Check() {

if (Street::maxspeed <= 40) return 1; // 1 tương ứng với đường phổ thông if (Street::maxspeed > 40 && maxspeed <= 80) return 2; // 2 tương ứng với đường quốc lộ

if (Street::maxspeed > 80) return 3; // 3 tương ứng với đường cao tốc }

void Street::Print() {

cout << " Street names: " << Street::name.first <<name.second.first << endl;

cout << " Street length: " << Street::name.second.second << "Km" << endl;

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

cout << " Maximum speed allowed: " << Street::maxspeed << "(km/h)" << endl;

cout << " Number of motor vehicle lanes: " << Street::numLanes << endl;

switch (Check()) {

default: break; }

} 2. Đồ thị

int NumPlaces = 12; / / Số điểm trên bản đồ int NumStreet = 17; // Số đường đi được khởi tạo.

void Input(vector<Street> st, vector<vector<pair<int, double>>>& adj) // Nhập thông tin vào vector các vector

{

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

for (int i = 0; i < NumStreet; i++) {

adj[st[i].name.first-64].push_back({st[i].name.second.first-64, st[i].name.second.second});

adj[st[i].name.second.first-64].push_back({st[i].name.first-64, st[i].name.second.second}); // Tạo đồ thi vô hướng

}}void Edit(){

for(int i = 0; i < 30; i++) {

cout <<"*"<<"-"; }

cout << endl;}

bool CheckPoint(string s, vector<Street> v) // kiểm tra xem một địa điểm có tồntại trên bản đồ hay không.

if (s.length() != 1) return false;

for (int i=0;i<v.size();i++) {

if (v[i].name.first == s[0] || v[i].name.second.first == s[0]) return true;

}

return false;}

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

void AddPoint(vector<Street> &v) // Cho phép người dùng thêm một địa điểm mới vào bản đồ và cập nhật đồ thị tương ứng.

cout << endl;

cout << " Enter here: "; string Checking = "" ; cin >> Checking;

if(!CheckInput(Checking,17)) {

int choice1 = 0, c = 1;

for(int i=Checking.size()-1; i >= 0; i--)

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

{

choice1= choice1+(Checking[i]-('1'-1))*c; c=c*10;

} double l;

cout << " The distance from your location to location " << 1].name.first <<" (km)" << endl;

cout << " Enter here: "; cin >> l;

if(l < 0 || l > v[choice1-1].name.second.second) {

do {

cout << " The distance you selected is not valid, please choose again " << endl;

cout << " Enter here: "; cin >> l;

} while (l < 0 || l > v[choice1-1].name.second.second); }

NumPlaces++;

NumStreet=NumStreet+2;

pair<char, pair<char, double>> streetName =

make_pair(char(NumPlaces+64), make_pair(v[choice1-1].name.first, l)); Street st1(streetName, v[choice1-1].maxspeed , v[choice1-1].numLanes); streetName = make_pair(char(NumPlaces+64), make_pair(v[choice1-1].name.second.first, v[choice1-1].name.second.second - l));

Street st2(streetName, v[choice1-1].maxspeed , v[choice1-1].numLanes); v.push_back(st2);

v.push_back(st1);

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

cout << " You have successfully added the location." << endl; cout << " Your position is called " << char(NumPlaces + 64) << endl;}

Thêm điểm vào đồ thị 3. Thuật toán Dijkstra:

void Dijkstra(int Start, int End,vector<Street> st) // Thuật toán Dijkstra{

vector<vector<pair<int, double>>> adj(NumPlaces+1); // khởi tạo vector các vector với số phần tử xin cấp phát là NumPlaces+1

Input(st, adj); // thực hiện nhập vào adj tạo đồ thị.

int pre[maxn]; // tạo mảng pre[] có tác dụng in ra đường đi ngắn nhất. vector<double> Distance(NumPlaces + 1, INF); // tạo vector số thực để khởi tạo khoảng cách đến mọi điểm, ban đầu khởi tạo khoảng cách là vô cùng. Distance[Start] = 0; // Cho khoảng cách đến điểm bắt đầu bằng 0.

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

pre[Start] = Start; // cho pre[Start]=Start tức đường đi đến điểm khởi đầu là chính nó.

priority_queue<pair<double, int>, vector<pair<double, int>>,

greater<pair<double, int>>> Q; // Khởi tạo hàng đợi ưu tiên theo thứ tự bé đến lớn

Q.push({0, Start}); // push điểm đầu với chiều dài là 0. while (!Q.empty())

{

pair<double, int> top = Q.top(); Q.pop();

int u = top.second; double Dis = top.first;

if (Dis > Distance[u]) // kiểm tra xem điểm này đã được thăm trước đó chưa.

continue;

for (auto it : adj[u]) // it là pair gồm điểm lân cận và khoảng cách từ điểm lân cận đến điểm đang xét.

{

int v = it.first; // v là điểm lân cận

double w = it.second; // w là khoảng cách từ điểm lân cận đến điểm đangxét.

if (Distance[v] >= Distance[u] + w) // Nếu khoảng cách từ Start đến v lớn hơn tổng khoách cách từ Start đến u kết hợp với w.

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

vector<Street> v;

pair<char, pair<char, double>> streetName = make_pair('A', make_pair('B', 1));

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

Street st1(streetName, 60, 4); v.push_back(st1);

streetName = make_pair('A', make_pair('E', 3)); Street st2(streetName, 30, 2);

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

Street st10(streetName, 40, 2); v.push_back(st10);

streetName = make_pair('F', make_pair('G', 5)); Street st11(streetName, 90, 6);

cout << " ***********************************************" << endl;

cout << " * SMART MAP *" << endl;

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

cout << " ***********************************************" << endl

<< endl;

cout << " Welcome to the smart map!" << endl; int choice = 0;

while (choice != 4) {

cout << endl;

cout << "What would you like to do?" << endl; cout << " 1. View streets information" << endl; cout << " 2. Find the way" << endl;

cout << " 3. Add your location" << endl; cout << " 4. Exit." << endl;

cout << "Enter your choice: "; string s;

{ case 1: { Edit();

cout << " Which street information would you like to receive?" << endl; for (int i = 0; i < 17; i++)

{

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

if(i<9) cout << " " << i + 1 << "." << v[i].name.first << v[i].name.second.first << " ";

else cout << " " << i + 1 << "." << v[i].name.first << v[i].name.second.first << " ";

if ((i + 1) % 4 == 0) cout << endl; }

cout << endl;

cout << " Enter here: "; string Checking = "" ; cin >> Checking;

if(!CheckInput(Checking,17)) {

int Choice1 = 0, c = 1 ;

for(int i=Checking.size()-1; i >= 0; i--) {

Choice1= Choice1+(Checking[i]-('1'-1))*c; c=c*10;

}

v[Choice1 - 1].Print(); Edit();

break;

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

} case 2: { Edit();

cout << " Enter starting point" << endl; cout << " Enter here: ";

string Start; cin >> Start;

if (!CheckPoint(Start, v)) {

do {

cout << " Location does not exist on the map. Please re-enter." << endl;

cout << " Enter again here: "; cin >> Start;

} while (!CheckPoint(Start, v)); }

char a= Start[0];

cout << " Enter the end point" << endl; cout << " Enter here: ";

string End; cin >> End;

if (!CheckPoint(End, v)) {

do {

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

cout << " Location does not exist on the map. Please re-enter." << endl;

cout << " Enter again here: "; cin >> End;

} while (!CheckPoint(End, v)); }

char b=End[0];

cout << " Minimum distance traveled from " << Start << " to " << End << endl;

cout << " " ; Dijkstra(a - 64, b - 64, v);

cout << "(KM):Total path length" << endl;

cout << " The route with the shortest travel time" << endl; cout << " " ;

Dijkstra(a - 64, b - 64, ResetLeght(v)); cout << "(h):Total estimated time" <<endl; Edit();

break; } case 3: { Edit(); AddPoint(v); Edit(); break; } default: break;

</div>