问一道算法题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道算法题

问一道算法题# JobHunting - 待字闺中

u*e2011-02-09 08:02

1 楼

给定1个M*N的矩阵，矩阵由0,1,2,3构成，其中0表示尚未访问到的点，1表示不可访问的
点，仅有一组2,3分别表示起点和终点，2到3的路径指从2只沿水平或竖直方向访问所有
0点并最终到达3点。求给定矩阵的可能路径数。
递归和用队列的方式我想到了，这两个原理是一样的，有什么其他思路么？

f*42011-02-09 08:02

2 楼

记得这东西有个iphone游戏的。。。
有不能经过已经访问过的0点的限制吗？

g*s2011-02-09 08:02

3 楼

not clear about the description.
0 refers to "not visited yet" while 1 "inaccessible", then how to
represent "visited"?
also, is the path simple but allow detour?

问的

【在 u******e 的大作中提到】

: 给定1个M*N的矩阵，矩阵由0,1,2,3构成，其中0表示尚未访问到的点，1表示不可访问的
: 点，仅有一组2,3分别表示起点和终点，2到3的路径指从2只沿水平或竖直方向访问所有
: 0点并最终到达3点。求给定矩阵的可能路径数。
: 递归和用队列的方式我想到了，这两个原理是一样的，有什么其他思路么？

u*e2011-02-09 08:02

4 楼

有，不然就无限了么～～

【在 f*******4 的大作中提到】

: 记得这东西有个iphone游戏的。。。
: 有不能经过已经访问过的0点的限制吗？

g*s2011-02-09 08:02

5 楼

then this is hamiltonian path problem, npc.

【在 u******e 的大作中提到】

: 有，不然就无限了么～～

u*e2011-02-09 08:02

6 楼

actully you can represent it as 1 after you visit
but it's not so important cause the only result is how many different ways.

【在 g*********s 的大作中提到】

: not clear about the description.
: 0 refers to "not visited yet" while 1 "inaccessible", then how to
: represent "visited"?
: also, is the path simple but allow detour?
:
: 问的

u*e2011-02-09 08:02

7 楼

不能完全这么说
hamilton path的话规定每个点的度应该大于n/2，事实上这里每个点的度最大也就4，
大多数情况下v数是大于8的

【在 g*********s 的大作中提到】

: then this is hamiltonian path problem, npc.

i*e2011-02-09 08:02

8 楼

你说的是这题吧？
http://www.quora.com/challenges
我想到的主要思路就是 DFS.
我觉得这问题主要的挑战就是怎么把 DFS 的 exponential 复杂度利用聪明的剪枝方法
大大的降下来。如果你画几个简单的图，你会发现 DFS 有很多可以剪枝优化的机会，
但是要怎么想到一个有效率的算法来涵盖这所有情况还是比较复杂的.
不知道你的思路是什么？也讨论一下吧。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

g*s2011-02-09 08:02

9 楼

thx for sharing. is this a good/promising startup?

【在 i**********e 的大作中提到】

: 你说的是这题吧？
: http://www.quora.com/challenges
: 我想到的主要思路就是 DFS.
: 我觉得这问题主要的挑战就是怎么把 DFS 的 exponential 复杂度利用聪明的剪枝方法
: 大大的降下来。如果你画几个简单的图，你会发现 DFS 有很多可以剪枝优化的机会，
: 但是要怎么想到一个有效率的算法来涵盖这所有情况还是比较复杂的.
: 不知道你的思路是什么？也讨论一下吧。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2011-02-09 08:02

10 楼

Hoho... That I don't know.
But just have a look at their team.
http://www.quora.com/about/team
And I don't belong to any of their attended schools :)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 g*********s 的大作中提到】

: thx for sharing. is this a good/promising startup?

I*d2011-02-09 08:02

11 楼

是（M+N-2）!/(（M-1）!*（N-1）!) 吗？

j*x2011-02-09 08:02

12 楼

eliminate all paths crossing “1” points from all possible paths connecting
2 and 3

i*e2011-02-09 08:02

13 楼

如果是单纯 DFS 的话，复杂度应该是 O(4^(M*N)).
因为每一步有四个选择，递归最深可以有 M*N （因为总共有 M*N 个节点).
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 I******d 的大作中提到】

: 是（M+N-2）!/(（M-1）!*（N-1）!) 吗？

g*s2011-02-09 08:02

14 楼

looks like another teenage facebook...

【在 i**********e 的大作中提到】

: Hoho... That I don't know.
: But just have a look at their team.
: http://www.quora.com/about/team
: And I don't belong to any of their attended schools :)
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2011-02-09 08:02

15 楼

不可能用那么简单的数学公式就算出来了吧。
不要忘了有些地方是不能走的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 I******d 的大作中提到】

: 是（M+N-2）!/(（M-1）!*（N-1）!) 吗？

u*e2011-02-09 08:02

16 楼

dfs的我写出来了，8*8几乎要数天才能完成了
能提高到60s内完成8*8么？

【在 i**********e 的大作中提到】

g*s2011-02-09 08:02

17 楼

it requires to access every 0-node.

connecting

【在 j********x 的大作中提到】

: eliminate all paths crossing “1” points from all possible paths connecting
: 2 and 3

u*e2011-02-09 08:02

18 楼

每个0都要走到

connecting

【在 j********x 的大作中提到】

: eliminate all paths crossing “1” points from all possible paths connecting
: 2 and 3

i*e2011-02-09 08:02

19 楼

你确定数天你的程序就能完成执行吗？
4^(8*8) = 3.4 × 10^38
这给你活多一百岁来等待都没用.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 u******e 的大作中提到】

: dfs的我写出来了，8*8几乎要数天才能完成了
: 能提高到60s内完成8*8么？

u*e2011-02-09 08:02

20 楼

额，总之数量级高到不可完成，所以简单DFS不是可接受的答案
那有啥建议呢？
是从数学角度优化还是代码角度优化？

【在 i**********e 的大作中提到】

: 你确定数天你的程序就能完成执行吗？
: 4^(8*8) = 3.4 × 10^38
: 这给你活多一百岁来等待都没用.
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

u*e2011-02-09 08:02

21 楼

这个公式是怎么得出来的？

【在 I******d 的大作中提到】

: 是（M+N-2）!/(（M-1）!*（N-1）!) 吗？

i*e2011-02-09 08:02

22 楼

我觉得这题纯粹是代码角度来优化。
你多画几个图吧，然后看看怎么剪枝来优化。
这是我唯一想到的优化方法，应该还有其他优化方法的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

u*e2011-02-09 08:02

23 楼

谢谢，我想想看，感觉挺难的-_-

【在 i**********e 的大作中提到】

: 我觉得这题纯粹是代码角度来优化。
: 你多画几个图吧，然后看看怎么剪枝来优化。
: 这是我唯一想到的优化方法，应该还有其他优化方法的。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

x*y2011-02-09 08:02

24 楼

See section B in http://code.google.com/codejam/contest/dashboard?c=32001#s=a&a=3.
This technique can be used here to avoid dupilcate calculation of same part.

问的

【在 u******e 的大作中提到】

I*d2011-02-09 08:02

25 楼

哦，对不起，我的答案不对。
我给的答案针对的是，M*N的矩阵从0,0走到M,N最短路线的走法。

【在 u******e 的大作中提到】

: 这个公式是怎么得出来的？