I\'m having difficulty with the logic of this program. Please help!! For this pr

Question

I'm having difficulty with the logic of this program. Please help!!

For this program you will be given a list of city names and x, y coordinates that signify the location of the city. You will store the list of cities in an array of structures and then use that array to write a series of functions.The data will be in a text file named "route_data.txt" and will be in the following format:

city x_coord y_coord

e.g.

Houston 0.5 1.6
Denver -1.5 4.2

etc.

The cities are in order. The first city is your home city. You will figure out how far it is from your home city to the last city in the list by moving from city to city in the list and calculating the total distance (we are assuming that we have cars that fly through the air and can use a straight line distance). Then you will write a function to improve the ability to visit each city once (the last city you visit may change).

You will write four functions for this program:

//reads the initial data from the input file
//returns false if the file is not opened correctly
bool getData(string inputFile, City cities[], int &numCities);

//prints the cities in order, one per line
void printRoute(City cities[], int numCities);

//calculates the distance from one city to the next
double getDistance(City city1, City city2);

//calculates the total distance from the first city to the last city
double totalDistance(City cities[], int numCities);

//uses an algorithm to make the total distance shorter than the initial distance (if possible)
void improveRoute(City cities[], int numCities);

Your main program should have the following algorithm:

get the data

print the route

show the total distance

improve the route

print the route

show the total distance

display the percentage improvement

The input file is named route_data.txt consisting of the following coordinates:

Explanation / Answer

/****************************************************
File Name: route.cpp
Pulls locations of several cities and optimizes the route between them.
*****************************************************/

#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

struct City
{
string name;
double x;
double y;
};

bool getData(string inputFile, City cities[], int &numCities);//checks to see if text file is readable and populates City array
double getDistance(City city1, City city2);//finds distance between two cities
double totalDistance(City cities[], int numCities);//finds total distance between all cities in a certain route
void greedyRouteImprove(City cities[], int numCities, const int MAX_CITIES);//finds an improved route based on getting nearest city
void hungarianMethodRouteImprove(City cities[], int numCities);//uses the hungarian method to find THE most optimal route

int main()
{
const int MAX_CITIES = 99;
int numCities = 0;
City cities[MAX_CITIES];

string inputFile = "route_data.txt";

if (getData(inputFile, cities, numCities))
{
cout << "Current Route: ";
for (int i = 0; i < numCities; i++)
cout << cities[i].name << endl;
//setw(5) << " " << setw(4) << cities[i].x << ", " << cities[i].y << endl;

cout << " Distance between cities: ";
for (int d = 0; d < numCities - 1; d++)
cout << setw(10) << cities[d].name << setw(4) << " -> " << left << setw(8) << cities[d+1].name << ": "
<< setprecision(2) << fixed << setw(9) << getDistance(cities[d], cities[d+1]) << endl;

cout << " Total distance: " << totalDistance(cities, numCities) << endl;

//greedyRouteImprove(cities, numCities, MAX_CITIES);
hungarianMethodRouteImprove(cities, numCities);
}
return 0;
}

bool getData(string inputFile, City cities[], int &numCities)
{
ifstream inFile;
inFile.open("route_data.txt");
if (inFile)
{
string name;
while (inFile >> name)
{
cities[numCities].name = name;
inFile >> cities[numCities].x;
inFile >> cities[numCities].y;

numCities++;
}
return true;
}
else
return false;
}

double getDistance(City city1, City city2)
{
return (sqrt(pow((city2.y - city1.y),2) + pow((city2.x - city1.x),2)));
}

double totalDistance(City cities[], int numCities)
{
double distance = 0;

for (int t = 0; t < numCities-1; t++)
distance += getDistance(cities[t],cities[t+1]);

return distance;
}

void greedyRouteImprove(City cities[], int numCities, const int MAX_CITIES)
{
cout << " [----------------------] ";
cout << " Improved Route: ";

bool valid;

City betterCities[MAX_CITIES];

betterCities[0] = cities[0];
double smallestDistance = 99;

for (int a = 0; a < numCities; a++)//iterates through betterCities array
{
for (int b = 1; b < numCities; b++)//iterates through cities array
{
if (getDistance(betterCities[a], cities[b]) < smallestDistance)
{
valid = true;//determines if a city is valid based if it's already used
for (int w = 0; w < numCities; w++)
{
if (betterCities[w].name == cities[b].name)
valid = false;
}
if(valid)
{
betterCities[a+1] = cities[b];
smallestDistance = getDistance(betterCities[a], cities[b]);
}
}
}
smallestDistance = 99;
}

for (int p = 0; p < numCities; p++)
cout << betterCities[p].name << endl;

cout << " Distance between cities: ";
for (int d = 0; d < numCities - 1; d++)
cout << setw(10) << betterCities[d].name << setw(4) << " -> " << left << setw(8) << betterCities[d+1].name << ": "
<< setprecision(2) << fixed << setw(9) << getDistance(betterCities[d], betterCities[d+1]) << endl;

cout << " Total distance: " << totalDistance(betterCities, numCities) << endl << endl;

cout << " >>> " << totalDistance(cities, numCities) / totalDistance(betterCities, numCities) << "x better <<< ";
}

void hungarianMethodRouteImprove(City cities[], int numCities)
{
double distancesArray[numCities][numCities];
double cleanDistancesArray[numCities][numCities];

for (int a = 0; a < numCities; a++)
for (int b = 0; b < numCities; b++)
distancesArray[a][b] = (getDistance(cities[a], cities[b]));

for (int r = 0; r < numCities; r++)
{
for (int c = 0; c < numCities; c++)
{
if (distancesArray[r][c] == 0.00)
{
distancesArray[r][c] = -1.00;
}
//cout << distancesArray[r][c] << ", ";
}
//cout << endl;
}

std::copy(&distancesArray[0][0], &distancesArray[0][0]+numCities*numCities,&cleanDistancesArray[0][0]);//copies arrays to be used later

const int BY = numCities;

int round = 0;
double totalDistance = 0;
int pathArray [BY];

while(round < BY)
{
cout << "Matrix: " << endl;
for (int a = 0; a < BY; a++)
{
cout << setw(5);
for (int b = 0; b < BY; b++)
{
cout << setw(5) << distancesArray[a][b] << " | ";
}
cout << endl;
}
cout << endl;

double minR = 99.0;
double minC = 99.0;

for (int r = 0; r < BY; r++) //row minimization
{
for (int c = 0; c < BY; c++)
if (distancesArray[r][c] < minR && distancesArray[r][c] != -1)
minR = distancesArray[r][c];

for (int iC = 0; iC < BY; iC++)
if (distancesArray[r][iC] != -1)
distancesArray[r][iC] = (distancesArray[r][iC] - minR);
minR = 99;
}

cout << "Row Reduced Matrix: " << endl;
for (int a = 0; a < 5; a++)
{
cout << setw(5);
for (int b = 0; b < BY; b++)
cout << setw(5) << distancesArray[a][b] << " | ";
cout << endl;
}
cout << endl;

for (int c = 0; c < BY; c++) //column minimization
{
for (int r = 0; r < BY; r++)
if (distancesArray[r][c] < minC && distancesArray[r][c] != -1)
minC = distancesArray[r][c];

for (int iR = 0; iR < BY; iR++)
if (distancesArray[iR][c] != -1)
distancesArray[iR][c] = (distancesArray[iR][c] - minC);
minC = 99;
}

cout << "Column Reduced Matrix: " << endl;
for (int a = 0; a < BY; a++)
{
cout << setw(5);
for (int b = 0; b < BY; b++)
cout << setw(5) << distancesArray[a][b] << " | ";
cout << endl;
}
cout << endl;

double penalty = 0;
double penaltyArray[BY][BY];
double minRow = 99.0;
double minCol = 99.0;

for (int x = 0; x < BY; x++)
for (int y = 0; y < BY; y++)
penaltyArray[y][x] = 0.00;

for (int a = 0; a < BY; a++)//row
{
for (int b = 0; b < BY; b++)//column
{
if (distancesArray[a][b] == 0)
{
distancesArray[a][b] = 100.0;
for (int c = 0; c < BY; c++)
{
if (distancesArray[a][c] < minRow && distancesArray[a][c] != -1)
minRow = distancesArray[a][c];
}
for (int r = 0; r < BY; r++)
{
if (distancesArray[r][b] < minCol && distancesArray[r][b] != -1)
minCol = distancesArray[r][b];
}
penaltyArray[a][b] = (minRow + minCol);
minRow = 99.0;
minCol = 99.0;
distancesArray[a][b] = 0;
}
}
}

double greatestPenalty = 0.0;

cout << "Penalty Matrix: " << endl;
for (int a = 0; a < BY; a++)
{
cout << setw(5);
for (int b = 0; b < BY; b++)
{
cout << setw(5) << penaltyArray[a][b] << " | ";
if (penaltyArray[a][b] > greatestPenalty)
greatestPenalty = penaltyArray[a][b];
}
cout << endl;
}

int> int scratchR = 0;
int scratchC = 0;

for (int a = 0; a < BY; a++)
for (int b = 0; b < BY; b++)
if (penaltyArray[a][b] == greatestPenalty)
while (oneCount < 1)
{
cout << " Location: " << a << " -> " << b << endl;
pathArray[a] = b;
totalDistance += cleanDistancesArray[a][b];
scratchR = a;
scratchC = b;
oneCount++;
}
distancesArray[scratchC][scratchR] = -1;

for (int r = 0; r < BY; r++)
distancesArray[r][scratchC] = -1;
for (int c = 0; c < BY; c++)
distancesArray[scratchR][c] = -1;

//cout << " Reduced Matrix: " << endl;
for (int a = 0; a < BY; a++)
{
for (int b = 0; b < BY; b++)
{
//cout << distancesArray[a][b] << " ";
if (penaltyArray[a][b] > greatestPenalty)
greatestPenalty = penaltyArray[a][b];
}
//cout << endl;
}
round++;
}

int stop = 0;
int city = 0;
cout << " Route: ";
while (stop < BY -1)
{
//cout << city << " -> " << pathArray[city] << ", ";
city = pathArray[city];
stop++;
}

for (int i = 0; i < BY; i++)
cout << i << "->" << pathArray[i] << ", ";
cout << " Total distance: " << totalDistance << endl;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.