用c++写一个基于tsp文件最短路径生成图片的代码,使用同目录下叫arr的tsp文件,生成后的图像文件也在同目录下
时间: 2024-02-05 08:12:37 浏览: 58
最短路径C++代码.zip
以下是基于tsp文件最短路径生成图片的c++代码:
```c++
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <opencv2/opencv.hpp>
using namespace std;
using namespace cv;
const double PI = 3.14159265358979323846;
struct Point {
int x;
int y;
};
vector<Point> points;
void readTSPFile(string filepath) {
ifstream file(filepath);
string line;
int num_points = 0;
bool is_data = false;
while (getline(file, line)) {
if (line == "NODE_COORD_SECTION") {
is_data = true;
continue;
}
if (is_data) {
if (line == "EOF") {
break;
}
Point point;
sscanf(line.c_str(), "%d %d %d", &num_points, &point.x, &point.y);
points.push_back(point);
}
}
}
double distance(Point p1, Point p2) {
return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}
void drawPath(Mat& img, vector<int>& path) {
for (int i = 0; i < path.size() - 1; i++) {
Point p1 = points[path[i]];
Point p2 = points[path[i+1]];
line(img, Point(p1.x, p1.y), Point(p2.x, p2.y), Scalar(0, 0, 255), 2);
}
Point p1 = points[path[0]];
Point p2 = points[path[path.size()-1]];
line(img, Point(p1.x, p1.y), Point(p2.x, p2.y), Scalar(0, 0, 255), 2);
}
void generateImage(vector<int>& path) {
int width = 800;
int height = 600;
Mat img(height, width, CV_8UC3, Scalar(255, 255, 255));
drawPath(img, path);
imwrite("path.png", img);
}
int main() {
string filepath = "arr.tsp";
readTSPFile(filepath);
vector<int> path(points.size());
for (int i = 0; i < points.size(); i++) {
path[i] = i;
}
double min_distance = distance(points[path[0]], points[path[1]]);
do {
double distance_sum = 0;
for (int i = 0; i < path.size() - 1; i++) {
distance_sum += distance(points[path[i]], points[path[i+1]]);
}
if (distance_sum < min_distance) {
min_distance = distance_sum;
generateImage(path);
}
} while (next_permutation(path.begin(), path.end()));
return 0;
}
```
在同目录下放置名为"arr.tsp"的tsp文件,运行程序后会生成名为"path.png"的图片文件,显示出最短路径。
阅读全文