TSP - Pomoc w przerobieniu programu

Question

Witam !
Mam następujący problem, nie mam pomysłu jak przerobić rozwiązanie Traveling Salesman Problem-u tak aby sprawdzał mi możliwe drogi z każdego dostępnego miasta :( Na razie zrobiłem tak że sprawdza mi tylko z miasta o pozycji 0 0 w macierzy i wyświetla przebytą drogę i koszt.
Liczę na jakąś podpowiedź, bo siedzę już 2 dzień nad tym i nic mi nie przychodzi do głowy.

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cstdlib>
#include <string>
#include <bits/stdc++.h>
#include <math.h>

using namespace std;

int real_cost = 0;
int cost_before_swapping = 0;

struct points
{
    int ordinal_number;
    int x_cordinate;
    int y_cordinate;
};

int calculate_cost(int point1, int x_point1, int y_point1, int point2, int x_point2, int y_point2) // liczymy koszt(dystans) przej�cia z jednego wierzcho�ka do drugiego, koszt to odleglosc miedzy nimi
{
    int distance;

    distance = (pow((x_point2 - x_point1), 2) + pow((y_point2 - y_point1), 2));
    distance = sqrt(distance);
    distance = abs(distance);

    //cout << "Distance between " << point1 << " and " << point2 << " = " << distance << endl;
    return distance;
}

int main()
{
    vector<points> point_s; // tworzenie vectora struktur

    // operacje na pliku z danymi
    fstream file;
    file.open("test_point.txt", ios::in);

    if (file.good())
    {
        // zmienne pomocnicze do wyciagania danych z poszczegolnych linii o punktach
        int order = 0;
        int xcoordinate = 0;
        int ycoordinate = 0;
        while (!file.eof())
        {
            file >> order;
            file >> xcoordinate;
            file >> ycoordinate;
            point_s.push_back({order, xcoordinate, ycoordinate}); // wpisywanie punktow do wektora
        }
        point_s.pop_back(); // UWAGA OSTATNI PUNKT JEST ZDUBLOWANY I MUSIMY GO USUNAC !!!
    }
    else
    {
        cout << "File error!" << endl;
    }
    file.close();

    /* Algorytm naiwny "Znajdowanie Najblizszego Sasiada"
    Tylko ten algorytm strtuje od iasta 0/0 i tylko dla tego wyznacza trase 
    */

    // 1. Tworzenie macierzy kwadratowej miast i wypelnienie jej odleglosciami

    int grid[point_s.size()][point_s.size()]; //macierz miast wraz z odleglosciami miedzy punktami
    int visited_points[point_s.size()];
    for (int i = 0; i < point_s.size(); i++)
        visited_points[i] = 0; // 0 - nieodwiedzone, 1 - odwiedzone

    for (int i = 0; i < point_s.size(); i++) // obliczanie drogi(kosztu) z punktu do punktu
    {
        for (int y = 0; y < point_s.size(); y++)
        {
            grid[i][y] = calculate_cost(point_s[i].ordinal_number, point_s[i].x_cordinate, point_s[i].y_cordinate, point_s[y].ordinal_number, point_s[y].x_cordinate, point_s[y].y_cordinate);
        }
    }

    
    int number_of_points = point_s.size();
    visited_points[0] = 1;
    int min_cost = 2000000;
    int current=0; // ten ktory ogladamy teraz (dokladniej ten wiersz)
    int next = 0; // nastepny punkt (majmniejsza trasa do tego punktu)
    while (number_of_points--)
    {
        for(int i=0; i<point_s.size(); i++)
        {
            if((min_cost > grid[current][i]) && (visited_points[i] == 0))
            {
                min_cost = grid[current][i];
                next = i;
            }

        }
        visited_points[next]=1;
        cout<<current<<" --> "; // wyswietlanie trasy
        current = next;
        real_cost += min_cost;        
        min_cost = 20000000;
        if(number_of_points == 0)
        {
        real_cost += grid[current][0];
        }
    }
    cout<<"0 ";
    cout<<"Cost: "<<real_cost-20000000<<endl;


    return 0;
}

Zawartość pliku z punktami:
 

1 0 15
2 0 33
3 0 51
4 0 60
5 2 21
6 5 40
7 0 11 
8 10 10 
9 9 9 
10 14 56

 

Comments

Nawiasem:

point_s.pop_back(); // UWAGA OSTATNI PUNKT JEST ZDUBLOWANY I MUSIMY GO USUNAC !!!

Wystarczy, że zrobisz poprawnie pętlę czytającą:

while (file >> order >> xcoordinate >> ycoordinate) {
        point_s.push_back({order, xcoordinate, ycoordinate}); 
}

i nic Ci się nie będzie dublować na końcu ;)

---

o dzięki :D