洪水填充算法 - 迷宮導航

我想實現洪水填充算法的一個版本來幫助解決微型鼠標迷宮的最短距離路徑。除了每個相鄰的非填充地點將被分配一個代表該地點到出發地的距離的數字之外，其工作方式與常規填充填充相同。每次算法移動到不同的單元格時，數字都會加1。這裏是一個沒有從左下角開始的迷宮的例子。洪水填充算法 - 迷宮導航

2 3 4 
1 2 3 
0 1 2

下面是當前代碼我有...

void nav_flood_rec(struct nav_array *array, int row, int column, int flood_num) 
{ 
    //Check the base case (not shown here) 
    if (base_case) 
     return; 

    //Assign the flood number 
    arrray->cells[row][column]->flood_number = flood_num; 

    //North 
    nav_flood_rec(array, row + 1, column, flood_num + 1); 

    //East 
    nav_flood_rec(array, row, column + 1, flood_num + 1); 

    //South 
    nav_flood_rec(array, row - 1, column, flood_num + 1); 

    //West 
    nav_flood_rec(array, row, column - 1, flood_num + 1); 
}

是我遇到的問題是，遞歸是不是在一個時間前進了一大步（有點含糊，但讓我解釋一下）。而不是檢查所有方向，然後移動算法將繼續向北移動而不檢查其他方向。似乎我想讓其他遞歸調用以某種方式產生，直到檢查其他方向。有沒有人有什麼建議？

來源

2013-04-03 Stefan Bossbaly

當您描述的內容聽起來像是您想要廣度優先搜索時，您已經實現了類似於深度優先搜索的內容。

使用隊列而不是堆棧。這裏你沒有明確地使用堆棧，但遞歸本質上是一個隱式堆棧。一個隊列也將解決堆棧溢出的問題，這看起來可能有很多遞歸。

此外，正如G.Bach所說，您需要將單元格標記爲已訪問，以便您的算法終止。

來源

2013-04-03 00:07:56 Pubby

+1這聽起來和BFS完全一樣。一個隊列將解決堆棧溢出問題，但它不會解決非終止循環。處理過的單元需要這樣標記。 –

哦，我看到我出錯的地方。唯一的問題是這是在微處理器上，並且只有內存堆棧（沒有動態內存），這意味着沒有malloc（）。我可以用一個數組來實現一個隊列，但是這看起來效率很低。 –

@StefanBossbaly如果你知道隊列中最多有多少元素，你可以非常有效地做到這一點。分配一個數組，保留一個'front'和''length'計數器，每次移除一個物品時增加'front'計數器並減少'length'計數器，每次放入物品時增加'length'計數器隊列。這兩個增量都是模數組的大小。 'front'計數器告訴你下一個要處理的元素在哪裏，'length'計數器告訴你隊列中有多少個元素。關於你的堆棧溢出問題，你需要標記單元格。 –

Wikipedia's article on the subject：

一種被明確基於隊列的實現顯示在下面的僞代碼。它類似於簡單的遞歸解決方案，但反而讓遞歸調用，它推的節點到LIFO隊列 - 作爲一個堆棧 - 消費：

Flood-fill (node, target-color, replacement-color): 
1. Set Q to the empty queue. 
2. Add node to the end of Q. 
4. While Q is not empty: 
5.  Set n equal to the last element of Q. 
7.  Remove last element from Q. 
8.  If the color of n is equal to target-color: 
9.   Set the color of n to replacement-color. 
10.  Add west node to end of Q. 
11.  Add east node to end of Q. 
12.  Add north node to end of Q. 
13.  Add south node to end of Q. 
14. Return.

來源

2013-04-03 00:14:44

你叫north()沒有測試任何條件語句。因此，意志，你的遞歸依次是：

1）基本情況
2）設置新的洪水號
3）遭遇//north，並呼籲nav_flood_rec()
4）重複測試。

正如你所見，你永遠不會接到你的其他電話。你需要實現一個條件測試，分支它，或者類似的東西。

不確定你想要做什麼，但你可以傳遞另一個結構作爲參數，併爲每個方向都有一個值，然後測試它們是否相等......就像......

struct decision_maker { 
    int north; 
    int south; 
    int west; 
    int east; 
};

然後在你的代碼：

/* assume dm is passed as a pointer to a decision_maker struct */ 

if (dm->north > dm->south) { 
    if (dm->south > dm->east) { 
    dm->east++; // increment first 
    // call east 
    } else if (dm->south > dm->west) { 
    dm->west++; // increment first 
    // call west 
    } else { 
    dm->south++; 
    // call south 
} else { 
    dm->north++; 
    // call north 
} 
/* 
* needs another check or two, like altering the base case a bit 
* the point should be clear, though. 
*/

它會變得有些混亂，但它會做的工作。

來源

2013-04-03 00:37:42 d0rmLife

洪水填充算法 - 迷宮導航

回答

相關問題