Benötigen Sie Hilfe beim Verständnis des Ansatzes der dynamischen Programmierung für eine "ausgeglichene 0-1-Matrix"?

Question

Problem: Ich habe Schwierigkeiten mit dem Dynamic Programming Ansatz für „Eine Art von ausgewogener 0-1 Matrix in "Dynamic Programming zu verstehen/visualisieren - Wikipedia Artikel"

Wikipedia. Link: https://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0.E2.80.931_matrix

konnte ich nicht Wenn man versucht, die Fibonacci-Reihe mit DP zu lösen, ist es einfach, ein Array zum Speichern vorheriger Zustandsergebnisse zu verwenden, da der Indexwert des Arrays die Lösung für diesen Zustand speichert.

Kann jemand den DP-Ansatz für die "0-1 balanced Matrix" auf einfachere Weise erklären?

Answer 1

Sie memoisieren Zustände, die wahrscheinlich wiederholt werden. Der Zustand, der in diesem Fall erinnert werden muss, ist der Vektor (k ist implizit). Schauen wir uns eines der Beispiele an, das Sie linked an. Jedes Paar im Vektorargument (mit der Länge n) repräsentiert "die Anzahl der Nullen und Einsen, die noch in dieser Spalte platziert werden müssen".

Nehmen wir das Beispiel auf der linken Seite, wo der Vektor ((1, 1) (1, 1) (1, 1) (1, 1)), when k = 2 und die Zuordnungen, die zu ihm waren 1 0 1 0, k = 3 und 0 1 0 1, k = 4 ist. Aber wir könnten den gleichen Zustand ((1, 1) (1, 1) (1, 1) (1, 1)), k = 2 aus einem anderen Satz von Zuordnungen erhalten, zum Beispiel: 0 1 0 1, k = 3 und . Wenn wir das Ergebnis für den Zustand notieren würden, ((1, 1) (1, 1) (1, 1) (1, 1)), könnten wir vermeiden, die Rekursion für diesen Zweig erneut neu zu berechnen.

Bitte lassen Sie mich wissen, wenn es etwas gibt, was ich besser klären könnte.

weitere Ausarbeitung in Reaktion auf Ihren Kommentar:

Die Wikipedia Beispiel scheint ziemlich eine Brute-Force mit memoization zu sein. Der Algorithmus scheint zu versuchen, alle Matrizen aufzuzählen, verwendet jedoch Memoization, um früh aus wiederholten Zuständen zu beenden. Wie listen wir alle Möglichkeiten auf? Um ihr Beispiel zu nehmen, n = 4, beginnen wir mit dem Vektor [(2,2),(2,2),(2,2),(2,2)] wo Nullen und Einsen noch platziert werden müssen. (Da die Summe jedes Tupel in dem Vektor k ist, könnten wir ein einfacheres Vektor haben, wo k und die Zählung von entweder Einsen oder Nullen beibehalten wird.)

In jeder Phase k, in der Rekursion, aufzuzählen wir alle mögliche Konfigurationen für den nächsten Vektor. Wenn der Status in unserem Hash existiert, geben wir einfach den Wert für diesen Schlüssel zurück. Andernfalls weisen wir den Vektor als neuen Schlüssel im Hash zu (in diesem Fall wird dieser Rekursionszweig fortgesetzt).

Zum Beispiel:

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

Wikipedia angeboten sowohl eine beschissene Erklärung und einen nicht idealen Algorithmus. Aber arbeiten wir damit als Ausgangspunkt.

Zuerst nehmen wir den Backtracking-Algorithmus. Anstatt die Zellen der Matrix "in eine bestimmte Reihenfolge" zu bringen, gehen wir in die erste Reihe, dann alles in die zweite Reihe, dann alles in die dritte Reihe und so weiter. Das wird klar funktionieren.

Jetzt ändern wir den Backtracking-Algorithmus etwas. Anstatt Zelle für Zelle zu gehen, gehen wir Zeile für Zeile. Also machen wir eine Liste der n choose n/2 möglichen Zeilen, die halb 0 und halb 1 sind.Dann eine rekursive Funktion, die in etwa so aussieht:

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 

Dies ist ein Backtracking-Algorithmus wie das, was wir vorher hatten. Wir machen nur ganze Reihen auf einmal, keine Zellen.

Aber beachten Sie, wir geben mehr Informationen weiter, als wir brauchen. Es besteht keine Notwendigkeit, die genaue Anordnung der Zeilen zu übergeben. Alles, was wir wissen müssen, ist, wie viele 1s in jeder verbleibenden Spalte benötigt werden. So können wir den Algorithmus so aussehen lassen:

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 

Diese Version ist fast die rekursive Funktion in der Wikipedia-Version. Der Hauptunterschied ist, dass unser Basisfall ist, dass wir nach jeder Zeile nichts brauchen, während Wikipedia uns den Basisfall aufschreiben lässt, um die letzte Zeile nach jedem anderen zu überprüfen.

Um von diesem zu einem Top-Down-DP zu gelangen, müssen Sie nur die Funktion notieren. Was in Python Sie tun können, indem Sie einen @memoize Dekorateur definieren. Wie folgt:

Aber denken Sie daran, dass ich den Wikipedia-Algorithmus kritisiert habe? Lasst uns anfangen, es zu verbessern! Die erste große Verbesserung ist das. Bemerken Sie, dass die Reihenfolge der Elemente von still_needed nicht wichtig sein kann, nur ihre Werte? Wenn Sie also nur die Elemente sortieren, können Sie die Berechnung nicht für jede Permutation separat durchführen. (Es kann eine Menge von Permutationen sein!)

@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 

Der kleinen harmlos sorted nicht wichtig sieht, aber es spart eine Menge Arbeit! Und jetzt, wo wir wissen, dass still_needed immer sortiert ist, können wir unsere Prüfungen vereinfachen, ob wir fertig sind und ob etwas negativ wurde. Außerdem können wir eine einfache Überprüfung hinzufügen, um den Fall herauszufiltern, in dem wir zu viele 0 in einer Spalte haben.

@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 

Und Sie possible_rows implementieren, vorausgesetzt, sollte diese beide arbeiten und als wesentlich effizienter sein, was Wikipedia angeboten.

=====

ist die komplette Arbeits Umsetzung. Auf meiner Maschine berechnete sie die 6. Laufzeit in weniger als 4 Sekunden.

#! /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)))