Programmation dynamique avec un grand nombre de sous-problèmes

Programmation dynamique avec un grand nombre de sous-problèmes. J'essaie donc de résoudre ce problème depuis Interview Street:

Grid Walking (Score 50 points)
Vous êtes situé dans une grille à $N$ dimensions à la position $(x_1,x_2,\dots,x_N)$ . Les dimensions de la grille sont $(D_1,D_2,\dots,D_N$ ). En une seule étape, vous pouvez avancer ou reculer d'une étape dans l'une des $N$ dimensions. (Il y a donc toujours $2N$ mouvements différents possibles). De combien de façons pouvez-vous prendre $M$ des étapes telles que vous ne quittez la grille à aucun moment? Vous quittez la grille si pour tout $x_i$ , soit $x_i \leq 0$ ou $x_i > D_i$ .

Mon premier essai a été cette solution récursive mémorisée:

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

Grande surprise: elle échoue pour un grand nombre d'étapes et / ou de dimensions par manque de mémoire.

La prochaine étape consiste donc à améliorer ma solution en utilisant la programmation dynamique. Mais avant de commencer, je vois un problème majeur avec l'approche. L'argument starting_pointest un $n$ tuple, où $n$ est aussi grand que $10$ . Donc, en fait, la fonction pourrait être number_of_ways(steps, x1, x2, x3, ... x10)avec $1 \leq x_i \leq 100$ .

Les problèmes de programmation dynamique que j'ai vus dans les manuels ont presque tous des variables twp, de sorte que seule une matrice à deux dimensions est nécessaire. Dans ce cas, une matrice à dix dimensions serait nécessaire. Soit cellules au total. $100^{10}$

Avec les matrices 2D en programmation dynamique, seule la ligne de calculs précédente est généralement nécessaire pour le calcul suivant, réduisant ainsi la complexité spatiale de à . Je ne sais pas comment je ferais la même chose dans ce cas. La visualisation d'une table n'est pas possible, donc la réponse devrait provenir directement de la récursion ci-dessus. $mn$ $\min(m,n)$

MISE À JOUR

En utilisant les suggestions de Peter Shor et en apportant quelques corrections mineures, notamment la nécessité de garder une trace de la position dans la fonction , et plutôt que de diviser uniquement les dimensions en deux ensembles A et B, en procédant au fractionnement récursivement, en utilisant efficacement une méthode de division et de conquête, jusqu'à ce qu'un scénario de base soit atteint où une seule dimension est dans l'ensemble. $W(i, t_i)$

J'ai trouvé l'implémentation suivante, qui a réussi tous les tests en dessous du temps d'exécution maximal:

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

algorithms efficiency dynamic-programming Alexandre
la source

"il échoue pour un grand nombre d'étapes et / ou de dimensions" - que signifie "échouer" ici?

Raphael

Bienvenue! J'ai modifié votre question pour a) utiliser un formatage Markdown et LaTeX approprié (veuillez le faire vous-même à l'avenir) et b) supprimer la gouttière superflue. Nous ne nous soucions pas des descriptions de code C; veuillez vous limiter aux idées , c'est-à-dire au pseudo-code des choses centrales.

Raphael

Échec signifie qu'il épuise toute la mémoire système disponible en remplissant le mem[]dictionnaire. Et merci d'avoir nettoyé ma réponse. Pas trop familier avec LaTeX mais fera un effort la prochaine fois.

Alexandre

Vous pouvez trouver de l'aide sur Markdown à côté de la boîte de l'éditeur; voir ici pour une introduction sur LaTeX.

Raphael

Réponses:

Les différentes dimensions sont indépendantes . Ce que vous pouvez faire est de calculer, pour chaque dimension j , combien de parcours différents il y a dans cette seule dimension qui prennent étapes. Appelons ce nombre . D'après votre question, vous savez déjà comment calculer ces nombres avec une programmation dynamique. $t$ $W(j,t)$

Maintenant, il est facile de compter le nombre de marches qui font pas dans la dimension . Vous avez $t_i$ $i$ façons d'interpénétrer les dimensions de sorte que le nombre total de pas effectués dans la dimensionsoit, et pour chacune de ces façons, vous avezmarches. Additionnez-les pour obtenir $N \choose t_1,t_2, \ldots, t_M$ $i$ $t_i$ $\Pi_1^N W(i,t_i)$ Maintenant, la mémoire est sous contrôle, car il suffit de se souvenir des valeurs. Le temps augmente de façon superpolynomiale pour les grands, mais la plupart des ordinateurs ont beaucoup plus de temps que la mémoire.

\sum_{t_{1} + t_{2} + \dots + t_{N} = M} (\binom{M}{t_{1}, t_{2}, \dots, t_{N}}) Π_{i = 1}^{N} W (i, t_{i}) .

$\sum_{t_1+t_2+\ldots+t_N=M}{M \choose t_1,t_2,\ldots,t_N}\ \Pi_{i=1}^N W(i,t_i).$

W (j, t)

$W(j,t)$

N

$N$

$A$ $B$ $A$ $B$ $W_A(t)$ $W_B(t)$

\sum_{t_{1} + t_{2} = M} (\binom{M}{t_{1}}) W_{A} (t_{1}) W_{B} (t_{2}) .

$\sum_{t_1 + t_2 = M} {M \choose t_1} \, W_A(t_1) W_B(t_2).$

Peter Shor
la source

Salut Peter. D'accord, c'était l'idée manquante. Maintenant, je n'ai plus qu'un doute. La somme externe itère sur toutes les combinaisons possibles de t1, t2, ... tn cette somme à M. Malheureusement, le nombre de ces combinaisons est C (M + 1, N-1), qui peut être aussi élevé que C (300 +1, 10-9). Très grand nombre ... :(

Alexandre

@Alexandre: Mon deuxième algorithme (commençant par "Vous pouvez faire encore mieux") n'a pas ce problème. J'ai laissé le premier algorithme dans ma réponse parce que c'est le premier que j'ai trouvé et parce que je pense qu'il est beaucoup plus facile d'expliquer le deuxième algorithme comme une variante du premier que de le donner sans aucune motivation.

Peter Shor du

J'ai implémenté le deuxième algorithme. C'est plus rapide, mais toujours trop bas pour les plus grandes limites. Le problème avec le premier était d'itérer sur toutes les possibilités de t1, t2, t3, ... tn qui se résumaient à M. Le deuxième algorithme ne fait qu'itérer sur les solutions à t1 + t2 = M. Mais alors il faut faire la même chose pour Wa (t1), itérant sur les solutions à t1 '+ t2' = t1. Et ainsi de suite récursivement. Voici l'implémentation au cas où vous seriez intéressé: pastebin.com/e1BLG7Gk . Et dans le deuxième algorithme, il devrait y avoir M multinomial sur t1, t2 non?

Alexandre

Ça ne fait rien! Résolu! J'ai également dû utiliser la mémorisation dans la fonction set_ways. Voici la solution finale, qui est extrêmement rapide! pastebin.com/GnkjjpBN Merci pour votre perspicacité Peter. Vous avez fait les deux observations clés: l'indépendance du problème et la division et la conquête. Je recommande aux gens de regarder ma solution car il y a des choses qui ne sont pas dans la réponse ci-dessus, comme la fonction W (i, ti) nécessitant un troisième argument, qui est la position. Cela doit être calculé pour les combinaisons de valeurs de i, ti et position. Si vous le pouvez, ajoutez également t2 le multinomial dans votre deuxième algorithme.

Alexandre

$\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}$

Voici quelques idées.

$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$ lorsque $x_2=j$
$2N$ $x_i - M > 0$ $x_i + M < D_i$ $i$ $(2N)^M$ $M\ll N$
$0$ $M\ll N$ $2M$ $x$ (notez qu'il sera bosselé à cause des chemins quittant la grille).

Cela devrait être suffisant pour maintenir une utilisation de la mémoire assez faible.

Raphael
la source

Salut Raphael, disons que notre objectif est maintenant (3, 3, 3, 3), sur une grille 5x5x5. En utilisant la programmation dynamique et en utilisant l'ordre lex comme vous l'avez suggéré, nous calculerions maintenant (0, 0, 0, 0), puis (0, 0, 0, 1), ... maintenant (0, 5, 5, 5). À quel moment nous pourrions nous débarrasser maintenant (0, 0, 0, 0) (ce qui est plus d'un rayon de un de (5, 5, 5), car nous en aurons maintenant besoin pour calculer maintenant (1, 0, 0 , 0), maintenant (1, 0, 0, 1), etc.? Vous avez mentionné M << N plusieurs fois, mais les limites sont 1 <= M <= 300 et 1 <= N <= 10. Donc , aux extrêmes, il ne semble pas que 1 << 300.

Alexandre

(2, 0, 0, 0)

$(2,0,0,0)$

(0, \*, \*, \*)

$(0,\*,\*,\*)$

(0, 0, 0, 0)

$(0,0,0,0)$

(1, 0, 0, 0)

$(1,0,0,0)$

M

$M$

N

$N$

M ≪ N

$M \ll N$

M = 1

$M=1$

N = 10

$N=10$

La 1) balle que je comprends. Cela réduit la complexité spatiale de M * D ^ N à D ^ N, mais D ^ N est encore trop. Je ne vois pas vraiment comment fonctionne la 2) puce. Pouvez-vous utiliser l'exemple de mon commentaire pour l'illustrer?

Alexandre

D

$D$

max_{i = 1, \dots, N} D_{i}

$\max_{i=1,\dots,N} D_i$ , puis l'application de la deuxième puce une fois réduit la complexité de l'espace à

D^{N - 1}

$D^{N-1}$ , la deuxième fois

D^{N - 2}

$D^{N-2}$ etc. (Plus précisément, cela va de

\prod_{i = 1}^{N} D_{i}

$\prod_{i=1}^N D_i$ à

\prod_{i = 2}^{N} D_{i}

$\prod_{i=2}^N D_i$ et ainsi de suite.)

Raphael

Je ne sais pas trop comment le faire ... Disons que j'ai compris et que j'ai réduit la complexité spatiale à D. Fondamentalement, les sous-problèmes M * D ^ N n'ont-ils pas encore besoin d'être résolus? Une propriété supplémentaire n'est-elle pas nécessaire pour rendre le problème polynomial?

Alexandre