需要幫助理解「平衡0-1矩陣」的動態規劃方法？

Question

問題：我努力理解/可視化動態規劃法動態規劃「中的A類平衡的0-1矩陣‘ - 維基百科條目’

維基百科鏈接：https://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0.E2.80.931_matrix

我做不到理解記憶在處理多維數組時如何工作例如，當試圖用DP解決Fibonacci系列時，使用數組來存儲以前的狀態結果很容易，因爲數組的索引值存儲該狀態的解決方案。

有人可以更簡單的方式解釋「0-1平衡矩陣」的DP方法嗎？

Answer 1

您正在記憶可能會重複的狀態。在這種情況下需要記住的狀態是向量（k是隱式的）。我們來看看你的例子之一linked。向量參數中的每對（長度爲n）表示「零和尚未放置在該列中的零的數量」。

以左側爲例，向量爲((1, 1) (1, 1) (1, 1) (1, 1)), when k = 2，導致它的任務分別爲1 0 1 0, k = 3和0 1 0 1, k = 4。但是我們可以從不同的分配集中得到相同的狀態((1, 1) (1, 1) (1, 1) (1, 1)), k = 2，例如：0 1 0 1, k = 3和1 0 1 0, k = 4。如果我們要記憶狀態的結果((1, 1) (1, 1) (1, 1) (1, 1))，我們可以避免重新計算該分支的遞歸。

請讓我知道，如果有什麼我可以更好地澄清。

響應您的評論的進一步闡述：

維基百科的例子似乎是非常蠻力與記憶化。該算法似乎試圖枚舉所有矩陣，但使用記憶來從重複狀態中提前退出。我們如何列舉所有可能性？以他們爲例，n = 4，我們從矢量[(2,2),(2,2),(2,2),(2,2)]開始，其中0和1還沒有被放置。 （由於每個元組中的矢量總和k，我們可以有地方k，要麼一或零的計數保持一個簡單的載體。）

在每一個階段，k，在遞歸，我們枚舉所有下一個向量的可能配置。如果狀態存在於我們的散列中，我們只需返回該鍵的值。否則，我們將該向量作爲散列中的新鍵（在這種情況下，此遞歸分支將繼續）。

例如：

Vector      [(2,2),(2,2),(2,2),(2,2)] 

Possible assignments of 1's: [1 1 0 0], [1 0 1 0], [1 0 0 1] ... etc. 

First branch:    [(2,1),(2,1),(1,2),(1,2)] 
    is this vector a key in the hash? 
    if yes, return value lookup 
    else, assign this vector as a key in the hash where the value is the sum 
    of the function calls with the next possible vectors as their arguments 

Answer 2

維基百科提供的兩個一個蹩腳的解釋和不理想的算法。但讓我們以此作爲起點。

首先讓我們來回溯算法。不要將矩陣的單元格按「某種順序」排列，我們先在第一行中執行所有操作，然後再執行第二行中的所有操作，然後再執行第三行中的所有操作，依此類推。很明顯，這將工作。

現在讓我們稍微修改回溯算法。我們將逐行進行，而不是逐個進行。因此，我們列出了n choose n/2可能的行，它們是0和1。然後有一個遞歸函數，看起來像這樣：

def count_0_1_matrices(n, filled_rows=None): 
    if filled_rows is None: 
     filled_rows = [] 
    if some_column_exceeds_threshold(n, filled_rows): 
     # Cannot have more than n/2 0s or 1s in any column 
     return 0 
    else: 
     answer = 0 
     for row in possible_rows(n): 
      answer = answer + count_0_1_matrices(n, filled_rows + [row]) 
     return answer 

這是一個像我們以前有回溯算法。我們一次只做整行，而不是單元格。

但請注意，我們傳遞的信息超出了我們的需求。沒有必要傳遞行的確切排列。我們需要知道的是每個剩餘列中需要多少個1。所以我們可以使算法看起來更像這樣：

def count_0_1_matrices(n, still_needed=None): 
    if still_needed is None: 
     still_needed = [int(n/2) for _ in range(n)] 

    # Did we overrun any column? 
    for i in still_needed: 
     if i < 0: 
      return 0 

    # Did we reach the end of our matrix? 
    if 0 == sum(still_needed): 
     return 1 

    # Calculate the answer by recursion. 
    answer = 0 
    for row in possible_rows(n): 
     next_still_needed = [still_needed[i] - row[i] for i in range(n)] 
     answer = answer + count_0_1_matrices(n, next_still_needed) 

    return answer 

這個版本幾乎是維基百科版本中的遞歸函數。主要區別在於我們的基本情況是每行完成後我們不需要任何東西，而維基百科會讓我們對基本情況進行編碼，以便在完成每一行後檢查最後一行。

要從此自頂向下DP，您只需要記憶該功能。在Python中你可以通過定義然後添加一個@memoize裝飾器來完成。像這樣：

from functools import wraps 

def memoize(func): 
    cache = {} 
    @wraps(func) 
    def wrap(*args): 
     if args not in cache: 
      cache[args] = func(*args) 
     return cache[args] 
    return wrap 

但請記住，我批評了維基百科算法？讓我們開始改進吧！這是第一大改進。你注意到still_needed元素的順序無關緊要，只是它們的值？所以只要對元素進行排序就會阻止您對每個排列單獨進行計算。 （可以有很多排列！）

@memoize 
def count_0_1_matrices(n, still_needed=None): 
    if still_needed is None: 
     still_needed = [int(n/2) for _ in range(n)] 

    # Did we overrun any column? 
    for i in still_needed: 
     if i < 0: 
      return 0 

    # Did we reach the end of our matrix? 
    if 0 == sum(still_needed): 
     return 1 

    # Calculate the answer by recursion. 
    answer = 0 
    for row in possible_rows(n): 
     next_still_needed = [still_needed[i] - row[i] for i in range(n)] 
     answer = answer + count_0_1_matrices(n, sorted(next_still_needed)) 

    return answer 

這一點無傷大雅sorted看起來並不重要，但它節省了大量的工作！現在我們知道still_needed總是被排序，我們可以簡化我們檢查是否完成，以及是否有負面情況。另外，我們可以添加一個簡單的檢查來過濾掉列中有太多0的情況。

@memoize 
def count_0_1_matrices(n, still_needed=None): 
    if still_needed is None: 
     still_needed = [int(n/2) for _ in range(n)] 

    # Did we overrun any column? 
    if still_needed[-1] < 0: 
     return 0 

    total = sum(still_needed) 
    if 0 == total: 
     # We reached the end of our matrix. 
     return 1 
    elif total*2/n < still_needed[0]: 
     # We have total*2/n rows left, but won't get enough 1s for a 
     # column. 
     return 0 

    # Calculate the answer by recursion. 
    answer = 0 
    for row in possible_rows(n): 
     next_still_needed = [still_needed[i] - row[i] for i in range(n)] 
     answer = answer + count_0_1_matrices(n, sorted(next_still_needed)) 

    return answer 

而且，假設你實現possible_rows，這應該都工作，並顯著比維基百科提供更高效。

=====

這是一個完整的工作實現。在我的機器上，它在4秒內計算出第6個學期。

#! /usr/bin/env python 

from sys import argv 
from functools import wraps 

def memoize(func): 
    cache = {} 
    @wraps(func) 
    def wrap(*args): 
     if args not in cache: 
      cache[args] = func(*args) 
     return cache[args] 
    return wrap 

@memoize 
def count_0_1_matrices(n, still_needed=None): 
    if 0 == n: 
     return 1 

    if still_needed is None: 
     still_needed = [int(n/2) for _ in range(n)] 

    # Did we overrun any column? 
    if still_needed[0] < 0: 
     return 0 

    total = sum(still_needed) 
    if 0 == total: 
     # We reached the end of our matrix. 
     return 1 
    elif total*2/n < still_needed[-1]: 
     # We have total*2/n rows left, but won't get enough 1s for a 
     # column. 
     return 0 
    # Calculate the answer by recursion. 
    answer = 0 
    for row in possible_rows(n): 
     next_still_needed = [still_needed[i] - row[i] for i in range(n)] 
     answer = answer + count_0_1_matrices(n, tuple(sorted(next_still_needed))) 

    return answer 

@memoize 
def possible_rows(n): 
    return [row for row in _possible_rows(n, n/2)] 


def _possible_rows(n, k): 
    if 0 == n: 
     yield tuple() 
    else: 
     if k < n: 
      for row in _possible_rows(n-1, k): 
       yield tuple(row + (0,)) 
     if 0 < k: 
      for row in _possible_rows(n-1, k-1): 
       yield tuple(row + (1,)) 

n = 2 
if 1 < len(argv): 
    n = int(argv[1]) 

print(count_0_1_matrices(2*n)))