Я наткнулся на проблему в Project Euler, https://projecteuler.net/problem=15. Я решил это с помощью комбинаторики, но мне было интересно, есть ли решение этой проблемы или подобных проблем в целом с помощью динамического программирования. А скажем, какие-то квадраты сетки сняты - можно ли ориентироваться? Я использую Python. Как мне это сделать? Любые советы приветствуются. Заранее спасибо.
Навигация по сетке
- Возможный дубликат алгоритма Lattice paths не закончить бег по сетке 20 x 20 26.01.2018
- Вы можете найти интересные решения для задач Project Euler, если заглянете на их форумы. Например, для этого примерно на полпути вниз по странице есть решение на Ruby с использованием динамического программирования. Так что это, по крайней мере, подтверждает, что то же самое возможно и в Python. 26.01.2018
Ответы:
Существует также математическое решение (которое, вероятно, вы использовали):
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
def paths(w, h):
return factorial(w + h) / (factorial(w) * factorial(h))
Это работает, потому что количество путей такое же, как количество способов выбрать путь вправо или вниз за w + h
шагов, где вы идете вправо w раз, что равно w + h choose w
или (w + h)! / (w! * h!)
.
С отсутствующими квадратами сетки, я думаю, есть комбинаторное решение, но оно очень медленное, если есть много отсутствующих квадратов, поэтому динамическое программирование, вероятно, было бы лучше.
Например, следующее должно работать:
missing = [
[0, 1],
[0, 0],
[0, 0],
]
def paths_helper(x, y, path_grid, missing):
if path_grid[x][y] is not None:
return path_grid[x][y]
if missing[x][y]:
path_grid[x][y] = 0
return 0
elif x < 0 or y < 0:
return 0
else:
path_count = (paths_helper(x - 1, y, path_grid, missing) +
paths_helper(x, y - 1, path_grid, missing))
path_grid[x][y] = path_count
return path_count
def paths(missing):
arr = [[None] * w for _ in range(h)]
w = len(missing[0])
h = len(missing)
return paths_helper(w, h, arr, missing)
print paths()
Вы можете сделать простой возврат и исследовать неявный граф следующим образом: (комментарии объясняют большую часть этого)
def explore(r, c, n, memo):
"""
explore right and down from position (r,c)
report a rout once position (n,n) is reached
memo is a matrix which saves how many routes exists from each position to (n,n)
"""
if r == n and c == n:
# one path has been found
return 1
elif r > n or c > n:
# crossing the border, go back
return 0
if memo[r][c] is not None:
return memo[r][c]
a= explore(r+1, c, n, memo) #move down
b= explore(r, c+1, n, memo) #move right
# return total paths found from this (r,c) position
memo[r][c]= a + b
return a+b
if __name__ == '__main__':
n= 20
memo = [[None] * (n+1) for _ in range(n+1)]
paths = explore(0, 0, n, memo)
print(paths)
Наиболее прямолинейно со встроенной в Python утилитой запоминания functools.lru_cache
. Вы можете закодировать отсутствующие квадраты как frozenset
(хешируемое) отсутствующих точек сетки (пар):
from functools import lru_cache
@lru_cache(None)
def paths(m, n, missing=None):
missing = missing or frozenset()
if (m, n) in missing:
return 0
if (m, n) == (0, 0):
return 1
over = paths(m, n-1, missing=missing) if n else 0
down = paths(m-1, n, missing=missing) if m else 0
return over + down
>>> paths(2, 2)
6
# middle grid point missing: only two paths
>>> paths(2, 2, frozenset([(1, 1)]))
2
>>> paths(20, 20)
137846528820