3 ms·
You're assuming that all movement must be in one of three directions, but in general, you can go in six directions -- forward or backward along the x, y, and z
by pjscott 14y ago
You're assuming that all movement must be in one of three directions, but in general, you can go in six directions -- forward or backward along the x, y, and z axes. Your cubic-time DP algorithm doesn't solve the self-avoiding walk problem, which I think is what jsolson vagely recalls.
http://en.wikipedia.org/wiki/Self-avoiding_walk http://en.wikipedia.org/wiki/Self-avoiding_walk
- jsolson 14y agoSo, the professor in question was Dana Randall. I believe she was talking about this topic: http://en.scientificcommons.org/42983059 http://en.scientificcommons.org/42983059 Basically, yes, self-avoiding paths. This was basically a brief aside in her honors undergrad algorithms course, so the topic was a bit beyond what I was prepared for at the time :)
- Someone 14y agoI wasn't assuming, I was following what the OP wrote: "by going only up or right one point with each move (that is, each move is either (0,1) or (1,0)))" for 3D. Counting self-avoiding walks is hard in 2D, too (http://oeis.org/A007764 http://oeis.org/A007764)