Name: Sung Il Choi
Course: CSI 203
Subject: Project
Instructor: Dr. Wang
Road planner
Road planner is a program which
design to gives an optimal road plan from Norristown to Temple University. The
program involves taking into account the uncertainties that could crop up in
the planning process such as snow, traffic jam, accident etc. Program takes
several factors to make road plan. The factors are time, date, weather and road
condition. The program takes accounted these factors to decide the road plan.
The Active logic is used for reasoning about the choice of road, based on
distance, weather and road condition. If one of road has accident or mad
weather, program is able to decide to change or continues with the plan.
Sometime road with mad condition can be faster than taking alternative
plan.
This
program is small that can be use in large scale with sufficient information. It
also can be used in navigation system.
Now this days, Navigation system is very popular for car. The current
navigation system only give position of car and map. With Active logic, the
trip is going to be more pleasant. Such system can be incorporated in Fedex,
UPS, military, and several transportation company.
Case study:
Road Planner
Problem
Creates a program that gives a best possible
road from Norristown to Temple University. Also It need to be able to change
the road plan according to user's need. Program should display the approximate
time and distance. If one of the road have accident or closed, It should give a
alternative plan or tell continue with plan.
Analysis
To give best possible road from Norristown to
Temple University, It use Dijkstra's algorithm and need to take current date,
time, weather condition and road condition from the user.
1. Date and month: if date is holiday, all road are clear.
2. Time : if time is rush hour,
average speed is decreasing by 1/2 time.
3. weather condition: if weather condition is mad, travel time is
increasing by level of weather condition. The level of weather condition scale
between 1 to 10.
4. Road condition:
ask user if there is any mad condition,
input the street.
Input from the user are:
Date
Time
Weather condition
Road condition( only accident )
Output for user are:
Distance
average speed
Sequence of road
Dijkstra's Algorithm
procedure
Dijkstra(G:weighted connected simple graph, with all weights positive)
{G has vertices a =
V0, V1,......,Vn = z and weights w(vi, vj) where (vi,vj) = ~ if {vi, vj} is not
an edge in G}
For i:= 1 to n
L(vi):= ~
L(a) := 0
S:= null
{the labels are now
initialized so that the label of a is zero and all other labels are ~, and S is
the empty set}
while z not belong
to S
begin
u:= a vertex not in s with L(u)
minimal
S:= S u {u}
for
all vertices v not in S
if L(u) + w(u, v) < L(v) then L(v):= L(u) + w(u, v)
{this adds a vertex to S with
minimal label and updates the labels of vertices
not in S}
end {L(z) =
length of shortest path from a to z}
Design
The program divides into three subprogram.
Initial Algorithm
1. Ask current date, time, weather
and road condition.
2. Makes the road plan.
3. Display the result
Algorithm Refinements
Step 2 Refinement
2.1 Find shortest path using
Dijkstra’s Algorithm
2.2
Takes factors to decide if the path is optimal road.
2.3 if the path is not optimal, find
shortest path.
Step 3 Refinement
3.1 Display average speed
3.2 Display travel distance
3.3 Display roads
code:
#include<iostream>
#include<string>
#include<fstream>
#include<cstdlib>
using namespace std;
struct road
{
string
names;
int mile,
time;
char
connect, traclight;
};
#define infile "road.dat"//infile
//function definition
void mainmenu(char &hour,int &date, char
&accident, string &street);
void sortpath(int& totalmile, float& totaltime, road
allroad[10], char& root);
void decision(char accident, char hour, road
allroad[10],float totaltime,int totalmile, char root,string street, int date);
char findstreet(road allroad[10], string street);
char holiday(int date);
void loadroad(ifstream& eds,road allroad[10]);
void display(char root, road allroad[10], int totaltime, int
totalmile);
int main()
{
int date,
option, totalmile;
float
totaltime;
char
accident,hour, root = 'a';
string
street;
road
allroad[10];
ifstream
eds;
//prepare
files
eds.open(infile);
if
(eds.fail())
{
cerr<<"******* ERROR:
cannot open" <<infile<<"for input."<<endl;
return EXIT_FAILURE;//failure return
}
//call all
fuction
loadroad(eds,allroad);
mainmenu(hour,date,
accident, street);
sortpath(totalmile,
totaltime, allroad, root);
//close
file
eds.close();
return 0;
}
//begining of mainmenu fuction
void mainmenu(char &hour,int &date, char
&accident, string &street)
{
cout<<"Please
type r:rush hour and n:normal hour"<<endl;
cout<<"please
enter time: ";
cin>>hour;
cout<<"Please
enter date: ";
cin>>date;
cout<<"Please
type y:yes or n: no"<<endl;
cout<<"is
there any accident? ";
cin>>accident;
if (
tolower(accident) == 'y')
{
cout<<"Please enter
street: ";
cin>>street;
}
}//end of mainmenu function
//begining of sortpath function
void sortpath(int& totalmile, float& totaltime, road
allroad[10], char& root)
{
int
temptime, tempmile;
char con =
root;
for(int
y=1; y <= 2; y++)
{
for(int x=0; x < 10; x++)
{
con
= allroad[x].connect;
if
((con =='con') || (con == 'u'))
{
temptime += allroad[x].time;
tempmile += allroad[x].mile;
}
}
//compare the total distance
if(tempmile < totalmile)
{
totaltime = temptime;
totalmile = tempmile;
root = con;
}
con = 'b';
}
}// end of sortpath function
//beginig of decision function
//use Active Logic to make decision
void decision(char accident, char hour, road
allroad[10],float totaltime,int totalmile, char root,string street, int date)
{
char
now[3];//store conclusion
now[3] =
'y'; //now[3] is future step. It has positive value
//making
decision for now[0], now[1], now[2].
if (accident == 'y')
{ if (findstreet(allroad, street) ==
'y')
now[0] = 'n';
} else
now[0] = 'y';
if (hour ==
'r')
now[1] = 'n';
else now[1] = 'y';
if
(holiday(date) =='y')
now[2] = 'y';
else now[2] = 'n';
//making final decision
for(int x = 0; x < 2;x++)
{
if((now[x] == 'y') || (now[x+1] ==
'y'))
now[3]
= 'y';
else now[3] = 'n';
}
//if now[3] is 'y' then display the
result
//else find the another road
if (now[3] == 'y')
display(root,allroad, totaltime,
totalmile);
else {
for(int
z = 0; z < 10; z++)
{
if (allroad[z].connect == root)
allroad[z].connect
= 'n';
}
sortpath(totalmile,
totaltime, allroad, root);
display(root,
allroad, totaltime, totalmile);
}
}//end of decision function
//subfunction of decision
//begining of findstreet
char findstreet(road allroad[10], string street)
{
char result
= 'n';
for(int
x=0; x < 10; x++)
{
if (street == allroad[x].names)
result = 'y';
}
return
result;
}//end of findstreet
//subfunction of decision
//beginng of holiday
char holiday(int date)
{
char
result;
switch(date)
{
case 1:
case 25:
case 8:
case 23:
case 17:
result = 'y';
break;
default:
result = 'n';
}
return
result;
}//end of holiday
//begining of loadroad function
//load street into memory
void loadroad(ifstream& eds,road allroad[10])
{
string
streets;
int
nummile, time, x;
char
connected, traffilight;
//read
first street
eds>>streets>>connected>>nummile>>time>>traffilight;
x = 0;
while(!eds.eof())
{
//storing information into array
allroad[x].names = streets;
allroad[x].connect = connected;
allroad[x].mile = nummile;
allroad[x].time = time;
allroad[x].traclight = traffilight;
//updating counter
x+=1;
//read next street
eds>>streets>>connected>>nummile>>time>>traffilight;
} // end
while
}//end of loadroad function
//display the result
//beigning of display function
void display(char root, road allroad[10], int totaltime, int
totalmile)
{
cout<<"
Road plan"<<endl;
cout<<"---------------------"<<endl;
for(int x
=0; x < 10;x++)
{
if((allroad[x].connect == root) ||
(allroad[x].connect == 'u'))
cout<<allroad[x].names<<endl;
}
cout<<endl;
cout<<"Distances
is: "<<totalmile<<endl;
totaltime =
totaltime / 2;
cout<<"Average mph:
"<<totaltime<<endl;
}//end of display function
Data
file:road.dat
Norristow u 0 1 y
476south a 2 3 n
363north b 3 1 y
76east a 7 2 n
73east b 12 1 y
roosbelt a 3 3 n
309south b 4 2 n
cheltelham b 2 2 y
broad b 4 2 y
midbroad u 4 2 y
Temple u 0 2 y