GreedySolve.cpp

#include "GreedySolve.h"
#include "Graph.h"
#include <iostream>
#include <algorithm>
#include <chrono>
#include <map>
#include <vector>
#include <random>
#include <cmath>

using namespace std;


// implementacja algorytmu nearest neihboor
Solution* GreedySolve::solve(Graph* graph, bool is_silent) {

    int no_vertices = graph->no_vertices;
    int best_cost = INT_MAX;
    vector<int> best_path;

    // Przeanalizuj wszystkie mo¿liwe wierzcho³ki startowe
    for (int start_vertex = 0; start_vertex < no_vertices; start_vertex++) {

        vector<bool> visited(no_vertices, false);
        vector<int> path;
        int total_cost = 0;

        int current_vertex = start_vertex;
        visited[current_vertex] = true;
        path.push_back(current_vertex);

        for (int i = 1; i < no_vertices; i++) {
            int nearest_vertex = -1;
            int min_distance = INT_MAX;

            // Szukanie najbli¿szego nieodwiedzonego wierzcho³ka
            for (int next_vertex = 0; next_vertex < no_vertices; next_vertex++) {
                if (!visited[next_vertex]) {
                    int distance = graph->edge_weight(current_vertex, next_vertex);
                    if (distance < min_distance) {
                        min_distance = distance;
                        nearest_vertex = next_vertex;
                    }
                }
            }

            // Aktualizuj trasê i koszt
            visited[nearest_vertex] = true;
            path.push_back(nearest_vertex);
            total_cost += min_distance;
            current_vertex = nearest_vertex;
        }

        // Powrót do wierzcho³ka startowego
        total_cost += graph->edge_weight(current_vertex, start_vertex);

        // SprawdŸ, czy to jest najlepsze rozwi¹zanie
        if (total_cost < best_cost) {
            best_cost = total_cost;
            best_path = path;
        }
    }

    if (!is_silent) {
        cout << endl << "best greedy cost: " << best_cost << endl;
    }

    Solution* solution = new Solution();
    solution->cost = best_cost;
    solution->path = best_path;

    return solution;
}