貪婪遞歸搜索

我的教授給了我們一個任務，我需要在網格中的某個點上搜索組成一個組的所有其他點（在這個例子中，我需要找到一個「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

貪婪遞歸搜索

回答

相關問題