我有一个城市模拟游戏，并试图找到一种方法来检查我们电力系统的流量。 基础知识: 城市 map 基于图 block (30 x 30 个图 block = 900 个图 block )。 现在我从一个发电厂开始，做一个递归的邻居检查(上、左、右、下)来检查是否有东西可以传输电力。如果有什么，我也开始检查邻居的瓷砖。 为了防止双重检查和/或无限递归调用，我用处理过的图 block 填充 ArrayList 并检查是否已处理新图 block 并将其添加到 ArrayList...

递归开始:

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

如果我可以信任日志输出，则不会尝试处理两次磁贴。这意味着，我在递归调用中没有错误。这也意味着，堆栈太小了。

有人知道如何避免堆栈限制吗？

[根据 Erics 的回答更新我的代码]

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

最佳答案

如果我对您的问题的理解正确，那么您正在尝试计算两个图 block 之间“由……提供支持”关系的传递闭包。非递归地计算传递闭包当然是可能的。

这是一个计算 C# 中关系的传递闭包的非递归算法。您应该能够使其适应您选择的语言。

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

请注意，基本上我在这里所做的是通过在堆上分配我自己的堆栈 来避免堆栈限制。那东西可以长到你喜欢的那么大。 (如果你用完了堆内存，那么你就会遇到更大的问题!)

另请注意，明智的做法是选择一种使“是...的成员？”的数据结构。谓词极其廉价。大小为 n 的数组列表通常是 O(n) 来回答“这个元素是这个集合的成员吗？”这个问题。这意味着您的算法总体上是 O(n^2) 。您能否使用像集合这样的集合或具有 O(1) 包含测试的哈希表？

此外，在纯粹的“代码质量”级别上，此方法可能需要做一些工作。事实上，太多重复代码是一个危险信号。我倾向于像这样的草图来写这个方法:

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

简而言之，不是递归的，没有重复的代码，并且是 O(n)。

关于android - 递归 + 900 个元素 + 邻居检查 = 导致 stackoverflow，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3353644/