Witam
Mam taki problem! Mam tablice o nieograniczonych kolumnach i 4 wierszach. W tablicy mam zaznaczone 2 punkty! Punkt Startowy i Cel. Moim zadaniem jest odnalezienie wszystkich możliwych ścieżek między tymi dwoma punktami. Niestety dla 1000 kolumn i więcej dostaje komunikat o błędzie stack overflow, nie znajduje mi również wszystkich możliwych ścieżek dla mniejszej ilości kolumn. Może mi ktoś pomóc lub doradzić jak ten problem najlepiej rozwiązać ?
Pozdrawiam
0
0
Obawiam się, że musisz znacząco doprecyzować problem.
0
Postaram się sprecyzować. Mam tablice dwuwymiarową o 4 wierszach i dowolnej ilości kolumn. W tej tablicy wstawione sa dwa punkty: START i CEL. Problem polega na znalezienie wszystkich możliwych dróg przez tablicę z punktu START do punktu CEL. Zamieszczam szkic zagadnienia. Tablica o 4 wierszach i 8 kolumnach. Kolor czerwony to START kolor zielony to CEL. Na kolorowo zaznaczone są przykładowe ścieżki łączące te dwa punkty.
0
A kiedy możemy powiedzieć że dwie ścieżki są równe. Bo z tego rysunku wynika, że wystarczy aby dwie ścieżki różniły się jednym polem i już są inne. Takich ścieżek będzie bardzo dużo. Może Ty poszukujesz najkrótsze ścieżki ?
0
Jeśli chodzi o przepełnienie stosu to prawdopodobnie wszystkie możliwe odnalezione ścieżki trzymasz w pamięci i Twój komp w pewnym momencie grzecznie odmawia współpracy, gdyż weź pod uwagę że liczba ścieżek będzie ogromna przy 1000 kolumnach. Możesz to ominąć zapisując w pamięci jedynie część ścieżek, które później wrzucasz na czas wykonywania programu np do pliku. Od razu mówię że bardzo spowolni to wykonywanie algorytmu, gdyż później będziesz musiał weryfikować nowe ścieżki odwołując się do pliku. Oczywiście to tylko sugestia i na 100% są lepsze rozwiązania, które jednak teraz nie przychodzą mi do głowy :)
A à propos nie znajdywania wszystkich ścieżek to już tylko kwestia algorytmu którego używasz. Podrzuć jego kod, albo schemat UML jeśli masz to zobaczymy :)
[browar]
0
Dalej problem jest mocno niedoprecyzowany... Jakie są ograniczenia w "wędrowaniu" po tej mapie? Czy są komórki, przez które przechodzić nie można? Czy można dwa razy wejść na to samo pole? Itp itd.
Błąd o przepełnieniu stosu wynika zapewne ze zbyt głębokiej rekurencji. Poza tym tak ogólnie dany problem generuje nieograniczoną (sic!) liczbę rozwiązań.
0
A jeśli szukasz najkrótszej ścieżki i po prostu przyjąłeś założenie że znajdziesz wszystkie i wybierzesz najkrótszą to raczej "strzeliłeś sobie w kolano" :) Do tego typu zadań służą np. algorytmy genetyczne lub inny algorytm heurystyczny (np. roju cząstek), które pozwalają na znalezienie najkrótszej ścieżki bez analizy wszystkich możliwych wariantów. Baaaaardzo ciekawy temat :)
[browar]
0
Dobra sprecyzuje problem w taki sposób. Nie chodzi mi o znalezienie najkrótszej ścieżki, ale ścieżki której koszt ruchu jest najmniejszy. Na punkcie startowym ustawiamy sobie kostkę do gry opisaną, tzn. każdemu oczku od 1 do 6 przypisujemy jakąś wartość nie większa niż 50, która oznacza koszt ruchu. Celem jest dojście do celu obracając kostkę w taki sposób aby koszt ruchów był jak najmniejszy. Napisałem algorytm który sypie mi stack overflow czyli jak przypuszczam za dużo wywołań rekurencyjnych. Dla małych rozmiarów tablicy algorytm znajduje mi ścieżkę ale niestety nie jest to ścieżka o najmniejszym koszcie ruchu. Myślę już nad tym problemem 2 tygodnie i nie mogę go rozgryźć. Aktualnie mój kod wygląda tak gdzie :
xS yS - współrzedne startu
x, y - aktualne wspolrzedne
dl - dlugosc sciezki
wynik[,] - tablica gdzie szukana jest sciezka
public void szukaj(int x, int y, int dl)
{
if ((xS == x) && (yS == y))
{
wynik[x, y] = 999;
return;
}
if (zpocz == false)
{
if (x < 1 || y < 1 || y > 18 || x > 4) return;
wynik[x, y] = dl;
if (wynik[x, y - 1] > dl + 1) szukaj(x, y - 1, dl + 1);
if (wynik[x - 1, y] > dl+1) szukaj(x - 1, y, dl + 1);
if (wynik[x + 1, y] > dl+1) szukaj(x + 1, y, dl + 1);
if (wynik[x, y + 1] > dl+1) szukaj(x, y + 1, dl + 1);
}
else
{
return ;
}
return ;
}
szukaj(xT, yT, 0);
xT yT - wspolrzedne celu
0
policz sobie, jak głęboko musi wykonać się szukaj(), żeby poradzić sobie z tysiącem kolumn.
kończy ci się miejsce na stosie. albo je zwiększ, albo pomyśl nad bardziej oszczędnym pamięciowo algorytmie.
0
lukiluk napisał(a)
Dobra sprecyzuje problem w taki sposób. Nie chodzi mi o znalezienie najkrótszej ścieżki, ale ścieżki której koszt ruchu jest najmniejszy. Na punkcie startowym ustawiamy sobie kostkę do gry opisaną, tzn. każdemu oczku od 1 do 6 przypisujemy jakąś wartość nie większa niż 50, która oznacza koszt ruchu. Celem jest dojście do celu obracając kostkę w taki sposób aby koszt ruchów był jak najmniejszy.
Przecież to kompletnie zmienia postać rzeczy ;) Czyli wszystko zależy od kostki, a nie od planszy. Wydaje mi się, że jeśli znajdziesz najkrótszą ścieżkę i przed startem tak obrócisz kostkę, aby obracała się wykorzystując ścianki o najmniejszych wagach - to uzyskasz potrzebny efekt.
0
Problem jest nadal mocno enigmatyczny, ale może takie podejście:
- szukamy na kostce dwóch sąsiadujących ścianek o najmniejszej sumie oczek (ściana 1 i 2)
- ustalamy najkrótszą (dowolną z najkrótszych) "ścieżkę" po tablicy od pkt A do pkt B
- podążamy ścieżką poprzez przewracanie kostki ze ścianki 1 na ściankę 2 i z powrotem (można tego dokonać wspomagając się obracaniem kostki w osi prostopadłej do płaszczyzny planszy)
No ale kto wie o co tu tak naprawdę chodzi?
0
Oczywiście jeśli można tak obracać sobie kostką ? Autor nic nie powiedział o tym ;) Ale wydaje się to słusznym podejściem. Jeśli kostki nie można obracać, to należy znaleźć takie 4 ścianki, gdzie suma wag jest najmniejsza ;)
0
mykhaylo napisał(a)
Jeśli kostki nie można obracać, to należy znaleźć takie 4 ścianki, gdzie suma wag jest najmniejsza ;)
To też chyba nie będzie takie proste - co jeśli trzeba będzie przejść 3 "kroki" w jednym kierunku? I tak będzie to kosztować co najmniej 8 pkt.
0
Poszukaj sobie algorytmu "A-star". On rozwiaze twoj problem. (tak mi sie wydaje :-))
0
A więc tak: kostka musi miec zawsze tą samą pozycję początkową tzn oczko 1 zwrócone ku górze a oczko 2 zwrócone do gracza! Z kostką nie mam problemu! Kostka sobie chodzi po ścieżkach i zlicza koszt ruchu! problemem jest znajdywanie samych ścieżek. A-star sie chyba nie nadaje do mojego problemu! wydaje mi się że bardziej djikstra! Jednak nie wiem jak przerobić algorytm djikstry do moich warunków! ktoś może się orientuje?
0
Mam pewien pomysł:
Zauważ, że gdy ustawisz kostkę w pozycji wyjściowej (1 góra, 2 do gracza) to ruch w prawo będzie kosztować 4, w lewo 3, do siebie 2 a od siebie 5. Więc możesz pozwolić zadecydować algorytmowi w którym kierunku ma wykonać ruch (na zasadzie porównań wagi każdego ruchu) byle w kierunku szukanego punktu lub w górę albo w dół. Możesz też założyć żeby zrobił 2 przejścia: po najkrótszej geometrycznej ścieżce oraz po wyliczanej dynamicznie przy każdym kroku.
Zakodowanie zmiennych wag nie powinno być problemem.
[browar]