BetterNearestNeighborSearch.cpp

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

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

const int N = 30;

using namespace std;
//default_random_engine eng(time(0));
default_random_engine eng;

using Graph = vector<vector<double>>;
using Visit = vector <bool>;
using VisitedPoints = vector<int>;

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;
}
Visit VisitGenerator() {
    Visit visit(N);
    for (int i = 0; i < N; i++)
        visit[i] = false;
    return visit;
}
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;
    }
    cout << endl;
}
void VisitPrinter(Visit visit) {
    for (int i = 0; i < visit.size(); i++)
        cout << visit[i] << " ";
    cout << endl;
}

int NearestWayFinder(Graph graph, int index, double& wayLength, Visit& visit) {
    double minimalWay = INFINITY;
    int minimalWayIndex = 0;
    for (int i = 0; i < N; i++)
        if (graph[index][i] < minimalWay && visit[i] == false) {
            minimalWay = graph[index][i];
            minimalWayIndex = i;
        }
    wayLength += minimalWay;
    return (minimalWayIndex);
}

double TravelingSalesmanNeighbour(Graph& graph, Visit& visit,int i, VisitedPoints &Visited) {

    int visitedCounter = 1;
    int nearestIndex = i;  double wayLength = 0;
    visit[i] = true; Visited.push_back(i);
    while (visitedCounter != N) {
        nearestIndex = NearestWayFinder(graph, nearestIndex, wayLength, visit);
        visitedCounter++;
        visit[nearestIndex] = true; Visited.push_back(nearestIndex);
    }
    wayLength += graph[i][nearestIndex];
    return wayLength;
}

int main() {
    srand(time(0));
    Graph graph = GraphGenerator();
    Visit visit = VisitGenerator();
    GraphPrinter(graph);
    //VisitPrinter(visit);

    vector< VisitedPoints> allVisitedPoints;
    double minWaylen = INFINITY;
    int minWayLenIndex = 0;
    for (int i = 0; i < N; i++) {
        Visit visit = VisitGenerator();
        VisitedPoints Visited;
        double wayLen = TravelingSalesmanNeighbour(graph, visit, i, Visited);
        //cout << "wayLen: " << wayLen << endl;
        if (wayLen < minWaylen) {
            minWaylen = wayLen;
            minWayLenIndex = i;
        }
        /*VisitPrinter(visit);*/
        allVisitedPoints.push_back(Visited);
        //cout << "Visited points: " << endl;
        /*for (int i = 0; i < Visited.size(); i++)
            cout << Visited[i] << " ";
        cout << endl;*/
    }
    cout << "minlenWay: " << minWaylen << endl;
    cout << "minLenWay way:" << endl;
    for (int j = 0; j < N; j++)
        cout << allVisitedPoints[minWayLenIndex][j] <<" ";

}