如何找到覆蓋2維數組中所有零所需的最少行數？

我試圖做一個體面的匈牙利算法的實施，但是我被困在如何找到覆蓋數組中的所有零的最小數量的行如何找到覆蓋2維數組中所有零所需的最少行數？

也我需要知道這些行使一些計算後

這裏的解釋是：

http://www.ams.jhu.edu/~castello/362/Handouts/hungarian.pdf

在步驟3

它說

使用盡可能少的行來覆蓋矩陣中的所有零。沒有簡單的規則來做到這一點 - 基本上是試錯。

在計算方面試驗和錯誤的含義是什麼？如果我有例如5行和5列的2D陣列然後

的第一行可以覆蓋所有的零，第一和第二，第一行和第一列，等等等等太多組合

ISN有沒有比這更有效率的東西？

在此先感謝

來源

2012-04-09 jan1

試錯法意味着O（（n + m）！）的複雜性。

最多隻需選擇min（n，m）行，因爲選擇所有行或列將覆蓋所有0。

我會實現一個動態編程算法來解決這個大問題的步驟。

來源

2012-04-09 14:19:41

您需要在這裏實施雙向匹配算法。圖中有兩個分區 - 其中一箇中的頂點表示行，另一箇中的頂點表示表中的列。如果在單元格（i，j）中存在1，則在行_i和列_j之間存在邊緣。然後您創建最大二分配匹配。在雙邊匹配算法的最後一次迭代之後，您需要確定哪些頂點通過增量路徑與您的匹配源相連接。增量路徑是僅使用正容量的邊的路徑。你應該有圖片，如：

  row_1     col_1 
     /       \ 
    /- row_2    col_2 -\ 
source - ....  some_edges   \ sink 
     \        /
     \ - row_n    col_n/
           ..../
           col_m

後你會發現最大的雙邊匹配，找到該行和列是通過從宿積極容量可達邊緣。現在，使用以下算法可以找到您需要從頭開始劃分的最少行數和列數 - 將所有無法從源訪問的行和所有可訪問的列刪除，這是您的最佳解決方案。

希望這個答案可以幫助你。

來源

2012-04-09 14:30:03

雖然它會給出一組覆蓋所有零的行，但這不會給出最小的行數;在第二行和第二列使用帶有零的3x3矩陣嘗試算法。你可以用2行覆蓋所有的零，但是這個算法會告訴你使用3行。 – gwilkins 2012-04-09 16:08:59

我有一個錯字 - 您需要找到不是來自信源的可達頂點。在你做的最大匹配（假設它是r_1 - > c_2，r_2 - > c_1）之後的例子中，從源頭可到達的是r_1，r_3，c_2，因此你根據我所解釋的選擇了r_2和c_2。這個解決方案不僅僅是推測 - 這是匈牙利算法的實現方式，我已經解決了這種方法的問題（例如：http://acm.timus.ru/problem.aspx?space=1&num=1076） – 2012-04-09 19:14:57

我認爲我誤解了你的意思是「從源頭上獲得的」。如果您有r_1-> c_2，r_2-> c_1作爲您的匹配，那麼r_3如何從源碼可達？ – gwilkins 2012-04-09 21:04:57

我不太清楚他們爲什麼告訴你做試驗和錯誤。然而，匈牙利算法不需要指數時間。看看維基百科，這將引導您如何找出線路的最小數量的例子（請看第3步）：

http://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation

文章還包含指向具體實施，以及一些在線課程匈牙利算法的說明比你使用的算法更完整（雖然也是更技術性的）。

來源

2012-04-09 16:54:57 gwilkins

如何找到覆蓋2維數組中所有零所需的最少行數？

回答

相關問題