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 .
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_point
es una -tupla, donde es tan grande como . De hecho, la función podría ser con .n 10 1 ≤ x i ≤ 100number_of_ways(steps, x1, x2, x3, ... x10)
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.
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.
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.
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
fuente
mem[]
diccionario. Y gracias por limpiar mi respuesta. No estoy muy familiarizado con LaTeX pero hará un esfuerzo la próxima vez.Respuestas:
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.t W(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.ti i (Nt1,t2,…,tM) i ti ΠN1W(i,ti)
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 porA B A B WA(t) WB(t)
fuente
una fórmula para de su código (para una celda interna, que ignora los casos de borde):now(s,x1,…,xn)
Aquí hay algunas ideas.
Eso debería ser suficiente para mantener el uso de memoria bastante bajo.
fuente