text2

#include
#include
#include
#include
#include
#include
#include

using namespace std;

struct Point {
int id;
double x;
double y;
};

clock_t start_time;

double distance(const Point& p1, const Point& p2) {
double dx = p1.x - p2.x;
double dy = p1.y - p2.y;
return sqrt(dx * dx + dy * dy);
}

double path_length(const vector& points, const vector& path) {
double length = 0.0;
for (int i = 0; i < path.size() - 1; ++i) {
length += distance(points[path[i]], points[path[i + 1]]);
}
length += distance(points[path.back()], points[path[0]]);
return length;
}

vector generate_neighbor(const vector& path) {
vector neighbor = path;
int i = rand() % path.size();
int j = rand() % path.size();
reverse(neighbor.begin() + min(i, j), neighbor.begin() + max(i, j) + 1);
return neighbor;
}

vector simulated_annealing(const vector& points, const vector& initial_path, double initial_temp, double cooling_rate) {
vector current_path = initial_path;
vector best_path = initial_path;
double current_length = path_length(points, current_path);
double best_length = current_length;
double temperature = initial_temp;

while (temperature > 1.0 && double(clock() - start_time) / CLOCKS_PER_SEC < 59.5){
    vector neighbor = generate_neighbor(current_path);
    double neighbor_length = path_length(points, neighbor);
    double delta_length = neighbor_length - current_length;

    if (delta_length < 0 || (rand() / (RAND_MAX + 1.0) < exp(-delta_length / temperature))) {
        current_path = neighbor;
        current_length = neighbor_length;

        if (current_length < best_length) {
            best_path = current_path;
            best_length = current_length;
        }
    }

    temperature *= cooling_rate;
}

return best_path;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

}

int main() {
vector points;
int point_id;
double x, y;
start_time = clock();
ifstream input_file("./points.txt");
if (!input_file.is_open()) {
cerr << “Failed to open input file.” << endl;
return 1;
}

while (input_file >> point_id >> x >> y) {
    points.push_back({point_id, x, y});
}
input_file.close();

int n = points.size();

srand(static_cast(time(nullptr)));

vector initial_path(n);
for (int i = 0; i < n; ++i) {
    initial_path[i] = i;
}
random_shuffle(initial_path.begin() + 1, initial_path.end());

double initial_temperature = 10000.0;
double cooling_rate = 0.999995;


vector best_path = simulated_annealing(points, initial_path, initial_temperature, cooling_rate);


ofstream output_file("output.txt");
if (!output_file.is_open()) {
    cerr << "Failed to open output file." << endl;
    return 1;
}

for (int i : best_path) {
    if(points[i].id<10){
        output_file << "00" <