项目欧拉#15

Question

昨晚我试图解决Project Euler挑战赛#15:

从2×2网格的左上角开始,右下角有6条路线(没有回溯).

alt text http://projecteuler.net/project/images/p_015.gif

通过20×20网格有多少条路线？

我认为这不应该这么难,所以我写了一个基本的递归函数:

const int gridSize = 20;

// call with progress(0, 0)
static int progress(int x, int y)
{
    int i = 0;

    if (x < gridSize)
        i += progress(x + 1, y);
    if (y < gridSize)
        i += progress(x, y + 1);

    if (x == gridSize && y == gridSize)
        return 1;

    return i;
}

我确认它适用于较小的网格,如2×2或3×3,然后将其设置为运行20×20网格.想象一下,当5小时之后,程序仍然愉快地处理数字,并且只完成了大约80%(基于检查其在网格中的当前位置/路线),这让我感到惊讶.

显然,我正在以错误的方式解决这个问题.你会如何解决这个问题？我认为它应该使用方程而不是像我的方法来解决,但不幸的是,这不是我的强项.

更新:

我现在有一个工作版本.基本上它缓存了在仍然需要遍历×m块之前获得的结果.以下是代码以及一些注释:

// the size of our grid
static int gridSize = 20;

// the amount of paths available for a "NxM" block, e.g. "2x2" => 4
static Dictionary<string, long> pathsByBlock = new Dictionary<string, long>();

// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
    return (gridSize - x) * (gridSize - y);
}

// call using progress (0, 0)
static long progress(long x, long y)
{
    // first calculate the surface of the block remaining
    long surface = calcsurface(x, y);
    long i = 0;

    // zero surface means only 1 path remains
    // (we either go only right, or only down)
    if (surface == 0)
        return 1;

    // create a textual representation of the remaining
    // block, for use in the dictionary
    string block = (gridSize - x) + "x" + (gridSize - y);

    // if a same block has not been processed before
    if (!pathsByBlock.ContainsKey(block))
    {
        // calculate it in the right direction
        if (x < gridSize)
            i += progress(x + 1, y);
        // and in the down direction
        if (y < gridSize)
            i += progress(x, y + 1);

        // and cache the result!
        pathsByBlock[block] = i;
    }

    // self-explanatory :)
    return pathsByBlock[block];
}

调用20次,对于尺寸为1×1到20×20的网格,产生以下输出:

There are 2 paths in a 1 sized grid
0,0110006 seconds

There are 6 paths in a 2 sized grid
0,0030002 seconds

There are 20 paths in a 3 sized grid
0 seconds

There are 70 paths in a 4 sized grid
0 seconds

There are 252 paths in a 5 sized grid
0 seconds

There are 924 paths in a 6 sized grid
0 seconds

There are 3432 paths in a 7 sized grid
0 seconds

There are 12870 paths in a 8 sized grid
0,001 seconds

There are 48620 paths in a 9 sized grid
0,0010001 seconds

There are 184756 paths in a 10 sized grid
0,001 seconds

There are 705432 paths in a 11 sized grid
0 seconds

There are 2704156 paths in a 12 sized grid
0 seconds

There are 10400600 paths in a 13 sized grid
0,001 seconds

There are 40116600 paths in a 14 sized grid
0 seconds

There are 155117520 paths in a 15 sized grid
0 seconds

There are 601080390 paths in a 16 sized grid
0,0010001 seconds

There are 2333606220 paths in a 17 sized grid
0,001 seconds

There are 9075135300 paths in a 18 sized grid
0,001 seconds

There are 35345263800 paths in a 19 sized grid
0,001 seconds

There are 137846528820 paths in a 20 sized grid
0,0010001 seconds

0,0390022 seconds in total

我接受了danben的回答,因为他帮助我找到了这个解决方案.但也对Tim Goodman和Agos赞成:)

奖金更新:

在阅读了Eric Lippert的回答之后,我又看了一眼并重写了一下.基本的想法仍然是相同的,但缓存部分已被取出并放入一个单独的功能,如Eric的例子.结果是一些更优雅的代码.

// the size of our grid
const int gridSize = 20;

// magic.
static Func<A1, A2, R> Memoize<A1, A2, R>(this Func<A1, A2, R> f)
{
    // Return a function which is f with caching.
    var dictionary = new Dictionary<string, R>();
    return (A1 a1, A2 a2) =>
    {
        R r;
        string key = a1 + "x" + a2;
        if (!dictionary.TryGetValue(key, out r))
        {
            // not in cache yet
            r = f(a1, a2);
            dictionary.Add(key, r);
        }
        return r;
    };
}

// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
    return (gridSize - x) * (gridSize - y);
}

// call using progress (0, 0)
static Func<long, long, long> progress = ((Func<long, long, long>)((long x, long y) =>
{
    // first calculate the surface of the block remaining
    long surface = calcsurface(x, y);
    long i = 0;

    // zero surface means only 1 path remains
    // (we either go only right, or only down)
    if (surface == 0)
        return 1;

    // calculate it in the right direction
    if (x < gridSize)
        i += progress(x + 1, y);
    // and in the down direction
    if (y < gridSize)
        i += progress(x, y + 1);

    // self-explanatory :)
    return i;
})).Memoize();

顺便说一句,我想不出更好的方法来使用这两个参数作为字典的关键.我用Google搜索了一下,看来这是一个常见的解决方案.那好吧.

Answer 1

快速无编程解决方案(基于组合学)

我认为它"没有回溯"意味着我们总是增加x或增加y.

如果是这样,我们知道总共我们将有40个步骤来达到终点 - x增加20,y增加20.

唯一的问题是40个中的哪个是x的20个增加.问题相当于:有多少种不同的方法可以从一组40个元素中选择20个元素.(元素是:步骤1,步骤2等,我们选择,例如,增加x的那些).

有一个公式:它是二项式系数,顶部为40,底部为20.40!/((20!)(40-20)!)换句话说,公式是40!/(20!)^2.这里!代表阶乘.(例如5! = 5*4*3*2*1)

取消20个中的一个!和40!的一部分,这变成:(40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/(20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1).因此问题简化为简单的算术.答案是137,846,528,820.

为了比较,请注意(4*3)/(2*1)从他们的例子给出答案,6.

Answer 2

如果使用动态编程(存储子问题的结果而不是重新计算它们),这可以更快地完成.动态规划可以应用于表现出最佳子结构的问题 - 这意味着可以从子问题的最优解(信用维基百科)构建最优解.

我宁愿不给出答案,但考虑到右下角的路径数量可能与相邻方块的路径数量有关.

另外 - 如果你打算用手工作,你会怎么做？

Answer 3

正如其他人所指出的那样,这个特定问题有一个离散的数学解决方案.但是假设你确实想要递归地解决它.你的性能问题是你一遍又一遍地解决同样的问题.

让我向您展示一个稍微高阶的编程技巧,它将带来巨大的回报.让我们来看一个更简单的递归问题:

long Fib(n) 
{
    if (n < 2) return 1;
    return Fib(n-1) + Fib(n-2);
}

你要求它计算Fib(5).这计算Fib(4)和Fib(3).计算Fib(4)计算Fib(3)和Fib(2).计算Fib(3)计算Fib(2)和Fib(1).计算Fib(2)计算Fib(1)和Fib(0).现在我们回去(2)计算蛋白原再次.然后我们回去(3)计算蛋白原再次.大量的重新计算.

假设我们缓存了计算结果.然后第二次请求计算,我们只返回缓存的结果.现在是高阶技巧.我想把这个"缓存函数结果"的概念表示为一个函数,它接受一个函数,并返回一个具有这个不错属性的函数.我会把它写成函数的扩展方法:

static Func<A, R> Memoize(this Func<A, R> f)
{
    // Return a function which is f with caching.
    var dictionary = new Dictionary<A, R>();
    return (A a)=>
    {
        R r;
        if(!dictionary.TryGetValue(a, out r))
        { // cache miss
            r = f(a);
            dictionary.Add(a, r);
        }
        return r;
    };
}

现在我们对Fib进行一些小的重写:

Func<long, long> Fib = null;
Fib = (long n) => 
{
    if (n < 2) return 1;
    return Fib(n-1) + Fib(n-2);
};

好的,我们有非记忆功能.现在,魔术:

Fib = Fib.Memoize();

当我们称之为Fib(5)时,现在我们进行字典查找.5不在字典中,所以我们调用原始函数.这称为Fib(4),它执行另一个字典查找和未命中.这称为Fib(3),依此类推.当我们第二次回到调用Fib(2)和Fib(3)时,结果已经在字典中,所以我们不重新计算它们.

编写两个参数版本:

static Func<A1, A2, R> Memoize(this Func<A1, A2, R>) { ... }

并不是太难,而是留作练习.如果你这样做,那么你可以采用原始漂亮的递归逻辑,对lambda进行简单的重写,然后说:

progress = progress.Memoize();

并且突然你的性能会提高,同时不会损失原始算法的可读性.

Answer 4

虽然动态编程肯定是解决此类问题的正确方法,但这个特定实例显示了可以被利用的规律性.

您可以将问题看作是安排一些"正确"和"向下"的问题,谨慎不要计算多次相同的安排.
例如,2号问题的解决方案(在问题中的图像中报告)可以这样看:

????  
????
????
????
????
????

因此,对于n侧的任何网格,您可以通过组合学找到解决方案:

from math import factorial
n = 20
print factorial(2*n)/(factorial(n)*factorial(n))

2N!是安排的数量20→+ 20↓,而两个n!说明可以安排→和↓的相同方式.

Answer 5

顺便说一句,你可以通过实现2x3将具有相同数量的路径作为3x2来进一步提高性能.您的记忆功能似乎只考虑一个完全列x行的字符串.但是,您可以在记忆中包含2x3键和3x2键的总路径.

因此,当你记住4x2等时,它会自动用相同数量的路径填充2x4.这将缩短您的时间,因为您之前已经计算过该表面区域的所有路径,为什么要再次这样做？