贪婪递归搜索

我的教授给了我们一个任务，我需要在网格中的某个点上搜索组成一个组的所有其他点（在这个例子中，我需要找到一个“L “问题内的形状）。贪婪递归搜索

所以网格是10x10，我的教授给了我们一个开始的地方。我的教授给了我们一个想法，那就是检查邻近的景点，并将其添加到一个集合中，如果该集合是新发现的（将集合在该集合中），然后递归地调用该方法。我知道我需要一个边界条件（否则我会得到stackoverflow异常），但我需要在逻辑上的帮助。

来源

2016-11-05 Kendrick Lamar

将更多想法放入变量名称中可能会使代码更易于阅读和修改，甚至像“initialSpots”这样的东西，当您试图推理所有这些不同的点结构时，它会使它更容易混淆 – dahui

重新命名了一些变量以方便其他人阅读。 –

也许为Spot类，“搜索”或“hasBeenSearched”添加一个布尔成员变量或函数，当您已经在此位置调用函数时将其设置为true，然后您可以防止函数被调用现货如果Spot.hasBeenSearched – dahui

我知道我需要一个边界条件[...]

你自己说的。一个关键词是边界。您需要检查网格中的某个点是否合法，，如果不是，请停止浏览。

另一种停止条件是如果现场已被访问。

如果实现这两个停止条件，如果你做进一步的递归调用之前进行这些检查，你会发现也不会溢出堆栈的解决方案。

事情是这样的：

private int countSpots(Set<Spot> visited, Spot spot) { 
    if (!isValid(spot) || visited.contains(spot)) { 
     return 0; 
    } 

    visited.add(spot); 

    int count = 1; 
    count += countSpots(visited, new Spot(spot.x - 1, spot.y)); 
    count += countSpots(visited, new Spot(spot.x + 1, spot.y)); 
    count += countSpots(visited, new Spot(spot.x, spot.y + 1)); 
    count += countSpots(visited, new Spot(spot.x, spot.y - 1)); 
    return count; 
}

顺便说一句，你正在使用的算法是flood fill变体，看到在维基百科页面的详细信息和提示和提示。

来源

2016-11-05 23:08:44 janos

你先生帮助我，因为你告诉我它是什么类型的算法，我设法改变代码并完成它。 –

的方式我做它：

我增加了对电网
我有两套其中一个包含了所有我访问过的斑点的边界条件，另一个包含我需要
回归现货已经在这两方面的
斑点添加到组适当的
递归调用各地现货

来源

2016-11-05 23:43:58

贪婪递归搜索

回答

相关问题