Dynamische Programmierung mit vielen Teilproblemen

Dynamische Programmierung mit vielen Teilproblemen. Ich versuche also, dieses Problem in der Interview Street zu lösen:

Gitter Gehen (50 Punkte) ,
Sie sind in einem befindet $N$ -dimensionalen Gitter an der Position $(x_1,x_2,\dots,x_N)$ . Die Abmessungen des Gitters sind $(D_1,D_2,\dots,D_N$ ). In einem Schritt können Sie in einer der $N$ Dimensionen einen Schritt vorwärts oder rückwärts gehen. (Es sind also immer $2N$ verschiedene Bewegungen möglich). Auf wie viele Arten können Sie M nehmen$M$Schritte, bei denen Sie das Raster zu keinem Zeitpunkt verlassen? Sie verlassen das Gitter, wenn für $x_i$ entweder $x_i \leq 0$ oder $x_i > D_i$ .

Mein erster Versuch war diese auswendig gelernte rekursive Lösung:

def number_of_ways(steps, starting_point):
    global n, dimensions, mem
    #print steps, starting_point
    if (steps, tuple(starting_point)) in mem:
        return mem[(steps, tuple(starting_point))]
    val = 0
    if steps == 0:
        val = 1
    else:
        for i in range(0, n):
            tuple_copy = starting_point[:]
            tuple_copy[i] += 1
            if tuple_copy[i] <= dimensions[i]:
                val += number_of_ways(steps - 1, tuple_copy)
            tuple_copy = starting_point[:]
            tuple_copy[i] -= 1
            if tuple_copy[i] > 0:
                val += number_of_ways(steps - 1, tuple_copy)
    mem[(steps, tuple(starting_point))] = val
    return val

Große Überraschung: Es schlägt bei einer großen Anzahl von Schritten und / oder Dimensionen aufgrund von Speichermangel fehl.

Der nächste Schritt ist also, meine Lösung durch dynamische Programmierung zu verbessern. Aber bevor ich anfange, sehe ich ein großes Problem mit dem Ansatz. Das Argument starting_pointist ein $n$ Tupel, wobei $n$ so groß wie $10$ . So in der Tat könnte die Funktion sein , number_of_ways(steps, x1, x2, x3, ... x10)mit $1 \leq x_i \leq 100$ .

Die dynamischen Programmierprobleme, die ich in Lehrbüchern gesehen habe, haben fast alle zwei Variablen, so dass nur eine zweidimensionale Matrix benötigt wird. In diesem Fall wäre eine zehndimensionale Matrix erforderlich. Also Zellen insgesamt.$100^{10}$

Bei 2D-Matrizen in der dynamischen Programmierung wird normalerweise nur die vorherige Berechnungsreihe für die nächste Berechnung benötigt, wodurch die räumliche Komplexität von auf min ( m , n ) verringert wird . Ich bin mir nicht sicher, wie ich das in diesem Fall tun würde. Die Visualisierung einer Tabelle ist nicht möglich, daher müsste die Antwort direkt aus der obigen Rekursion stammen.$mn$$\min(m,n)$

AKTUALISIEREN

Verwenden Sie die Vorschläge von Peter Shor und nehmen Sie einige kleinere Korrekturen vor, insbesondere die Notwendigkeit, die Position in der -Funktion zu verfolgen und nicht nur die Dimensionen in zwei Sätze A und B aufzuteilen, sondern die Aufteilung rekursiv und effektiv durchzuführen Eine Divide-and-Conquer-Methode, bis ein Basisfall erreicht ist, in dem sich nur eine Dimension in der Menge befindet.$W(i, t_i)$

Ich habe die folgende Implementierung entwickelt, die alle Tests unterhalb der maximalen Ausführungszeit bestanden hat:

def ways(di, offset, steps):
    global mem, dimensions
    if steps in mem[di] and offset in mem[di][steps]:
        return mem[di][steps][offset]
    val = 0
    if steps == 0:
        val = 1
    else:
        if offset - 1 >= 1:
            val += ways(di, offset - 1, steps - 1)
        if offset + 1 <= dimensions[di]:
            val += ways(di, offset + 1, steps - 1)
    mem[di][steps][offset] = val
    return val


def set_ways(left, right, steps):
    # must create t1, t2, t3 .. ti for steps
    global mem_set, mem, starting_point
    #print left, right
    #sleep(2)
    if (left, right) in mem_set and steps in mem_set[(left, right)]:
        return mem_set[(left, right)][steps]
    if right - left == 1:
        #print 'getting steps for', left, steps, starting_point[left]
        #print 'got ', mem[left][steps][starting_point[left]], 'steps'
        return mem[left][steps][starting_point[left]]
        #return ways(left, starting_point[left], steps)
    val = 0
    split_point =  left + (right - left) / 2 
    for i in xrange(steps + 1):
        t1 = i
        t2 = steps - i
        mix_factor = fact[steps] / (fact[t1] * fact[t2])
        #print "mix_factor = %d, dimension: %d - %d steps, dimension %d - %d steps" % (mix_factor, left, t1, split_point, t2)
        val += mix_factor * set_ways(left, split_point, t1) * set_ways(split_point, right, t2)
    mem_set[(left, right)][steps] = val
    return val

import sys
from time import sleep, time

fact = {}
fact[0] = 1
start = time()
accum = 1
for k in xrange(1, 300+1):
    accum *= k
    fact[k] = accum
#print 'fact_time', time() - start

data = sys.stdin.readlines()
num_tests = int(data.pop(0))
for ignore in xrange(0, num_tests):
    n_and_steps = data.pop(0)
    n, steps = map(lambda x: int(x), n_and_steps.split())
    starting_point = map(lambda x: int(x), data.pop(0).split())
    dimensions = map(lambda x: int(x), data.pop(0).split())
    mem = {}
    for di in xrange(n):
        mem[di] = {}
        for i in xrange(steps + 1):
            mem[di][i] = {}
            ways(di, starting_point[di], i)
    start = time()
    #print 'mem vector is done'
    mem_set = {}
    for i in xrange(n + 1):
        for j in xrange(n + 1):
            mem_set[(i, j)] = {}
    answer = set_ways(0, n, steps)
    #print answer
    print answer % 1000000007
    #print time() - start

Die verschiedenen Dimensionen sind unabhängig . Was Sie tun können, ist für jede Dimension j zu berechnen, wie viele verschiedene Spaziergänge es in genau dieser Dimension gibt, die Schritte ausführen. Nennen wir diese Nummer W ( j , t ) . Aus Ihrer Frage wissen Sie bereits, wie Sie diese Zahlen mit dynamischer Programmierung berechnen können.$t$$W(j,t)$

Jetzt ist es einfach , die Anzahl der Schichten zu zählen , die nehmen in Dimension Schritte i . Sie haben ($t_i$$i$Wegen der Dimensionenso dass die Gesamtzahl der Schritte interspersing in Dimensioniistti, und für jede dieser Möglichkeitenwie Sie habenΠN1W(i,ti)geht. Summiere diese, um ∑t1+t2+…+tN=M($N \choose t_1,t_2, \ldots, t_M$$i$$t_i$$\Pi_1^N W(i,t_i)$ Jetzt ist der Speicher unter Kontrolle, da Sie sich nur noch die WerteW(j,t)merken müssen. Die Zeit wächst für großeNsuperpolynomiell, aber die meisten Computer haben viel mehr Zeit als Speicher.

Sie können es noch besser machen. Teilen Sie die Dimensionen rekursiv in zwei Teilmengen, und B , und berechnen Sie, wie viele Spaziergänge es gibt, indem Sie nur die Dimensionen in Teilmenge A und nur die in B verwenden . Nennen Sie diese Nummern W A ( t ) bzw. W B ( t ) . Sie erhalten die Gesamtzahl der Spaziergänge vorbei$A$$B$$A$$B$$W_A(t)$$W_B(t)$

$\newcommand{\now}{\operatorname{now}}\now(s,x_1,\dots,x_n)$

$\qquad \begin{align} \now(s,x_1,\dots,x_n) = \phantom{+} &\sum_{i=0}^n \now(s-1,x_1,\dots,x_{i-1},x_i + 1, x_{i+1},\dots,x_n) \\ + &\sum_{i=0}^n\now(s-1,x_1,\dots,x_{i-1},x_i - 1, x_{i+1},\dots,x_n) \end{align}$

Hier sind ein paar Ideen.

• $s=k$$s<k$
• $s$$x_1=i$$x_1\leq i-2$$x_2$$x_1=i$$x_1 = i$$x_2 \leq j-2$$x_2=j$ erreicht ist - und so weiter.
• $2N$$x_i - M > 0$$x_i + M < D_i$$i$$(2N)^M$$M\ll N$
• $0$$M\ll N$$2M$$x$ (beachten Sie, dass er aufgrund von Pfaden, die das Gitter verlassen, verbeult wird).

Das sollte ausreichen, um die Speichernutzung recht gering zu halten.