//////////////////// // // Name: Round Trip Problem (Console) // Author: Shadow // Version: 1.0.0 // Date: 16.10.2018 // Description: Solution to the round trip problem // (Finding the shortest round trip // through a given set of points). // I have a visualized version up, // this is just for anyone who wants // to delve into the logic behind the // approximation a bit more. // Link to that code is in the // comments. // Planned: - // Input: The coordinates of the starting point // of the route followed by the coordinates // of the waypoints. // (x- and y-coordinate separated by enter) // Example: // 392 // 195 => starting point // 448 // 142 // 387 // 219 => two waypoints // Output: The order of points. // //////////////////// // //////////PREPROCESSOR////////// // #include #include #include #include // //////////CLASSES////////// // struct Coordinates { int x; int y; Coordinates(const int x, const int y) :x{x}, y{y} {} }; class Point { private: Coordinates coordinates; public: Point() :coordinates{0, 0} {} Point(const int x, const int y) :coordinates{x, y} {} Point(const Coordinates& coordinates) :coordinates{coordinates} {} inline int getX() const { return coordinates.x; } inline int getY() const { return coordinates.y; } inline double getVectorLength() const { return std::sqrt ( coordinates.x * coordinates.x + coordinates.y * coordinates.y ); } friend std::istream& operator>>(std::istream&, Point&); friend std::ostream& operator<<(std::ostream&, const Point&); }; // //////////FUNCTIONS////////// // std::istream& operator>>(std::istream& str, Point& point) { str >> point.coordinates.x >> point.coordinates.y; return str; } std::ostream& operator<<(std::ostream& str, const Point& point) { str << "(" << point.coordinates.x << " | " << point.coordinates.y << ")"; return str; } /* calculateDistance takes in two points and * calculates the distance between them. * The formula for this can be found in basically * any maths formula collection. * You simply calculate the length of the vector * connecting those two points. */ double calculateDistance(const Point& a, const Point& b) { return std::sqrt( (b.getX() - a.getX()) * (b.getX() - a.getX()) + (b.getY() - a.getY()) * (b.getY() - a.getY()) ); } /* calculateTourDistance takes in a list of points * and calculates the length of that route by * adding up the distances between the points. * Nothing major, just a helper function. */ double calculateTourDistance(const std::list& tour) { double distance {0.0}; for (auto it = tour.cbegin(); it != std::prev( tour.cend() ); ++it) { distance += calculateDistance( *it, *std::next( it ) ); } return distance; } /* Now for the actual algorithm. * The easiest solution to finding the shortest * route would be to calculate every route * possible and to compare the lengths * of those routes. Easy. * However, with an increasing amount of * waypoints, this solution becomes less elegant. * Say, you want to visit all capitals of the * members of the Europian Union. * There are currently 28 members, meaning you * would have to calculate (28 - 1)! possible * routes, which is quite a chunk. * One possible solution is to integrate the * furthest waypoints into the route in an * 'intelligent' way. * To be able to to that, we first need to * determine the furthest point in regard to * an existing route. * Essentially , we want to find one specific * point whose smallest distance to the route * (the smallest distance to one of its points) * is the biggest possible. */ std::list::const_iterator getIndexOfFarestPoint(const std::list& route, const std::list& points) { /* iterator to the route point that is the * corresponding point for the furthest point. */ auto indexOfRoutePoint = route.cbegin(); /* iterator to the furthest point */ auto indexOfFarestPoint = points.cbegin(); /* iterate through all available points to test */ for (auto pt = points.cbegin(); pt != points.cend(); ++pt) { /* calculate the distance from one point to * each point in the route, */ auto rt = route.cbegin(); double distance = calculateDistance( *pt, *rt ); for ( ; rt != std::prev( route.cend() ); ++rt) { double currentDistance = calculateDistance( *pt, *rt ); /* find the smallest distance to one of the points */ if (currentDistance < distance) { distance = currentDistance; } } /* if the smallest distance from the point to * the route is bigger than the distance from * the currently furthest point, replace it. */ if ( distance > calculateDistance( *indexOfFarestPoint, *indexOfRoutePoint ) ) { indexOfRoutePoint = rt; indexOfFarestPoint = pt; } } /* return the iterator to the furthest point */ return indexOfFarestPoint; } /* Now that we know the furthest point to * the route, we want to insert in into * the route in a meaningful way, * so that the new route's length is * as small as possible. */ std::list::iterator getIndexOfBestInsert(std::list& route, const Point& point) { /* To do so, we iterate over the list and * insert the furthest point once in each place, * calculate the length of that route and compare * those lengths. */ auto indexOfBestInsert = std::next( route.begin() ); route.insert( std::next( route.begin() ), point ); double distance = calculateTourDistance(route); route.erase( std::next( route.begin() ) ); for (auto it = std::next( route.begin(), 2 ); it != route.end(); ++it) { route.insert(it, point); double currentDistance = calculateTourDistance(route); route.erase( std::prev(it) ); if (currentDistance < distance) { indexOfBestInsert = it; distance = currentDistance; } } /* Afterwards, we return an iterator to the place * in the route where the point should be * inserted for a shortest route possible. */ return indexOfBestInsert; } /* Now, we can stuck our algorithm together. * In the beginning, the route only consist * of the starting and ending point. * While there are still waypoints left, * we determine the furthest point to the route, * insert it in a way that the new route is as * short as possible and then remove that point * from the list of waypoints. */ std::list approximateTour(std::list waypoints, const Point& startingPoint) { std::list tour {startingPoint, startingPoint}; while ( !waypoints.empty() ) { auto indexOfFarestPoint = getIndexOfFarestPoint( tour, waypoints ); auto indexOfBestInsert = getIndexOfBestInsert( tour, *indexOfFarestPoint ); tour.insert( indexOfBestInsert, *indexOfFarestPoint ); waypoints.erase(indexOfFarestPoint); } return tour; } /* And that's pretty much everything that * is there to this algorithm. * Of course, there are other ways * to solving this problem, * but for now, this is the best * approximation I've found so far. */ // //////////MAIN FUNCTION////////// // int main() { Point startingPoint; std::cout << "Please enter a starting point."; std::cin >> startingPoint; std::list waypoints; Point point; std::cout << "\nPlease enter the waypoints now."; while (std::cin >> point) { waypoints.push_back(point); } std::cout << "\n\nYour input:"; std::cout << "\n" << startingPoint; for (const Point& point : waypoints) { std::cout << "\n" << point; } std::cout << "\n" << startingPoint; std::list sortedWaypoints( approximateTour( waypoints, startingPoint ) ); std::cout << "\n\nThe route is as following:"; for (const Point& point : sortedWaypoints) { std::cout << "\n" << point; } return 0; }