[C#] Nieznany mi wyjątek w algorytmie znajdowania drogi


(Kamiljano) #1

Witam, jestem dość nowy w C# i wciąż miewam dziwne problemy z tym językiem. Ostatnio próbowałem napisać algorytm znajdujący trasę z punktu A do B.

Oto jak wygląda sam algorytm:

private route Way(place b, route r,int i)

        {

            if (r.LastPlace==b)

                return r;

            if (r.LastPlace.Container.Count > i)

            {

                r.GoTo(r.LastPlace.Container[i]);

                return Way(b, r, 0);

            }

            else

            {

                r.GoBack();

                MessageBox.Show("fsad");

                return Way(b, r, ++i);

            }

        }

a tak wygląda moja struktura route:

public struct route

    {

//-----------------------------------------------------------------------------------------------variables

        uint distance;

        LinkedList places;

        place start;

        //-----------------------------------------------------------------------------------------------properties

        public int NumeberOfPlaces

        {

            get { return places.Count+1; } //+1 - starting place

        }

        public int NumberOfRoads

        {

            get { return places.Count; }

        }

        public uint Distance

        {

            get { return distance; }

        }

        public place LastPlace

        {

            get 

            {

                if (distance == 0)

                    return start;

                else

                    return places.Last.Value.Destination;

            }

        }

        public place StartingPlace

        {

            get { return start; }

        }

        //-----------------------------------------------------------------------------------------------methods

        public route(place start)

        {

            this.start = start;

            distance = 0;

            places = new LinkedList();

        }

        public void GoTo(road p)

        {

            distance += p.Distance;

            places.AddLast(p);

        }

        public void GoBack()

        {

            if (distance > 0)

            {

                distance -= places.Last.Value.Distance;

                places.RemoveLast();

            }

        }

    }

Generalnie algorytm wydaje się być względnie w porządku, bo dla krótkich tras działa bez zarzutu, ale gdy wybiorę odrobinę dłuższą (np. przez 4 miejsca), podświetla mi się

return places.Last.Value.Destination;

we właściwości LastPlace i mówi, że mam wyjątek: Cannot evaluate expression because the current thread is in a stack overflow state.} System.Exception {System.StackOverflowException}

czy coś z tym można zrobić?


(Ryan) #2

Tak - użyć debuggera i sprawdzić co się dzieje. ;] Prawdopodobnie dzieje się dokładnie to, co mówi wyjątek - następuje przepełnienie stosu. Struktury w C# - w przeciwieństwie do klas - są alokowane na stosie. A Ty wołasz rekurencyjnie Way, które struktur route generuje sporo. Pewnie place i road to też struktury, prawda? Możesz powiedzieć dlaczego struktury a nie klasy? Tak na marginesie już - okropnie zaprojektowany kod. Dlaczego umieszczasz start poza LL places?


(Fiołek) #3

Musisz zmniejszyć ilość rekurencyjnych wywołań metod(Way?), gdyż nie mieszczą się już one na stosie. Gdy debugger Ci przerwie działanie rzuć okiem na CallStack - powinieneś mieć masę wywołań jednej metody.

Do grupowania kodu w plikach stosuje się #region, nie komentarze :wink:


([alex]) #4

Do znajdywania drogi jest znacznie szybszy i powszechnie znany algorytm Dijkstry.

Szukanie drogi przez przeglądanie wszystkich możliwych wariantów jest już nie wykonalne (w ciągu życia jednego człowieka, na jednym komputerze) dla zaledwie 15 miast.


(Kamiljano) #5

no ja wiem o algorytmie Dijkstry, ale miałem problemy z ogarnięciem jego działania, więc chciałem rekurencyjnie sprawdzić wszystkie możliwe kombinacje, biorąc pod uwagę, że mapa, którą dostałem jest dość mocno uproszczona i zakładam, że tych kombinacji nie ma tak niesamowicie wiele


([alex]) #6

jeżeli masz 4 miasta to ilość dróg od jednego do drugiego jest nieskończona.

A-[b-C-]-D

odcinek B-C może powtarzać się niesknoconą ilość razy, właśnie dla tego twój algorytm dal 4ch miast lub więcej w końcu przepełni każdy stos.