rekurencyjne + 900 elementów + sprawdzenie sąsiada = powoduje stackoverflow

Question

Mam grę symulacyjną miasta i próbuję znaleźć sposób na sprawdzenie przepływu naszego systemu zasilania. Podstawy: Mapa miasta oparta jest na kafelkach (30 na 30 kafelków = 900 kafelków). Teraz zaczynam od elektrowni i wykonuję kontrolę rekursywnego sąsiada (góra, lewo, prawo, dół), aby sprawdzić, czy jest coś, co przeniesie moc. Jeśli coś jest, zaczynam sprawdzać te kafelki również dla sąsiadów. Aby uniknąć podwójnych kontroli i/lub nieskończone wywołań rekurencyjnych, ja wypełnić ArrayList z przetworzonych płytek i sprawdzić, czy nowa dachówka zostało już przetworzone i dodane do ArrayList ...

Rekursywnie początek:

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    Log.w("GT", "update env for id: " + id); 
    int newId = id - GameMap.mMapSize; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
    newId = id + GameMap.mMapSize; 
    if (newId < GameMap.mMapCells.size() && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
    newId = id - 1; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
    newId = id + 1; 
    if (newId < GameMap.mMapCells.size() 
      && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     updatePowerEnvironment(newId, elements); 
    } 
} 

Jeśli mogę zaufać wynikowi dziennika, żaden kafelek nie został przetworzony dwukrotnie. Oznacza to, że nie mam błędów w wywołaniach rekursywnych. Co oznacza także, że stos jest po prostu za mały.

Czy ktoś ma pomysł, jak uniknąć ograniczenia stosu?

[Update i mój kod w wyniku ERIC Odpowiedź]

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    Stack<Integer> toProcess = new Stack<Integer>(); 
    toProcess.push(id); 
    int mapSize = GameMap.mMapCells.size(); 
    while (!toProcess.empty()) { 
     id = toProcess.pop(); 
     Log.e("GT", "id to process: " + id); 
     if (elements.contains(id)) { 
      continue; 
     } 
     int[] neighborIds = computeNeighbors(id); 
     for (int neighbor : neighborIds) { 
      if (neighbor < 0 || neighbor >= mapSize) { 
       continue; 
      } 
      if (!GameMap.mMapCells.get(neighbor).mPowerEnabled) { 
       continue; 
      } 
      toProcess.push(neighbor); 
     } 
     elements.add(id); 
    } 
} 

private int[] computeNeighbors(int id) { 
    return new int[] {id + GameMap.mMapSize, id - GameMap.mMapSize, id + 1, id - 1}; 
} 

Answer 1

Jeśli rozumiem problem prawidłowej starają się obliczyć zamknięcie przechodni z „jest zasilany przez” relacji dwie płytki. Z pewnością możliwe jest nierekurencyjne obliczenie zamknięcia przechodniego.

Oto nierekurencyjny algorytm obliczający przechodnie zamknięcie relacji w języku C#. Powinieneś być w stanie dostosować to do wybranego języka.

http://blogs.msdn.com/b/ericlippert/archive/2010/02/08/making-the-code-read-like-the-spec.aspx

Należy zauważyć, że w zasadzie to, co robię tutaj jest unikanie limit stosu przydzielania mój własny stos na stercie. Ta rzecz może rosnąć tak duża, jak tylko chcesz. (Jeśli zabraknie pamięci sterty, to masz większe problemy!).

Należy również zauważyć, że rozsądnie byłoby wybrać strukturę danych, która powoduje, że "jest członkiem?". predykat wyjątkowo tani. Lista tablic o rozmiarze n jest zwykle O (n), aby odpowiedzieć na pytanie "czy ten element jest członkiem tej kolekcji?" co oznacza, że ​​twój algorytm jest ogólnie O (n^2). Czy możesz użyć kolekcji takiej jak zestaw lub tabela mieszania, która ma testowanie zamknięcia O (1)?

Również na czysto "jakości kodu" ta metoda może wykorzystać trochę pracy. Fakt, że jest , tak bardzo zduplikowany kod jest czerwoną flagą. Byłbym skłonny napisać ten sposób jak ten szkic:

Set<int> PoweredTiles(int powersource) 
{ 
    Set<int> result = an empy set; 
    Stack<int> stack = an empty stack; 
    stack.Push(powersource); 
    while (stack is not empty) 
    { 
     int current = stack.Pop(); 
     if (result.Contains(current)) continue; 
     result.Add(current); 
     int[] neighbours = { compute the neighbours } 
     foreach(int neighbour in neighbours) 
     { 
      if (neighbour is not in range of grid) continue; 
      if (neighbour is not a power carrier) continue; 
      stack.Push(neighbour); 
     } 
    } 
    return result; 
} 

krótkie, do punktu, nie rekurencyjnego, brak kodu powielane i O (n).

Answer 2

Trzeba tylko przekonwertować rekursywną implementację na wersję iteracyjną (jak twierdzi teoria, jest to zawsze możliwe).

Na przykład, można:

• utrzymać kolejkę komórek-być sprawdzane
• natomiast ta kolejka nie jest pusta, proces przedniego elementu
  • przetwarzać komórkę Zrób cokolwiek musisz zrobić z samą komórką, a następnie dla każdego z jej czterech sąsiadów, jeśli nie są jeszcze w kolejce, dodaj je do kolejki
• powtarzać aż do kolejki jest pusty

Answer 3

Sprawny, rekurencyjny algorytm powinien pracują pod warunkiem, że nie usunąć flagi (zakładam, jesteś po prostu ustawienie flagi czy płytka ma władzę, czy nie) przed wykonaniem rekursji . Coś takiego:

void updateCell(position) 
{ 
    for each direction (north, south, east, west) do the following: 
    -- is there a cell there? (test for edges), if not, exit now; 
    -- can it be powered? 
    false: exit now; 
    true: set powered=true, call updateCell(this position); 
} 

void updatePowerGrid(start) 
{ 
    clearPowerFlags(); 
    set powered=true for start; 
    updateCell(start); 
} 

To powinno działać wystarczająco dobrze, dopóki nie użyjesz naprawdę dużych rozmiarów siatki.

Answer 4

Możesz zrobić iteracyjny. Mają dwie listy, z których jedna rejestruje, gdzie byłeś, i jedną, która śledzi, gdzie aktualnie się znajdujesz.

Kod Psuedo z kodem:

While(ToBeChecked is not empty) { 
    //Note In python i'd be using a copy of the list so I could edit it without 
    //concequence during the iteration. ie for a in b[:] 
    for each element in ToBeChecked 
     updatePowerEnvironment(...); 
     //Remove element you are checking   
     removeElementFromToBeChecked(...); 
} 

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    Log.w("GT", "update env for id: " + id); 
    int newId = id - GameMap.mMapSize; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     //call addElementToBeChecked instead and I beleive the above already 
     //makes sure it has not already been checked 
     addElementToBeChecked(newId, elements); 
    } 
    newId = id + GameMap.mMapSize; 
    if (newId < GameMap.mMapCells.size() && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     addElementToBeChecked(newId, elements); 
    } 
    newId = id - 1; 
    if (newId >= 0 && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     addElementToBeChecked(newId, elements); 
    } 
    newId = id + 1; 
    if (newId < GameMap.mMapCells.size() 
      && GameMap.mMapCells.get(newId).mPowerEnabled 
      && !elements.contains(newId)) { 
     elements.add(newId); 
     addElementToBeChecked(newId, elements); 
    } 
} 

addElementToBeChecked(...) { 
    ToBeChecked.add(); 
    //Some other stuff if needed 
} 
removeElemenToBeChecked(...) { 
    ToBeChecked.remove(); 
    //Some other stuff if needed 
} 

Answer 5

Pierwszą rzeczą, chciałbym spróbować to tylko, aby zmienić kolejność przeszukiwania z północno-południowo-zachodniej-wschodu na północny-wschód-południowego-zachodu. W ten sposób:

public void updatePowerEnvironment(int id, ArrayList<Integer> elements) { 
    if (!GameMap.ValidCellId(id)) 
     return; 
    if (!GameMap.mMapCells.get(id).mPowerEnabled) 
     return; 
    if (elements.Contains(id)) 
     return; 
    elements.Add(id); 
    updatePowerEnvironment(id - GameMap.mMapSize, elements); 
    updatePowerEnvironment(id + 1, elements); 
    updatePowerEnvironment(id + GameMap.mMapSize, elements); 
    updatePowerEnvironment(id - 1, elements); 
} 

Może to zmniejszyć głębokość rekursji, zmniejszając liczbę zaangażowanych map.