Programación dinámica con gran cantidad de subproblemas.

11

Programación dinámica con gran cantidad de subproblemas. Así que estoy tratando de resolver este problema desde Interview Street:

Caminata de cuadrícula (Puntuación 50 puntos)
Está situado en una cuadrícula dimensional en la posición . Las dimensiones de la cuadrícula son ). En un paso, puede caminar un paso adelante o atrás en cualquiera de las dimensiones. (Por lo tanto, siempre hay movimientos diferentes posibles). ¿De cuántas maneras puede dar pasos para no abandonar la cuadrícula en ningún momento? Dejas la cuadrícula si para cualquier , ya sea o .N(x1,x2,,xN)(D1,D2,,DNN2NMxixi0xi>Di

Mi primer intento fue esta solución recursiva memorable:

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

Gran sorpresa: falla por una gran cantidad de pasos y / o dimensiones debido a la falta de memoria.

Entonces, el siguiente paso es mejorar mi solución usando programación dinámica. Pero antes de comenzar, veo un problema importante con el enfoque. El argumento starting_pointes una -tupla, donde es tan grande como . De hecho, la función podría ser con .n 10 1 x i100nn10number_of_ways(steps, x1, x2, x3, ... x10)1xi100

Los problemas de programación dinámica que he visto en los libros de texto casi todos tienen variables twp, por lo que solo se necesita una matriz bidimensional. En este caso, se necesitaría una matriz de diez dimensiones. Entonces celdas en total.10010

Con las matrices bidimensionales en programación dinámica, generalmente solo se necesita la fila anterior de cálculos para el siguiente cálculo, por lo tanto, se reduce la complejidad espacial de a . No estoy seguro de cómo haría lo mismo en este caso. Visualizar una tabla no es factible, por lo que la respuesta tendría que venir directamente de la recursividad anterior.mnmin(m,n)

ACTUALIZAR

Usando las sugerencias de Peter Shor, y haciendo algunas correcciones menores, en particular la necesidad de realizar un seguimiento de la posición en la función , y en lugar de solo dividir las dimensiones en dos conjuntos A y B, dividiendo recursivamente, efectivamente usando un método de divide y vencerás, hasta que se alcance un caso base donde solo haya una dimensión en el conjunto.W(i,ti)

Se me ocurrió la siguiente implementación, que pasó todas las pruebas por debajo del tiempo máximo de ejecución:

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
Alexandre
fuente
2
"falla para una gran cantidad de pasos y / o dimensiones", ¿qué significa "falla" aquí?
Raphael
1
¡Bienvenidos! Edité su pregunta para a) usar el formato adecuado de Markdown y LaTeX (por favor, para usted mismo en el futuro) yb) eliminar el canal superfluo. No nos interesan los borrones de código C; restringirse a las ideas , que es el pseudocódigo de las cosas centrales
Raphael
Falla significa que agota toda la memoria del sistema disponible al llenar el mem[]diccionario. Y gracias por limpiar mi respuesta. No estoy muy familiarizado con LaTeX pero hará un esfuerzo la próxima vez.
Alexandre
Puede encontrar ayuda en Markdown junto al cuadro del editor; Vea aquí una introducción a LaTeX.
Raphael

Respuestas:

14

Las diferentes dimensiones son independientes . Lo que puede hacer es calcular, para cada dimensión j , cuántas caminatas diferentes hay en esa dimensión que pasos. Llamemos a ese número . A partir de su pregunta, ya sabe cómo calcular estos números con programación dinámica.tW(j,t)

Ahora, es fácil contar la cantidad de caminatas que toman pasos en la dimensión . Tiene formas de intercalar dimensiones para que el número total de pasos dados en la dimensión sea , y para cada una de estas formas tenga camina. Suma estos para obtener Ahora, la memoria está bajo control, ya que solo necesita recordar los valores . El tiempo crece súper polinomialmente para grande , pero la mayoría de las computadoras tienen mucho más tiempo que memoria.tii(Nt1,t2,,tM)itiΠ1NW(i,ti)

t1+t2++tN=M(Mt1,t2,,tN) Πi=1NW(i,ti).
W(j,t)N

Puedes hacerlo aún mejor. Recursiva dividir las dimensiones en dos subgrupos, y , y calcular cuántos camina Hay utilizando sólo las dimensiones en subconjunto , y sólo los de . Llame a estos números y , respectivamente. Obtienes el número total de caminatas porABABWA(t)WB(t)

t1+t2=M(Mt1)WA(t1)WB(t2).
Peter Shor
fuente
Hola Pedro. Muy bien, esa era la idea faltante. Ahora solo me queda una duda. La suma externa itera sobre todas las combinaciones posibles de t1, t2, ... tn esa suma a M. Desafortunadamente, el número de tales combinaciones es C (M + 1, N-1), que puede ser tan alto como C (300 +1, 10-9). Número muy grande ... :(
Alexandre
1
@Alexandre: Mi segundo algoritmo (que comienza con "Puedes hacerlo aún mejor") no tiene ese problema. Dejé el primer algoritmo en mi respuesta porque es el primero que se me ocurrió, y porque creo que es mucho más fácil explicar el segundo algoritmo como una variante del primero que simplemente darlo sin ninguna motivación.
Peter Shor
Implementé el segundo algoritmo. Es más rápido, pero sigue siendo demasiado bajo para los límites más grandes. El problema con el primero era iterar sobre todas las posibilidades de t1, t2, t3, ... tn que sumaba a M. El segundo algoritmo solo itera sobre soluciones a t1 + t2 = M. Pero entonces lo mismo debe hacerse para Wa (t1), iterando sobre soluciones a t1 '+ t2' = t1. Y así sucesivamente. Aquí está la implementación en caso de que esté interesado: pastebin.com/e1BLG7Gk . Y en el segundo algoritmo, el multinomio debería ser M sobre t1, t2 no?
Alexandre
¡No importa! ¡Resuelto! También tuve que usar la memorización en la función set_ways. ¡Aquí está la solución final, que es increíblemente rápida! pastebin.com/GnkjjpBN Gracias por su perspicacia Peter. Hiciste ambas observaciones clave: problema de independencia y divide y vencerás. Recomiendo que la gente vea mi solución porque hay algunas cosas que no están en la respuesta anterior, como la función W (i, ti) que necesita un tercer argumento, que es la posición. Eso tiene que calcularse para combinaciones de valores de i, ti y posición. Si puede, también agregue t2 el multinomio en su segundo algoritmo.
Alexandre
4

una fórmula para de su código (para una celda interna, que ignora los casos de borde):now(s,x1,,xn)

now(s,x1,,xn)=+i=0nnow(s1,x1,,xi1,xi+1,xi+1,,xn)+i=0nnow(s1,x1,,xi1,xi1,xi+1,,xn)

Aquí hay algunas ideas.

  • Vemos que una vez que ha calculado todos los valores para , puede eliminar todos los valores calculados para .s=ks<k
  • Para una fija , debe calcular las entradas de la tabla en orden lexicográfico (solo porque es simple). Luego, tenga en cuenta que cada celda solo necesita esas celdas dentro de un "radio de uno", es decir, ninguna coordenada puede estar más lejos que una. Por lo tanto, una vez que su iteración llegue a , puede soltar todos los valores para . Si eso no es suficiente, haga lo mismo para : para fijo , elimine los valores con y cuando se alcanza , y así sucesivamente.sx1=ix1i2x2x1=ix1=ix2j2x2=j
  • Tenga en cuenta que "por lo que siempre hay movimientos diferentes posibles" se mantiene solo en el centro de la cuadrícula, es decir, si y para todo . Pero eso también significa que la respuesta es fácil en el medio: es sólo . Si tuviera una recurrencia de programación dinámica que funcionara, eso solo le permitiría eliminar la mayor parte de la tabla (si ).2NxiM>0xi+M<Dii(2N)MMN
  • Otra cosa a tener en cuenta es que no tiene que calcular toda la tabla; la mayoría de los valores se completarán con todos modos (si ). Puede restringirse al cubo (hiper) de longitud de borde alrededor de (tenga en cuenta que se abollará debido a los caminos que salen de la cuadrícula).0MN2Mx

Eso debería ser suficiente para mantener el uso de memoria bastante bajo.

Rafael
fuente
Hola Rafael, digamos que nuestro objetivo es ahora (3, 3, 3, 3), en una cuadrícula de 5x5x5. Usando programación dinámica y usando el orden lex como sugirió, calcularíamos ahora (0, 0, 0, 0), luego (0, 0, 0, 1), ... ahora (0, 5, 5, 5). En qué punto podríamos descartar ahora (0, 0, 0, 0) (que está a más de un radio de uno de (5, 5, 5), ya que ahora lo necesitaremos para calcular ahora (1, 0, 0 , 0), ahora (1, 0, 0, 1), etc. Mencionó M << N un par de veces, pero los límites son 1 <= M <= 300 y 1 <= N <= 10. Entonces , en los extremos, no parece que 1 << 300.
Alexandre
1) ¿Qué no está claro en mi segunda viñeta? Tan pronto como calcule , puede descartar . Sin embargo, ese no es el primer punto donde puede descartar ; la última celda para la que lo necesita es . 2) No estoy demasiado preocupado por sus valores específicos para y , para ser honesto. Prefiero mirar el problema general. Si no tienes , las últimas dos viñetas no te ayudarán mucho. embargo, y deberían ser suficientes para notar el efecto, y ninguna de las estrategias duele. (2,0,0,0)(0,\*,\*,\*)(0,0,0,0)(1,0,0,0)MNMNM=1N=10
Rafael
1
La 1) bala entiendo. Eso reduce la complejidad espacial de M * D ^ N a D ^ N, pero D ^ N sigue siendo demasiado. Sin embargo, no estoy viendo cómo funciona la 2) bala. ¿Puedes usar el ejemplo en mi comentario para ilustrarlo?
Alexandre
@Alexandre que hice en mi comentario anterior. Si leo como significado , entonces aplicar la segunda viñeta una vez reduce la complejidad del espacio a , la segunda vez a y pronto. (Más precisamente, va de a y así sucesivamente.)Dmaxi=1,,NDiDN1DN2i=1NDii=2NDi
Rafael
No entiendo muy bien cómo hacerlo ... Digamos que sí entendí, y que reduje la complejidad espacial a D. Fundamentalmente, ¿no será necesario resolver los subproblemas M * D ^ N? ¿No se necesita una propiedad adicional para hacer que el problema sea polinómico?
Alexandre