Odmiana problemu komiwojażera - algorytm z powrotami

Odpowiedz Nowy wątek
2016-01-11 00:05

Rejestracja: 5 lat temu

Ostatnio: 3 lata temu

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.

edytowany 1x, ostatnio: Jasiul, 2016-01-11 00:09

Pozostało 580 znaków

2016-01-11 00:19

Rejestracja: 14 lat temu

Ostatnio: 3 dni temu

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()

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-11 10:12

Rejestracja: 5 lat temu

Ostatnio: 3 lata temu

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ł?

Pozostało 580 znaków

2016-01-11 11:04

Rejestracja: 14 lat temu

Ostatnio: 3 dni temu

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)](http://4programmers.net/Forum/1213515):
> 
```c
            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)


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-11 11:59

Rejestracja: 5 lat temu

Ostatnio: 3 lata temu

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.

edytowany 1x, ostatnio: Jasiul, 2016-01-11 12:00

Pozostało 580 znaków

2016-01-11 12:02

Rejestracja: 14 lat temu

Ostatnio: 3 dni temu

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

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-11 12:50

Rejestracja: 5 lat temu

Ostatnio: 3 lata temu

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.

edytowany 5x, ostatnio: Jasiul, 2016-01-11 13:30
temp2 - masz obliczone ale w dwóch miejscach liczysz to samo, zmień na sensowną nazwę. - _13th_Dragon 2016-01-11 13:07
Może jeszcze doklej dane testowe. - _13th_Dragon 2016-01-11 13:10
odl_od_ost_do_pierw = ... - zgubiłeś hipot - _13th_Dragon 2016-01-11 13:28
yup, przy przeklejaniu, ale dzięki - Jasiul 2016-01-11 13:30

Pozostało 580 znaków

2016-01-11 13:32

Rejestracja: 14 lat temu

Ostatnio: 3 dni temu

  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ęć.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-01-13 19:36

Rejestracja: 5 lat temu

Ostatnio: 3 lata temu

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.

Pozostało 580 znaków

Odpowiedz

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