logo标签列表

递归 + 900元素 + 邻居检查 = 导致堆栈溢出错误。

androidstackarrayliststack-overflow
5
我有一款城市模拟游戏，想要找到一种方法来检查我们的电力系统流量。 基本原理： 城市地图是基于瓷砖构建的（30 x 30个瓷砖 = 900个瓷砖）。 现在我从一个发电厂开始，进行递归邻居检查（上方，左侧，右侧，下方），以检查是否存在可传输电力的东西。如果有，我会继续检查这些瓷砖的邻居。 为了防止重复检查和/或无限递归调用，我使用ArrayList填充已处理的瓷砖，并检查新的瓷砖是否已被处理并添加到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};
}
我这里没有看到基本情况... - NullUserException
1
@NullUserException：基本情况是“如果在任何方向上都没有未处理的电源瓷砖，则不执行任何操作”。您看不到它，因为不需要编写代码来实现“不执行任何操作”。 - Eric Lippert
顺便提一下，创建线程时可以显式地设置线程堆栈的大小（请参阅线程构造函数）。正如其他人所指出的那样，这并不是正确的解决方案，但为了完整起见我想提一下。 - fadden
@Fadden，这是真的，但文档中也提到给定的大小可能会被完全忽略。因此，这不仅不正确，而且根本不是解决方案，但Eric给了我正确的答案。 - WarrenFaith
5个回答
17

如果我正确理解您的问题，您正在尝试计算两个瓷砖之间“由...驱动”关系的传递闭包。非递归地计算传递闭包是完全可能的。

这里有一个在C#中计算关系传递闭包的非递归算法。您应该能够将其调整为您选择的语言。

链接

请注意，我所做的基本上是通过在堆上分配自己的堆栈来避免堆栈限制。那个东西可以随意增长。（如果您用尽了堆内存，那么您就有更大的问题！）

还要注意，明智的选择数据结构使“是否为成员？”谓词非常便宜。大小为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)。

我必须承认我不太熟悉复杂性理论，但是你的代码很有效！ 我更新了问题并附上了我写的代码。 - WarrenFaith
1
@WarrenFaith：很高兴你喜欢它。关于复杂性的问题是，当你询问“这个包含n个元素的数组列表是否包含x？”时，它回答这个问题的方式是：“第一个项目是x吗？不是。第二个项目是x吗？不是。...第n个项目是x吗？不是。好的，它不在列表中”。如果该列表中有400个项目，则每次通过循环都要进行400次比较。ArrayList针对快速插入到末尾进行了优化，代价是慢速搜索。您可以考虑使用一些“集合”数据类型，它们针对快速搜索进行了优化，因为大多数操作都是搜索。 - Eric Lippert
比 true 更多。感谢这个建议！总是忘记显而易见的事情） - WarrenFaith
作为一名程序员，你应该花一些时间了解复杂度和大O符号的概念。 - Brian
你首先应该问一下“不熟悉”是什么意思 :) - WarrenFaith
3
你只需要将递归实现转换为迭代实现（理论告诉我们这是始终可行的）。
例如，你可以：
- 维护一个待检查的单元格队列 - 当此队列不为空时，处理队列的前端元素
- 要处理单元格，请对单元格本身执行必要的操作，然后对其四个邻居中的每一个进行以下操作： - 如果它们尚未在队列中，则将它们添加到队列中
- 重复以上步骤直到队列为空。
一个小细节是，如果你正在使用不可变的数据结构，那么使用栈比使用队列几乎总是更有效率的。结果将是相同的，只是处理事物的顺序会有所不同。 - Eric Lippert
@Eric，你是在指集合中的对象是不可变的，还是指函数式编程风格的不可变容器，就像你最近写博客所述的那样？ - AakashM
1
我指的是数据容器。一个不可变的栈比一个不可变的队列更便宜。 - Eric Lippert
0
一个高效的递归算法应该能够正常工作，只要在递归之前清除标志（我假设你只是在设置标志来表示瓷砖是否有电源）。可以像这样做：
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);
}

这在使用非常庞大的网格尺寸之前应该工作得很好。

0

你可以将其变成迭代的。有两个列表，一个用于跟踪您已经访问过的位置，另一个用于跟踪您当前正在检查的位置。

伪代码与您的代码：

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
}
0
我会尝试的第一件事就是将搜索顺序从北-南-西-东改为北-东-南-西。像这样：
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);
}

这可能会减少递归深度，取决于所涉及的映射。
最小递归深度取决于图形的形状，而不是递归执行的顺序。最小可能值等于到离电源最远的方块的最短路径长度。在30x30的网格上，我们可以轻松构建一个子集，它是450个节点长的单一路径，因此我们需要能够处理至少450次递归，并且对于n x n图形，我们需要能够处理n^2 / 2次递归。递归解决方案根本无法扩展；我们需要采用非递归解决方案。 - Eric Lippert
@Eric Lippert - 是的，当然你是对的。当我写这个答案时，我想象它们被处理的顺序可能会在由大量连续网格区域组成的图中产生影响，但我没有考虑到在深度优先搜索中它没有任何影响。螺旋和扫描一样糟糕。我还认为设计用于创建最长路径的病态配置不是问题，但是，在游戏中，每个人都会尝试这样做！ - Jeffrey L Whitledge
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接