Odmiana problemu komiwojażera - algorytm z powrotami

0

Cześć,
jestem w trakcie pisania (przyznam bez bicia, że przerobiłem gotowy algorytm z internetu) programu, który:

  1. z pliku wczyta punkty o danych współrzędnych i wagach
  2. za pomocą algorytmu z powrotami wyznaczy ścieżkę krótszą niż ileśtam (podane w pliku) o najwyższej sumie wag
  3. wypisze najwyższą sumę wag oraz indeksy kolejnych miast na ścieżce w sposób: start miasto1 miasto2 ... start
 
#include <iostream>
#include <stack>
#include <fstream>
#include <cmath>

using namespace std;

struct sWierzch{
    int x;
    int y;
    int waga;
    int indeks;
};

int n,m,najw_profit,aktual_profit,it,aktual_dlugosc;  //n - il wierzch, m - max dlugosc, it - zlicza iteracje
bool *czyOdwiedz;                                                // tab odwiedzin
sWierzch *W;                                                       // tab wierzcholkow
stack <sWierzch> najl_droga;
stack <sWierzch> aktual_droga;  


int odleglosc(sWierzch w1, sWierzch w2)
{
    return ( sqrt( (w1.x-w2.x)*(w1.x-w2.x) + (w1.y-w2.y)*(w1.y-w2.y) ) );
}


void TSP(sWierzch v)
{
    int u;
        it++;                                         //zliczamy iteracje - elementy stosu?
        aktual_droga.push(v);                // zapamiętujemy na stosie bieżący wierzchołek

        if(it < n)                          // jeśli brak ścieżki Hamiltona, to jej szukamy
        {

            czyOdwiedz[it] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
            for(u = 0; u < n; u++)            // Przeglądamy sąsiadów wierzchołka v
            if(!czyOdwiedz[u] && ((aktual_dlugosc + odleglosc(v,W[u]) + odleglosc(W[u],W[0])) <= m) )       /* Szukamy nieodwiedzonego jeszcze sąsiada, sprawdzamy, czy droga bedzie miala odpowiednia dlugosc*/
            {
                aktual_profit += W[u].waga;            // Dodajemy wagę u do profitu
                aktual_dlugosc += odleglosc(v,W[u]);  //Dodajemy odleglosc od aktualnego wierzcholka do nastepnego
                TSP(W[u]);                                    // Rekurencja
                aktual_profit -= W[u].waga;            // Usuwamy wagę u z sumy
            }
            czyOdwiedz[it] = false;                    // Zwalniamy bieżący wierzchołek
        }
        else if((aktual_dlugosc + odleglosc(v,W[it]) + odleglosc(W[it],W[0])) <= m)  // Jeśli nie ma nieodwiedzonych sasiadow, a droga spelnia warunek
        {
                           // to sprawdzamy, czy aktualny profit jest najwiekszy
            if(aktual_profit > najw_profit)                    // Jeśli tak,
            {
                najw_profit = aktual_profit;                    
                najl_droga = aktual_droga;
            }

        }

        aktual_droga.pop();
        it--;                        // Usuwamy bieżący wierzchołek ze ścieżki
}


int main()
{
    int i; 

    ifstream in;

    in.open("in.txt");

    in >> n >> m;                  // Czytamy liczbę wierzchołków i ich wagi

    // Inicjalizacja

    czyOdwiedz = new bool [n];     
    W = new sWierzch [n];

    for(i = 0; i < n; i++)
    {
        czyOdwiedz[i] = false;
        W[i] = {0,0,0,0};
    }
    it = 0;

  // Odczytujemy dane wejściowe

    for(i = 0; i < n; i++)
    {
        in >> W[i].x >> W[i].y >> W[i].waga;
        W[i].indeks = i;
    }

  // Rozpoczynamy algorytm

    najw_profit  = 0;
    aktual_profit = 0;
    aktual_dlugosc = 0;

    TSP(W[0]);

    cout <<W[0].indeks<<" ";
    while(!najl_droga.empty())
    {
        cout << najl_droga.top().indeks << " ";
        najl_droga.pop();
    }
    cout << "najw_profit = " << najw_profit << "\n";


  // Sprzatamy

    in.close();

    delete [] czyOdwiedz;
    delete [] W;

    return 0;
}

Niestety, program nie działa, chociaż się kompiluje i zwraca jakieś wartości.
Błąd siedzi gdzieś w funkcji TSP (ponieważ nie nauczyli mnie/nauczyłem się debugować w cpp, sprawdziłem to cout'ami, więc mam nadzieję, że tylko tam), konkretnie zdaje mi się, że skopałem warunek na długość trasy albo odwołania do wierzchołków.
Z góry dziękuję za pomoc :)

PS. Uczę się pisać "czysty kod" - prosiłbym Was o krytykę również pod tym kątem.

1
  1. Zapoznaj się z inkrementacją bo jej nie rozumiesz: http://4programmers.net/Forum/1101404
  2. Zmienne globalne - tylko jeżeli całej twojej rodzinie grożą śmiercią.
  3. Używasz stack<> zaś vector<> nie?
  4. Czemu nie używasz konstruktora ifstream?
  5. Zapoznaj się z funkcją hypot()
0

Ok, dzięki za uwagi, poprawiłem:

#include <iostream>
#include <stack>
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

struct sWierzch{
    int x;
    int y;
    int waga;
    int indeks;
};

int n,m,najw_profit,aktual_profit,it; //n - il wierzch, m - max dlugosc
float aktual_dlugosc;
vector <bool> czyOdwiedz;                         // tab odwiedzin
vector <sWierzch> W;                             // tab wierzcholkow
stack <sWierzch> najl_droga;
stack <sWierzch> aktual_droga;              // Stosy w tablicy

void TSP(sWierzch v)
{
    int u;
    cout<<"dodaje w:"<<it<<"\n";
        ++it;
        aktual_droga.push(v);                // zapamiętujemy na stosie bieżący wierzchołek

        if(it < n)                   // jeśli brak ścieżki Hamiltona, to jej szukamy
        {

            czyOdwiedz[it] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
            for(u = 0; u < n; ++u)           // Przeglądamy sąsiadów wierzchołka v
            if(!czyOdwiedz[u] && ((aktual_dlugosc + hypot(v.x-W[u].x,v.y-W[u].y) + hypot(W[0].x-W[u].x,W[0].y-W[u].y)) <= m) )       // Szukamy nieodwiedzonego jeszcze sąsiada
            {
                aktual_profit += W[u].waga;            // Dodajemy wagę u do sumy
                aktual_dlugosc += hypot(v.x-W[u].x,v.y-W[u].y);
                TSP(W[u]);                             // Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
                aktual_profit -= W[u].waga;            // Usuwamy wagę u z sumy
            }
            czyOdwiedz[it] = false;                    // Zwalniamy bieżący wierzchołek
        }
        else if((aktual_dlugosc + hypot(v.x-W[it].x,v.y-W[it].y) + hypot(W[0].x-W[it].x,W[0].y-W[it].y)) <= m)
        {
            if(aktual_profit > najw_profit)                    // Jeśli tak,
            {
                najw_profit = aktual_profit;                     // To zapamiętujemy tę sumę
                najl_droga = aktual_droga;                       // i droge
            }
            aktual_dlugosc -= hypot(W[0].x-W[it].x,W[0].y-W[it].y);
        }

        aktual_droga.pop();
        --it;                        // Usuwamy bieżący wierzchołek ze ścieżki
}


int main()
{
    int i;
    sWierzch tmp;

    ifstream in("in.txt",ios_base::in);

    in.open("in.txt");
    cout << "otworzylem in\n";

    in >> n >> m;                  // Czytamy liczbę wierzchołków i maksymalna dlugosc

  // Inicjalizacja

    W.reserve(n);
    czyOdwiedz.reserve(n);
    it = 0;

  // Odczytujemy dane wejściowe

    for(i = 0; i < n; ++i)
    {
        in >> tmp.x >> tmp.y >> tmp.waga;
        tmp.indeks = i;
        W.push_back(tmp);
    }

    cout << "Wczytalem wierzcholki\n";

  // Rozpoczynamy algorytm

    najw_profit  = 0;
    aktual_profit = 0;
    aktual_dlugosc = 0;

    TSP(W[0]);

    while(!najl_droga.empty())
    {
        cout << najl_droga.top().indeks << " ";
        najl_droga.pop();
    }
    cout << W[0].indeks << "\n";
    cout << "najw_profit = " << najw_profit << "\n";

    cout << "sprzatam\n";

    in.close();

    return 0;
}
 

Czy z tą inkrementacją chodziło jedynie o optymalizację? Bo, z tego, co wiem, różnica w działaniu jest między m=i++; a m=++i;, a między i++; a ++i; nie ma. Co do zmiennych globalnych - wiem, ale jakoś na razie nie widzę innego sensownego rozwiązania :P
Poza tym, w sumie nic nie zmieniłem, a kod wykłada się już na próbie wywołania TSP, ma ktoś jakiś pomysł?

1
Jasiul napisał(a):

Co do zmiennych globalnych - wiem, ale jakoś na razie nie widzę innego sensownego rozwiązania

struct Bajzel
  {
   int n,m,najw_profit,aktual_profit,it; //n - il wierzch, m - max dlugosc
   float aktual_dlugosc;
   vector <bool> czyOdwiedz;                         // tab odwiedzin
   vector <sWierzch> W;                             // tab wierzcholkow
   stack <sWierzch> najl_droga;
   stack <sWierzch> aktual_droga;              // Stosy w tablicy
  };
 
void TSP(sWierzch v,Bajzel &b)
{ ...
Jasiul napisał(a):
            for(u = 0; u < n; ++u)           // Przeglądamy sąsiadów wierzchołka v
            if(...
  • postaw klamerki u tego for'a bo nie widać na pierwszy rzut oka.

Usuń wielokrotne obliczenia tego samego na rzecz dodatkowej zmiennej lokalnej, np: hypot(v.x-W[u].x,v.y-W[u].y)

0

O, fajny myk, dzięki.
A mógłbyś (lub ktokolwiek mógłby) mi może jeszcze napisać, jak powinienem wywołać funkcję TSP w mainie? Siedzę przy dokumentacji wektora i nic mi nie przychodzi do głowy.

1
Bajzel b;
in >> b.n >> b.m; 
b.W.reserve(n);
...
n.najw_profit=0;
...
TSP(b.W[0],b);
0

Dziwne, TSP(W[0]) nie działało, a po dodaniu struktury sDeklar (tudzież Bajzel) TSP(d.W[0],d) juz tak 0.0
Tzn. program się kompiluje, ale it rośnie do kilku tysięcy, czyli TSP wywołuje się tyle razy bez powrotu, a potem się wykłada.

edit: jednak wrzucę kod:

#include <iostream>
#include <stack>
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

struct sWierzch{
    int x;
    int y;
    int waga;
    int indeks;
};

struct sDeklar{
    int n,m,najw_profit,aktual_profit,it; //n - il wierzch, m - max dlugosc
    float aktual_dlugosc;
    vector <bool> czyOdwiedz;                         // tab odwiedzin
    vector <sWierzch> W;                             // tab wierzcholkow
    stack <sWierzch> najl_droga;
    stack <sWierzch> aktual_droga;              // Stosy w tablicy
};

void TSP(sWierzch v, sDeklar &d)
{
    int u;
    cout<<"dodaje w:"<<d.it<<"\n";
        ++d.it;                                 //ilosc wierzcholkow/iteracji
        d.aktual_droga.push(v);                // zapamiętujemy na stosie bieżący wierzchołek

        float odl_od_ost_do_pierw = 0;   
        odl_od_ost_do_pierw = hypot( d.W[0].x-d.W[d.it].x, d.W[0].y-d.W[d.it].y ); //odl od ostatniego wierzcholka na stosie do pierwszego

        if(d.it < d.n)                   // jeśli brak ścieżki Hamiltona, to jej szukamy
        {
            d.czyOdwiedz[d.it] = true;            // Oznaczamy bieżący wierzchołek jako odwiedzony
            for(u = 0; u < d.n; ++u)            // Przeglądamy sąsiadów wierzchołka v
            {
                float do_nast = 0;
                do_nast = hypot( v.x-d.W[u].x, v.y-d.W[u].y );

                if(!d.czyOdwiedz[u] && ((d.aktual_dlugosc + do_nast + hypot( d.W[0].x-d.W[u].x, d.W[0].y-d.W[u].y )) <= d.m) )       // Szukamy nieodwiedzonego jeszcze sąsiada i spr, czy dlugosc trasy do aktualnego wierzcholka + dlugosc trasy do nastepnego wierzcholka + dlugosc trasy od nastepnego do poczatkowego miesci sie w zakresie
                {
                    d.aktual_profit += d.W[u].waga;            // Dodajemy wagę nastepnego wierzcholka u do sumy
                    d.aktual_dlugosc += do_nast;
                    TSP(d.W[u],d);                             // Rekurencyjnie wywołujemy szukanie cyklu Hamiltona
                    d.aktual_profit -= d.W[u].waga;            // Usuwamy wagę u z sumy
                }
            }
            d.czyOdwiedz[d.it] = false;                    // Zwalniamy bieżący wierzchołek
        }
        else if((d.aktual_dlugosc + hypot( v.x-d.W[d.it].x, v.y-d.W[d.it].y ) + odl_od_ost_do_pierw) <= d.m)
        {
            if(d.aktual_profit > d.najw_profit)                    // Jeśli tak,
            {
                d.najw_profit = d.aktual_profit;                     // To zapamiętujemy tę sumę
                d.najl_droga = d.aktual_droga;                       // i droge
            }
            d.aktual_dlugosc -= odl_od_ost_do_pierw;
        }

        d.aktual_droga.pop();
        --d.it;                                             // Usuwamy bieżący wierzchołek ze ścieżki
}


int main()
{
    int i;
    sWierzch tmp;
    sDeklar d;

    ifstream in("in.txt",ios_base::in);

    in.open("in.txt");
    cout << "otworzylem in\n";

    in >> d.n >> d.m;                  // Czytamy liczbę wierzchołków i maksymalna dlugosc

  // Inicjalizacja

    d.W.reserve(d.n);
    d.czyOdwiedz.reserve(d.n);
    d.it = 0;

  // Odczytujemy dane wejściowe

    for(i = 0; i < d.n; ++i)
    {
        in >> tmp.x >> tmp.y >> tmp.waga;
        tmp.indeks = i;
        d.W.push_back(tmp);
    }

    cout << "Wczytalem wierzcholki\n";

  // Rozpoczynamy algorytm

    d.najw_profit  = 0;
    d.aktual_profit = 0;
    d.aktual_dlugosc = 0;
    cout << "costam\n";
    TSP(d.W[0],d);

    while(!d.najl_droga.empty())
    {
        cout << d.najl_droga.top().indeks << " ";
        d.najl_droga.pop();
    }
    cout << d.W[0].indeks << "\n";
    cout << "najw_profit = " << d.najw_profit << "\n";

    cout << "sprzatam\n";

    in.close();

    return 0;
} 

`in.txt:

33 2439
1910 2430 0
1820 2400 0
1260 2490 20
1440 2800 20
1690 2810 20
2070 2820 20
1250 2660 20
2180 2730 20
1250 2260 20
2250 1700 30
1990 1500 30
1490 1510 30
1150 1860 30
1240 2980 30
1780 2810 30
910 2980 40
1000 3260 40
1390 3310 40
1995 1030 40
1520 800 40
1470 3120 50
740 3650 50
2100 2550 50
1800 2530 10
1950 2470 10
2140 2180 10
1600 2140 10
1865 2620 10
1790 2890 10
1430 1990 20
1700 1900 20
1080 2100 20
1570 2370 10`

Pierwsza linijka to n, m, niżej współrzędne to wierzchołek startowy i jego waga, reszta to reszta wierzchołków.

1
  1. Po wywołaniu TSP(d.W[u],d); nie odtwarzasz d.aktual_dlugosc coś tam odtwarzasz przy ostatnim kroku ale tego jest za mało.
  2. To:
else if((d.aktual_dlugosc + hypot( v.x-d.W[d.it].x, v.y-d.W[d.it].y ) + odl_od_ost_do_pierw) <= d.m)

wykona się kiedy d.it>=d.n zaś ostatnim indeksem d.W[] może być d.n-1 czyli wyłazisz poza przydzieloną pamięć.

0

W tym kodzie, przynajmniej u mnie, źle działało wczytywanie - zamiast ifstream in("in.txt",ios_base::in); dałem ifstream in;, ponieważ wczytywało mi n i m z kosmosu oraz dalej nie działa to, co wyżej.
Po kilku zmarnowanych godzinach, odpuściłem sobie tę implementację, przepisałem program od nowa, zapisałem odległości na macierzy, a resztę na tablicach dynamicznych - działa dobrze i szybko.
Mimo porażki, jeszcze raz dziękuję za podpowiedzi.

1 użytkowników online, w tym zalogowanych: 0, gości: 1