Это школьный проект, в котором мы должны найти общее кратчайшее расстояние, пройденное до всех точек один раз, без возврата к исходной точке. Я решил это, используя метод ближайшего соседа, однако иногда он не дает самый быстрый маршрут. Есть ли алгоритмы, которые я могу использовать, чтобы решить эту проблему? Я хотел попробовать использовать 2-Opt Swap, однако для этого необходимо подключить все точки.
Вот мой основной код:
// Mini Proj.cpp : This file contains the 'main' function. Program execution begins and ends there.
#include <iostream>
#include <list>
#include <iterator>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
// #pragma warning(disable : 4996) // turn off warnings for error code
using namespace std;
int numArr[20]; // Set to 20 for redundancy, in case there's a lot of locations
// Display Code Keilaash
int rack_length;
int rack_height;
int id = 49;
// typedef for easier use.
typedef vector<vector<char>> Matrix;
typedef vector<char> Row;
// Class to hold Location's X and Y value
class Location
{
public:
int m_x;
int m_y;
Location()
{
m_x = -1;
m_y = -1;
};
Location(int x, int y)
{
m_x = x;
m_y = y;
};
};
/* Make matrix of all 0s. */
void setup_matrix(Matrix &matrix) // Matrix is access matrix[y][x]
{
// asigning values, I suppose this is done allready.
for ( int y = rack_height-1 ; y >= 0 ; y-- ) // start from top left
{
vector<char> row(rack_length);
for (int x = 0; x < rack_length; x++)
{
row[x] = '0';
}
matrix.push_back(row);
}
}
/* Initialise matrix with home and points */
void preset_matrix(int x, int y, Matrix &matrix) // Set X then set Y
{
matrix[0][0] = 'H';
matrix[y][x] = 'X';
}
/* mark location as being visited. */
void update_matrix(int x, int y, Matrix &matrix) // Set X then Set Y
{
matrix[y][x] = id ;
id++;
}
/* display the matrix on the screen */
void display_matrix(Matrix &matrix)
{
// matrix is accessed as matrix[y][x]
cout << "\nMatrix Output:" << endl;
for (int y = rack_height-1 ; y >= 0 ; y--) // loop 3 times for three lines
{
for (int x = 0 ; x < rack_length ; x++) // loop for the three elements on the line
{
cout << matrix[y][x]; // display the current element out of the array
}
cout << endl; // when the inner loop is done, go to a new line
}
cout << endl;
}
int main()
{
int numElements;
ifstream readIn;
string fileName;
for (int i = 0; i <= 20; i++)
{
numArr[i] = i;
}
cout << "What is the name of the file you would like to open (please include the .txt extension): ";
cin >> fileName;
readIn.open(fileName.c_str()); // Open text file for subsequent information retrieval
// Error check, to notify the user if there was trouble opening the file
if (!readIn)
{
cout << "There was an error opening the file you wanted" << endl;
}
else
{
int inputCount = 0;
for (int i = 0; i < 20; i++)
{
readIn >> numArr[i];
if (readIn)
{
inputCount++;
}
}
inputCount -= 2;
// cout << inputCount << endl; // Count the number of individual co-ordinates that were put into the text file (Xi, Yi)
cout << "Total X length: " << numArr[0] << endl;
cout << "Total Y length: " << numArr[1] << endl;
int y = 2, z = 3;
for (int i = 0; i < inputCount; i++)
{
if (i < inputCount / 2)
{
cout << "Location " << i + 1 << ": " << numArr[y] << ", " << numArr[z] << endl;
y += 2;
z += 2;
}
}
// Save data into variables
rack_length = numArr[0];
rack_height = numArr[1];
numElements = inputCount;
}
/* List of Location */
list<Location> locationList, sortedLocationList;
list<Location>::iterator it, iteratorShortest;
/* Create list of locations */
vector<int> xCoordinates;
vector<int> yCoordinates;
// Transfer xy from array to vectors
for (int i = 2; i < numElements + 2; i++)
{
if (i % 2 == 0) // even
{
xCoordinates.push_back(numArr[i]);
}
else // odd
{
yCoordinates.push_back(numArr[i]);
}
}
/* Safety Checks */
// ensure proper tally of x and y coordinates
if ( xCoordinates.size() != yCoordinates.size() )
{
cout << "\nNumber of x and y coordinates do not match" << endl;
return -1;
}
// ensure rack size larger than points in rack.
double maxXCoordinate = *max_element(xCoordinates.begin(), xCoordinates.end()); // max element returns iterator
double maxYCoordinate = *max_element(yCoordinates.begin(), yCoordinates.end()); // max element returns iterator
if (maxXCoordinate > rack_length || maxYCoordinate > rack_height)
{
cout << "\nYour xy coordinate is not in rack_length or rack_height" << endl;
return -1;
}
int numberOfLocations = xCoordinates.size();
Matrix matrix;
setup_matrix(matrix);
// initialise Location nodes for algorthim and display
for (int i = 0; i < numberOfLocations; i++)
{
Location location(xCoordinates[i], yCoordinates[i]);
locationList.push_back(location);
preset_matrix(xCoordinates[i], yCoordinates[i], matrix);
}
/* Greedy Algorithm */
int currentX = 0;
int currentY = 0;
int listSize = locationList.size();
for (int i = 0; i < listSize; i++)
{
int shortestDistance = -1; // -1 indicates undefined
// reset iterator
iteratorShortest = locationList.begin();
// Loops through location list, finding the shortest distance from start location to next location.
for (it = locationList.begin(); it != locationList.end(); it++)
{
// Find Difference in X and Y coordinates
int xDiff = abs((*it).m_x - currentX);
int yDiff = abs((*it).m_y - currentY);
int distance = xDiff + yDiff;
if (distance < shortestDistance || shortestDistance == -1)
{
//cout << "new shortest distance found " << distance << endl; //DEBUG
shortestDistance = distance;
// save shortest element's iterator
iteratorShortest = it;
}
else
{
//cout << "not longer" << endl; //DEBUG
}
}
// add location to sorted list
sortedLocationList.push_back(*iteratorShortest);
/* Reset algortihm to find next closest node*/
// set new value for current x and y
currentX = (*iteratorShortest).m_x;
currentY = (*iteratorShortest).m_y;
// Remove found element from list
locationList.erase(iteratorShortest);
}
/* Display list of locations */
display_matrix(matrix);
for (it = sortedLocationList.begin(); it != sortedLocationList.end(); it++)
{
update_matrix( (*it).m_x , (*it).m_y , matrix);
display_matrix(matrix);
}
return 0;
}
И это мой текстовый файл с именем rack1.txt:
10
10
6
0
2
3
4
1
4
4
6
7
6
1
7
1
Любая помощь будет оценена! ??