BoltzmannTravellingSalesman

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

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

const int N = 20;
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++) {
            if (i == j) {
                graph[i][j] = 0;
                graph[j][i] = 0;
                continue;
            }
            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 t) {
    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 p = 1 / (1 + exp(-NET / t));
    if (rand() < p * RAND_MAX)
        nn[j] = 1;
    else
        nn[j] = 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;
    int TESTS = 20;
    for (int test = 0; test < TESTS; test++) {
        cout << "test: " << test << endl;
        NN nn(N * N);
        NNFilling(nn);
        double t = 10*N;
        double difference = t / (40.0 * N * N);
        for (int i = 0; i < 40; i++) {
            t = 0.85 * t + 0.003;
            /*for (int j = 0; j < N * N; j++) {
                NeuronUpdater(nn, weights2, 5, rand() % (N * N),t);
                t *= 0.9999;
            }*/
            /*for (int j = 0; j < N * N; j++) {
                NeuronUpdater(nn, weights2, 5, j, t);
                t *= 0.9999;
            }*/

            for (int j = 0; j < N * N; j++) {
                NeuronUpdater(nn, weights1, 10, rand() % (N * N), t);

            }
            for (int j = 0; j < N * N; j++) {
                NeuronUpdater(nn, weights1, 10, j, t);

            }
            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 << "Temperature: " << t << endl;
            cout << "E: " << E << endl;
            //}

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

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

//написать обычного полного переборного коммивояжера
// энергия при гиперболическом тангенсе не монотонно уменьшается, испытывает скачки, при этом результат, который некронйка считает верным, не имеет минимальную энергию
//Хопфилд через диффуры