Algoritmia - estudiante

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#define N 5 // Número de ciudades

#define INF 999999999

typedef struct {

    int x, y;

} City;

double distance(City a, City b) {

    int dx = a.x - b.x;

    int dy = a.y - b.y;

    return sqrt(dx * dx + dy * dy);

}

double totalDistance(int path[], City cities[]) {

    double total = 0;

    for (int i = 0; i < N - 1; i++) {

        total += distance(cities[path[i]], cities[path[i + 1]]);

    }

    total += distance(cities[path[N - 1]], cities[path[0]]);

    return total;

}

void swap(int *a, int *b) {

    int temp = *a;

    *a = *b;

    *b = temp;

}

double simulatedAnnealing(City cities[]) {

    int currentPath[N];

    int newPath[N];

    double currentDistance, newDistance, delta, acceptanceProbability;

    double temperature = 1000.0;

    double coolingRate = 0.995;

    // Inicializar la ruta actual de forma aleatoria

    for (int i = 0; i < N; i++) {

        currentPath[i] = i;

    }

    currentDistance = totalDistance(currentPath, cities);

    while (temperature > 1.0) {

        // Generar una nueva ruta permutando dos ciudades

        for (int i = 0; i < N; i++) {

            newPath[i] = currentPath[i];

        }

        int index1 = rand() % N;

        int index2 = rand() % N;

        swap(&newPath[index1], &newPath[index2]);

        newDistance = totalDistance(newPath, cities);

        // Calcular la diferencia entre las distancias

        delta = newDistance - currentDistance;

        // Decidir si se acepta la nueva solución

        if (delta < 0 || ((double)rand() / RAND_MAX) < exp(-delta / temperature)) {

            for (int i = 0; i < N; i++) {

                currentPath[i] = newPath[i];

            }

            currentDistance = newDistance;

        }

        // Reducir la temperatura

        temperature *= coolingRate;

    }

    return currentDistance;

}

int main() {

    City cities[N] = {{0, 0}, {1, 2}, {3, 1}, {5, 2}, {4, 0}};

    double result = simulatedAnnealing(cities);

    printf("Distancia mínima encontrada: %.2f\n", result);

    return 0;

}