СломанныйКоммивояжер

// TravellingSalesman.cpp : Этот файл содержит функцию "main". Здесь начинается и заканчивается выполнение программы.
//

#include <iostream>
#include <vector>
#include <ctime>
#include <random>

const int N = 500;


using namespace std;
default_random_engine eng;

using Graph = vector<vector<double>>;
using NN = vector<double>;//сеть с нейронами, где нейрон - это double
using Weights = vector<vector<double>>;
using Ways = vector<int>;

void GraphPrinter(Graph graph) {
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < graph.size(); j++)
            cout << graph[i][j] << " ";
        cout << endl;
    }
}
void WaysPrinter(Ways ways) {
    for (int i = 0; i < ways.size(); i++)
        cout << ways[i] << " ";
    cout << endl;
}

void NNPrinter(NN nn) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << round(nn[i * N + j]) << " ";
        cout << endl;
    }
}
Graph GraphGenerator() {
    Graph graph(N);
    for (int i = 0; i < graph.size(); i++) {
        graph[i].resize(N);
    }
    uniform_real_distribution<double> distr(1, 10);
    for (int i = 0; i < graph.size(); i++) {
        for (int j = 0; j < i; j++) {
            double dist = distr(eng);
            graph[i][j] = dist;
            graph[j][i] = graph[i][j];
        }
    }
    return graph;
}

/*Weights WeightsCalculator(Graph graph, double A = 20, double B = 20, double C = 10, double D = 0.14) {*/
Weights WeightsCalculator(Graph graph, double A, double B, double C, double D) {
    Weights weights(N * N);
    for (int i = 0; i < weights.size(); i++) {
        weights[i].resize(N * N);
    }
    for (int index = 0; index < N * N; index++) {
        int x = index / N;
        int i = index % N;
        for (int endex = 0; endex < N * N; endex++) {
            int y = endex / N;
            int j = endex % N;
            double w = 0;
            if (x == y && i != j)
                w -= A;
            if (x != y && i == j)
                w -= B;
            w -= C;
            if (j == i + 1 || j == i - 1)
                w -= (D * graph[x][y]);
            if ((j == 0 && i == N - 1)  || (j == N - 1 && i == 0))
                w -= (D * graph[x][y]);
            if (index == endex) w = 0;
            weights[index][endex] = w;
        }
    }
    return weights;
}

void NeuronUpdater(NN& nn, Weights weights, double C, int j) {
    double NET = 0;
    for (int i = 0; i < nn.size(); i++)
        NET += weights[i][j] * nn[i];
    double w_0_j = C * (N - 0.5);
    NET += w_0_j;
    double u_0 = 1;
    /*if (NET > 0)
        nn[j] = 1;
    if (NET < 0)
        nn[j] = 0;*/
    nn[j] = 0.5 * (1 + tanh(NET / u_0));
}

double EnegryChecker(NN nn, Weights weights, double C) {
    double E = 0;
    double w_0_j = C * (N - 0.5);
    for (int i = 0; i < nn.size(); i++)
        for (int j = 0; j < nn.size(); j++)
            E += weights[i][j] * nn[i] * nn[j];
    E *= -0.5;

    for (int j = 0; j < nn.size(); j++)
        E -= (w_0_j * nn[j]);
    return E;
}

bool OkayNNChecker(NN nn, Ways& ways) {
    ways.resize(N);
    int counter1 = 0, counter2 = 0;
    for (int i = 0; i < N; i++) {
        int counter1 = 0;
        for (int j = 0; j < N; j++) {
            int index = i * N + j;
            if (nn[index] >= 0.5) {
                counter1++;
                ways[j] = i;
            }
        }
        counter2 = 0;
        for (int k = 0; k < N; k++) {
            if (nn[i + k * N] >=0.5)
                counter2++;
        }
        if (counter1 != 1 || counter2 != 1) return false;
    }
    return true;
}
double LengthCounter(Ways ways, Graph graph) {
    double length = 0;
    for (int i = 0; i < N - 1; i++)
        length += graph[ways[i]][ways[i + 1]];
    length += graph[ways[0]][ways[N - 1]];
    return length;

}
void NNFilling(NN& nn) {
    for (int i = 0; i < N; i++)
        nn[i] = rand() % 2;
}
//нужно сделать чтобы в каждом городе ровно 1 единица матрицы nn и в кадждый момент времени был только один город
// найти длину пути
bool NarayanaPermutation(Ways &ways) {

    int index=-1;
    for (int i = (N - 2); i >= 0; i--) {
        if (ways[i] < ways[i + 1]) {
            index = i;
            break;
        }
    }
    if (index == -1)
        return false;
    for (int j = (N - 1); j > index; j--) {
        if (ways[index] < ways[j]) {
            swap(ways[index], ways[j]);
            break;
        }
    }
    reverse(ways.begin() + (index + 1), ways.end());
    return true;
}

Ways OrdinaryTravelingSalesman(Graph graph) {
    Ways ways(N); Ways minimalWays(N);
    for (int i = 0; i < N; i++)
        ways[i] = i;
    double min = INFINITY;
    while (true) {
        double newMinimum = LengthCounter(ways, graph);
        if (newMinimum < min) {
            min = newMinimum;
            minimalWays = ways;
        }
        if (!NarayanaPermutation(ways)) break;
    }
    return minimalWays;
}
Ways WorstOrdinaryTravelingSalesman(Graph graph) {
    Ways ways(N); Ways maximumWays(N);
    for (int i = 0; i < N; i++)
        ways[i] = i;
    double max = -INFINITY;
    while (true) {
        double newMinimum = LengthCounter(ways, graph);
        if (newMinimum > max) {
            max = newMinimum;
            maximumWays = ways;
        }
        if (!NarayanaPermutation(ways)) break;
    }
    return maximumWays;
}
int main()
{

    Graph graph = GraphGenerator();
    srand(time(0));
    //GraphPrinter(graph);
    cout << endl;
    Weights weights1 = WeightsCalculator(graph,20,20,10,0.14);
    Weights weights2 = WeightsCalculator(graph, 5, 5, 5, 0.5);

    Ways ways(N, 0);
    /*Ways ordindaryWays = OrdinaryTravelingSalesman(graph);
    WaysPrinter(ordindaryWays);
    cout << LengthCounter(ordindaryWays, graph) << endl;
    Ways WorstordindaryWays = WorstOrdinaryTravelingSalesman(graph);
    WaysPrinter(WorstordindaryWays);
    cout << LengthCounter(WorstordindaryWays, graph) << endl;*/

    double sum = 0;
    double best = INFINITY;
    for (int test = 0; test < 10; test++) {
        NN nn(N * N);
        NNFilling(nn);
        for (int i = 0; i < 40; i++) {
            for (int j = 0; j < 100; j++)
                NeuronUpdater(nn, weights2, 5, rand() % (N * N));
            for (int j = 0; j < 100; j++)
                NeuronUpdater(nn, weights2, 5, j);
            for (int j = 0; j < 100; j++)
                NeuronUpdater(nn, weights1, 10, rand() % (N * N));
            for (int j = 0; j < 100; j++)
                NeuronUpdater(nn, weights1, 10, j);
            double E = EnegryChecker(nn, weights1, 10);

            //if (i % 200 == 0) {
            ways.clear();
            bool NNCheck = OkayNNChecker(nn, ways);
            if (NNCheck) {
                cout << "Count 1 in NN: " << NNCheck << endl;
                WaysPrinter(ways);
                cout << LengthCounter(ways, graph) << endl;
                cout << endl;

            }
            else
                cout << "Fail\n";
            //NNPrinter(nn);
            cout << endl;
            cout << "E: " << E << endl;
            //}

            if (i == 39 && NNCheck) {
                double l = LengthCounter(ways, graph);
                sum += l;
                if (l < best) best = l;
            }
        }

    }
    cout << "Average: " << sum / 10 << endl;
    cout << "Best: " << best << endl;
}