Алгоритм решетки путей не завершает работу для сетки 20 х 20

Question

Я написал следующий код на python для решения проблемы 15 из Project Euler :

grid_size = 2
def get_paths(node):
        global paths

        if  node[0]  >= grid_size and node[1] >= grid_size:
                paths += 1
                return
        else:
                if node[0]<grid_size+1 and node[1] < grid_size+1:
                     get_paths((node[0]+1,node[1]))
                     get_paths((node[0],node[1]+1))
        return paths

def euler():
                print get_paths((0,0))

paths = 0
if __name__ == '__main__':
    euler()

Хотя он работает достаточно хорошо для сетки 2 X 2, он работает часамидля сетки 20 х 20.Как я могу оптимизировать код, чтобы он мог работать на больших сетках?Это что-то вроде первой проблемы поиска?(Мне так кажется.)

Как я могу измерить сложность моего решения в его текущей форме?

Answer 1

Возможно, вы захотите изучить математику, стоящую за этой проблемой. Нет необходимости на самом деле перебирать все маршруты. (Фактически, вы никогда не сделаете такую ​​1-минутную отметку).

Я могу опубликовать подсказку, но не сделаю этого, если вы не попросите об этом, поскольку я не хотел бы испортить ее для вас.

Edit: Да, алгоритм, который вы используете, никогда не будет оптимальным, так как нет способа уменьшить пространство поиска вашей проблемы. Это означает, что (как заявил pg1989) вам придется искать альтернативные способы решения этой проблемы.

Как сказал Сверре, осмотр здесь может подтолкнуть в правильном направлении: http://en.wikipedia.org/wiki/Binomial_coefficient

Здесь можно найти прямое решение (предупреждение, большой спойлер):

Answer 2

Решая задачи в Project Euler, долго думайте о математике проблемы, прежде чем начинать писать код.Эта проблема может быть решена без какого-либо кода.

Мы пытаемся подсчитать количество путей через сетку.Если вы заметили, что количество ходов вниз и вправо не меняется независимо от пути, вам нужно беспокоиться только о порядке, в котором вы двигаетесь вниз и вправо.Таким образом, в случае 2x2 работают следующие комбинации:

DDRR 
DRDR
RDRD
RRDD
RDDR
DRRD

Обратите внимание, что если мы выберем, куда мы помещаем ходы R , размещение движений D определен.Так что на самом деле нам остается только выбрать из 4 доступных слотов движения, которые получают ходы R .Можете ли вы вспомнить математическую операцию, которая делает это?

Answer 3

Ваш алгоритм экспоненциальный, но только потому, что вы переоцениваете get_paths с одним и тем же вводом много раз. Добавление Memoization к нему заставит его работать вовремя. Также вам нужно избавиться от глобальной переменной и использовать вместо нее возвращаемые значения. См. Также Динамическое программирование для аналогичной идеи.

Answer 4

Вероятно, не так, как проект Эйлер хотел, чтобы эта проблема была решена, но ответом является просто центральный биномиальный коэффициент сетки 20x20.

Используя формулу, представленную в статье в вики, вы получаете:

from math import factorial, pow
grid = 20
print int(factorial(2 * grid) / pow(factorial(grid), 2))

Answer 5

Ключ не в том, чтобы заставить ваш алгоритм работать быстрее, так как он (потенциально) будет работать за экспоненциальное время, независимо от того, насколько быстр каждый шаг.

Вероятно, лучше найти другой способ вычисления ответа.Использование вашего (дорогого, но правильного) решения в качестве сравнения для небольших значений, вероятно, является разумным средством сохранения при оптимизации алгоритма.

Answer 6

Вот мое решение:

memo = {(0, 1) : 1, (1, 0) : 1}
def get_pathways(x, y):

    if (x, y) in memo : return memo[(x, y)]

    pathways = 0
    if 0 in (x, y):
        pathways = 1
    else:
        pathways = get_pathways(x-1, y) + get_pathways(x, y-1)


    memo[(x, y)] = pathways
    return pathways

наслаждайтесь:)

Answer 7

Это может быть решено простым наблюдением шаблона для маленьких сеток и определением простой формулы для больших сеток.Для сетки 20x20 существует более 100 миллиардов путей, и любое итеративное решение может занять слишком много времени для вычисления.

Answer 8

Этот вопрос дает хорошее представление об оптимизации. Код в C #, но алгоритмы применимы. Остерегайтесь спойлеров, хотя.

Проект Эйлера # 15