NearestNeighborSearch.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>;

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;
    cout << endl;
    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);
}
vector<int> Visited;
double TravelingSalesmanNeighbour(Graph &graph, Visit &visit) {
    int visitedCounter = 1;
    int currentIndex = 0, nearestIndex = 0;  double wayLength=0;
    visit[0] = true; Visited.push_back(0);
    while (visitedCounter != N) {
        nearestIndex = NearestWayFinder(graph, nearestIndex, wayLength, visit);
        visitedCounter++;
        visit[nearestIndex] = true; Visited.push_back(nearestIndex);
    }
    wayLength += graph[0][nearestIndex];
    return wayLength;
}

int main() {
    srand(time(0));
    Graph graph = GraphGenerator();
    Visit visit = VisitGenerator();
    GraphPrinter(graph);
    VisitPrinter(visit);
    cout << TravelingSalesmanNeighbour(graph, visit) << endl;
    VisitPrinter(visit);
    for (int i = 0; i < Visited.size(); i++)
        cout << Visited[i] << " ";

}