java-贪婪递归搜索

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-贪婪递归搜索，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1774字，纯文字阅读大概需要3分钟。

内容图文

我的教授给了我们一个作业,我需要在网格中的给定点附近搜索构成一个组的所有其他斑点(在此示例中,我需要找到问题内呈“ L”形的斑点的数量) .

网格是10×10,我的教授给了我们一个起点.我的教授给我们提供了一个想法,即检查相邻的点,并将其添加到集合中,如果新发现了该点(将在集合中),则递归调用该方法.

private Spot findSpots(Set<Spot> spots, Set<Spot> activeSpots, Spot initial) {
    Spot newSpot = null;


    Set<Spot> activeSet = new HashSet<Spot>();
    checkAround(activeSet, new Spot(initial.i - 1, initial.j));
    checkAround(activeSet, new Spot(initial.i + 1, initial.j));
    checkAround(activeSet, new Spot(initial.i, initial.j - 1));
    checkAround(activeSet, new Spot(initial.i, initial.j + 1));


    for (Spot spot : activeSet) {
        newSpot = findSpots(spots, activeSpots, spot);
        if (grid[newSpot.i][newSpot.j] == true)
            spots.add(newSpot);
    }

    return newSpot;
 }
 private boolean checkAround(Set<Spot> spots, Spot spot) {
    if (!spots.contains(spot)) {
        spots.add(spot);
        return true;
    }
    return false;
 }

我知道我需要一个边界条件(否则我会得到stackoverflow异常),但是我需要逻辑上的帮助.

解决方法:

I know I need a boundary condition […]

你自己说的一个关键词是边界.
您需要检查网格中的斑点是否合法,
如果没有,请停止探索.

另一个停止条件是该景点是否已被访问过.

如果您实现了这两个停止条件,
如果您在进行进一步的递归调用之前执行了这些检查,
您将找到解决方案而不会导致堆栈溢出.

像这样：

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的变体,
在Wikipedia页面上查看更多信息以及提示和提示.

内容总结

以上是互联网集市为您收集整理的java-贪婪递归搜索全部内容，希望文章能够帮你解决java-贪婪递归搜索所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端