Algorytm mrówkowy - Stack overflow

Algorytm mrówkowy - Stack overflow
NI
  • Rejestracja:około 13 lat
  • Ostatnio:ponad 3 lata
  • Postów:30
0

Witam. Napisałem algorytm mrówkowy z problemem komiwojażera. Ściągam plik ze współrzędnymi miast o wielkości 101 punktów - wszystko pięknie działa, ale w przypadku większych plików (280 miast) wyskakuje błąd "Stack Overflow". W czym rzecz?

Plik ze współrzędnymi o nazwie a280.tsp.gz

edytowany 1x, ostatnio: niesuszek
Adam Boduch
prosze o poprawne tytulowanie watkow
_13th_Dragon
  • Rejestracja:prawie 20 lat
  • Ostatnio:17 dni
1

Policz ile to w bajtach:

Kopiuj
    int tab[MAX_MIASTA], sciezka[MAX_MIASTA];
    double odleglosc[MAX_MIASTA][MAX_MIASTA];
    double feromon[MAX_MIASTA][MAX_MIASTA];

i to na stosie.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
n0name_l
  • Rejestracja:ponad 12 lat
  • Ostatnio:prawie 5 lat
  • Postów:2412
1

A thread's assigned stack size can be as small as a few dozen kilobytes. Allocating more memory on the stack than is available can result in a crash due to stack overflow.

http://en.wikipedia.org/wiki/Stack-based_memory_allocation

In software, a stack overflow occurs when the stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program.

http://en.wikipedia.org/wiki/Stack_overflow

KR
na pewno nie kilka kilobajtow, jak juz to MB. chyba, że na mikroprocku odpalasz
NI
  • Rejestracja:około 13 lat
  • Ostatnio:ponad 3 lata
  • Postów:30
0

Tzn? Nie za bardzo rozumiem co masz na myśli _13th_Dragon. Mam stworzyć stos i umieszczać na nim te elementy? Nie da się tego jakoś prościej obejść?

_13th_Dragon
@n0name_l wyjaśnił ci to dokładniej.
BB
  • Rejestracja:ponad 11 lat
  • Ostatnio:ponad 10 lat
  • Lokalizacja:100lica
  • Postów:79
0

Utwórz te tablice dynamicznie (np. użyj vectora)


Z zawodu księgowy. Programować dopiero się uczę, więc proszę o wyrozumiałość ;). W kręgu zainteresowań: sztuczna inteligencja (SSN, AG, LR etc.).
NI
  • Rejestracja:około 13 lat
  • Ostatnio:ponad 3 lata
  • Postów:30
0

Korzystałem z new/delete, ale też marny skutek. Vectorów nigdy nie używałem. Dużo zmian w kodzie musiałbym wprowadzić?

n0name_l
Co to znaczy marny skutek?
_13th_Dragon
Bo go uczyli, uczyli, uczyli a skutek marny. :D
NI
To znaczy, że bez jakichkolwiek zmian.
n0name_l
Wniosek jest jeden, nie umiesz korzystac z new/delete. Bo na stercie sila rzeczy ciezko jest uzyskac blad "stack overflow".
MarekR22
Moderator C/C++
  • Rejestracja:ponad 17 lat
  • Ostatnio:14 minut
0
Kopiuj
class algMrowka {
public:
    int obecneMiasto, nastepneMiasto, sciezkaIndex, najDrogaIndex;
    vector<double> tab, sciezka;
    double dlugoscDrogi, najDroga;
    vector<vector<double> > odleglosc; //[MAX_MIASTA][MAX_MIASTA];
    vector<vector<double> > feromon; // [MAX_MIASTA][MAX_MIASTA];
 
public:
    void inicjalizacja() {
        int skad, dokad;
        ifstream plik;
        plik.open(NAZWAPLIKU);
 
        odleglosc = vector<vector<double> >(MAX_MIASTA, vector<double>(MAX_MIASTA));
        feromon = vector<vector<double> >(MAX_MIASTA, vector<double>(MAX_MIASTA, INIT_FEROMON));
        
        //tworzenie miasta
        for(skad=0; skad<MAX_MIASTA; skad++) {
            plik >> miasta[skad].x;
            plik >> miasta[skad].y;
        }
       ...

Ogólnie nie jest źle, największy problem to to, że za dużo próbujesz umieścić w jednej metodzie i nadmiernie stosujesz zmienne globalne.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22
n0name_l
Ale jaki jest sens zamieniac tablice o stalym na rozmiarze na vectory? To chyba nie tedy droga.
MarekR22
zgadzam się, ale to jest droga na skróty.
n0name_l
Najszybciej to cale obiekty powyrzucac ze stosu, ale tak czy siak z tego co widze to nie powinno sie kompilowac.
NI
  • Rejestracja:około 13 lat
  • Ostatnio:ponad 3 lata
  • Postów:30
0

1>c:\users\niesuch\documents\visual studio 2010\projects\mrowka\mrowka\mrowkojad.cpp(162): warning C4244: 'argument' : conversion from 'double' to 'unsigned int', possible loss of data
1>c:\users\niesuch\documents\visual studio 2010\projects\mrowka\mrowka\mrowkojad.cpp(162): warning C4244: 'argument' : conversion from 'double' to 'unsigned int', possible loss of data
1>c:\users\niesuch\documents\visual studio 2010\projects\mrowka\mrowka\mrowkojad.cpp(218): warning C4244: '=' : conversion from 'double' to 'int', possible loss of data
1>c:\users\niesuch\documents\visual studio 2010\projects\mrowka\mrowka\mrowkojad.cpp(219): warning C4244: '=' : conversion from 'double' to 'int', possible loss of data
1>c:\users\niesuch\documents\visual studio 2010\projects\mrowka\mrowka\mrowkojad.cpp(222): warning C4244: '=' : conversion from 'double' to 'int', possible loss of data
1>c:\users\niesuch\documents\visual studio 2010\projects\mrowka\mrowka\mrowkojad.cpp(223): warning C4244: '=' : conversion from 'double' to 'int', possible loss of data
========== Build: 1 succeeded, 0 failed, 0 up-to-date, 0 skipped ==========

Kopiuj
for(int mrowka=0; mrowka<MAX_MROWEK; mrowka++) {
            for(int i=0; i<MAX_MIASTA; i++) {        
                if(i<MAX_MIASTA-1) {
                    skad=mrowki[mrowka].sciezka[i];
                    dokad=mrowki[mrowka].sciezka[i+1];
                }
                else {
                    skad=mrowki[mrowka].sciezka[i];
                    dokad=mrowki[mrowka].sciezka[0];
                }

                feromon[skad][dokad]+=(100/mrowki[mrowka].dlugoscDrogi);
                feromon[dokad][skad]=feromon[skad][dokad];
            }
        } 
MarekR22
popraw tą linijkę: vector&lt;int&gt; tab, sciezka;, błąd copy paste :)
NI
  • Rejestracja:około 13 lat
  • Ostatnio:ponad 3 lata
  • Postów:30
0

user image

Kopiuj
         //inicjalizacja mrowek
        dokad=0;
        for(int mrowka=0; mrowka<MAX_MROWEK; mrowka++) {
            if(dokad==MAX_MIASTA)
                dokad=0;

            mrowki[mrowka].obecneMiasto=dokad++;

            for(skad=0; skad<MAX_MIASTA; skad++) {
                mrowki[mrowka].tab[skad]=0;
                mrowki[mrowka].sciezka[skad]=-1;
            }

            mrowki[mrowka].sciezkaIndex=1;
            mrowki[mrowka].sciezka[0]=mrowki[mrowka].obecneMiasto;
            mrowki[mrowka].nastepneMiasto=-1;
            mrowki[mrowka].dlugoscDrogi=0;
            mrowki[mrowka].tab[mrowki[mrowka].obecneMiasto]=1;
        }
MarekR22
znaczy, że masz błąd w kodzie. Normalne tablice nie sprawdzają zakresu indeksów, operator[] dla wektora kompilowany w debug sprawdza.

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.