đệ quy + 900 yếu tố + hàng xóm kiểm tra = nguyên nhân stackoverflow

Question

Tôi có một trò chơi mô phỏng thành phố và cố gắng tìm một cách để kiểm tra dòng chảy của hệ thống điện của chúng tôi. Thông tin cơ bản: Bản đồ cho thành phố dựa trên các ô (30 x 30 gạch = 900 ô). Bây giờ tôi bắt đầu tại một nhà máy điện và thực hiện kiểm tra hàng xóm đệ quy (trên cùng, bên trái, bên phải, phía dưới) để kiểm tra xem có cái gì đó sẽ vận chuyển sức mạnh không. Nếu có cái gì đó, tôi cũng bắt đầu kiểm tra gạch này cho hàng xóm. Để ngăn chặn kiểm tra đôi và/hoặc cuộc gọi đệ quy vô hạn, tôi điền vào một ArrayList với gạch xử lý và kiểm tra xem một ngói mới đã được xử lý và thêm vào ArrayList ...

đệ quy bắt đầu:

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); 
    } 
} 

Nếu tôi có thể tin tưởng đầu ra nhật ký, không có lát nào được xử lý hai lần. Điều đó có nghĩa, rằng tôi không có lỗi trong các cuộc gọi đệ quy. Điều này cũng có nghĩa là, ngăn xếp chỉ đơn giản là quá nhỏ.

Có ai đó có ý tưởng cách tránh giới hạn ngăn xếp không?

[Update và mã của tôi là kết quả của Erics câu trả lời]

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

Nếu tôi hiểu vấn đề của bạn một cách chính xác bạn đang cố gắng để tính đóng cửa bắc cầu của "được cung cấp bởi" mối quan hệ giữa hai viên gạch. Nó chắc chắn có thể tính toán một sự đóng cửa chuyển tiếp không đệ quy.

Đây là thuật toán không đệ quy tính toán sự đóng cửa chuyển tiếp của một quan hệ trong C#. Bạn sẽ có thể thích nghi điều đó với ngôn ngữ bạn chọn.

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

Lưu ý rằng về cơ bản những gì tôi đang làm ở đây là tránh các giới hạn ngăn xếp bởi phân bổ stack riêng của tôi trên đống. Điều đó có thể phát triển lớn như bạn muốn. (Nếu bạn hết bộ nhớ heap thì bạn có vấn đề lớn hơn!)

Cũng lưu ý rằng chọn cấu trúc dữ liệu làm cho "thành viên?" vị ngữ cực rẻ. Một danh sách mảng có kích thước n thường là O (n) để trả lời câu hỏi "là phần tử này có phải là thành viên của bộ sưu tập này không?" có nghĩa là thuật toán của bạn là O (n^2) tổng thể. Bạn có thể sử dụng một bộ sưu tập như một bộ hoặc một bảng băm có thử nghiệm ngăn chặn O (1) không?

Ngoài ra, ở mức "chất lượng mã" thuần túy, phương pháp này có thể sử dụng một số công việc. Thực tế là có rất nhiều mã trùng lặp trong đó có một lá cờ đỏ. Tôi sẽ có khuynh hướng viết phương pháp này giống như phác thảo này:

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; 
} 

Ngắn, đến điểm, không đệ quy, không có mã trùng lặp và O (n).

Answer 2

Bạn chỉ cần chuyển đổi triển khai đệ quy của bạn thành một bản lặp lại (như lý thuyết cho chúng ta biết luôn luôn có thể).

Ví dụ, bạn có thể:

• duy trì một hàng đợi của các tế bào-to-be-kiểm tra
• trong khi hàng đợi này là không có sản phẩm nào, quá trình tố trước
  • để xử lý một tế bào , hãy làm bất cứ điều gì bạn phải làm cho chính ô đó, sau đó cho mỗi trong số bốn nneighbours
  • nếu chúng chưa có trong hàng đợi, hãy thêm chúng vào hàng đợi
• lặp lại cho đến khi hàng đợi rỗng

Answer 3

Một hiệu quả, thuật toán đệ quy nên làm việc với điều kiện bạn xóa các cờ (tôi giả sử bạn chỉ cần thiết lập cờ vào việc một ngói có quyền lực hay không) trước khi thực hiện đệ quy . Một cái gì đó như thế này:

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); 
} 

Điều này sẽ hoạt động tốt cho đến khi bạn sử dụng kích thước lưới thực sự rất lớn.

Answer 4

Bạn có thể làm cho nó lặp đi lặp lại. Có hai danh sách, một danh sách theo dõi vị trí của bạn và danh sách theo dõi vị trí bạn hiện đang kiểm tra.

psuedo Mã với mã của bạn:

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

Điều đầu tiên tôi sẽ cố gắng chỉ là để thay đổi thứ tự tìm kiếm từ Bắc-Nam-Tây-Đông đến Đông Bắc-Tây Nam. Như thế này:

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); 
} 

Điều này có thể làm giảm độ sâu đệ quy, suy giảm trên bản đồ liên quan.