如何记住长度为n的搜索的递归路径
Zac*_*lov 6 java algorithm recursion search memoization
第一次发布时以为我会尝试这个社区的。
我已经研究了几个小时，但我似乎找不到足够接近的例子来提出想法。我不在乎什么语言的答案，但更喜欢java，c / c ++或伪代码。
我正在寻找网格中长度为n的连续路径。
我找到了一个递归解决方案，我认为它是干净的并且始终可以工作，但是如果路径数量太大，则运行时效果很差。我意识到我可以迭代实现，但是我想先找到一个递归解决方案。
我不在乎什么语言的答案，但更喜欢java，c / c ++。
问题是这样的-对于String []和int pathLength，该长度有多少条路径。
{长度3的{“ ABC”，“ CBZ”，“ CZC”，“ BZZ”，“ ZAA”}
这是下面的第三和第七条路径。
A B C A . C A B . A . . A . . A . . . . .
. . . . B . C . . C B . . B . . B . . . .
. . . . . . . . . . . . C . . . . C C . .
. . . . . . . . . . . . . . . . . . B . .
. . . . . . . . . . . . . . . . . . . A .
(spaces are for clarity only)
返回长度为3（ABC）的7条可能路径
这是原始的递归解决方案
public class SimpleRecursive {
private int ofLength;
private int paths = 0;
private String[] grid;
public int count(String[] grid, int ofLength) {
this.grid = grid;
this.ofLength = ofLength;
paths = 0;
long startTime = System.currentTimeMillis();
for (int j = 0; j < grid.length; j++) {
for (int index = grid[j].indexOf('A'); index >= 0; index = grid[j].indexOf('A', index + 1)) {
recursiveFind(1, index, j);
}
}
System.out.println(System.currentTimeMillis() - startTime);
return paths;
}
private void recursiveFind(int layer, int x, int y) {
if (paths >= 1_000_000_000) {
}
else if (layer == ofLength) {
paths++;
}
else {
int xBound = grid[0].length();
int yBound = grid.length;
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (dx != 0 || dy != 0) {
if ((x + dx < xBound && y + dy < yBound) && (x + dx >= 0 && y + dy >= 0)) {
if (grid[y].charAt(x) + 1 == grid[y + dy].charAt(x + dx)) {
recursiveFind(layer + 1, x + dx, y + dy);
}
}
}
}
}
}
}
}
这非常慢，因为每个新字母都可以产生8个递归，因此复杂性迅速上升。
我决定使用备忘录来提高性能。
这就是我想出的。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class AlphabetCount {
private int ofLength;
private int paths = 0;
private String[] grid;
// This was an optimization that helped a little. It would store possible next paths
// private HashMap<Integer, ArrayList<int[]>> memoStack = new HashMap<Integer, ArrayList<int[]>>();
//hashmap of indices that are part of a complete path(memoization saves)
private HashMap<Integer, int[]> completedPath = new HashMap<Integer, int[]>();
//entry point
public int count(String[] grid, int ofLength) {
this.grid = grid;
//Since i find the starting point ('A') by brute force then i just need the next n-1 letters
this.ofLength = ofLength - 1;
//variable to hold number of completed runs
paths = 0;
//holds the path that was taken to get to current place. determined that i dont really need to memoize 'Z' hence ofLength -1 again
List<int[]> fullPath = new ArrayList<int[]>(ofLength - 1);
//just a timer to compare optimizations
long startTime = System.currentTimeMillis();
//this just loops around finding the next 'A'
for (int j = 0; j < grid.length; j++) {
for (int index = grid[j].indexOf('A'); index >= 0; index = grid[j].indexOf('A', index + 1)) {
//into recursive function. fullPath needs to be kept in this call so that it maintains state relevant to call stack? also the 0 here is technically 'B' because we already found 'A'
recursiveFind(fullPath, 0, index, j);
}
}
System.out.println(System.currentTimeMillis() - startTime);
return paths;
}
private void recursiveFind(List<int[]> fullPath, int layer, int x, int y) {
//hashing key. mimics strings tohash. should not have any duplicates to my knowledge
int key = 31 * (x) + 62 * (y) + 93 * layer;
//if there is more than 1000000000 paths then just stop counting and tell me its over 1000000000
if (paths >= 1_000_000_000) {
//this if statement never returns true unfortunately.. this is the optimization that would actually help me.
} else if (completedPath.containsKey(key)) {
paths++;
for (int i = 0; i < fullPath.size() - 1; i++) {
int mkey = 31 * fullPath.get(i)[0] + 62 * fullPath.get(i)[1] + 93 * (i);
if (!completedPath.containsKey(mkey)) {
completedPath.put(mkey, fullPath.get(i));
}
}
}
//if we have a full run then save the path we took into the memoization hashmap and then increase paths
else if (layer == ofLength) {
for (int i = 0; i < fullPath.size() - 1; i++) {
int mkey = 31 * fullPath.get(i)[0] + 62 * fullPath.get(i)[1] + 93 * (i);
if (!completedPath.containsKey(mkey)) {
completedPath.put(mkey, fullPath.get(i));
}
}
paths++;
}
//everything with memoStack is an optimization that i used that increased performance marginally.
// else if (memoStack.containsKey(key)) {
// for (int[] path : memoStack.get(key)) {
// recursiveFind(fullPath,layer + 1, path[0], path[1]);
// }
// }
else {
int xBound = grid[0].length();
int yBound = grid.length;
// ArrayList<int[]> newPaths = new ArrayList<int[]>();
int[] pair = new int[2];
//this loop checks indices adjacent in all 8 directions ignoring index you are in then checks to see if you are out of bounds then checks to see if one of those directions has the next character
for (int dx = -1; dx <= 1; ++dx) {
for (int dy = -1; dy <= 1; ++dy) {
if (dx != 0 || dy != 0) {
if ((x + dx < xBound && y + dy < yBound) && (x + dx >= 0 && y + dy >= 0)) {
if (grid[y].charAt(x) + 1 == grid[y + dy].charAt(x + dx)) {
pair[0] = x + dx;
pair[1] = y + dy;
// newPaths.add(pair.clone());
//not sure about this... i wanted to save space by not allocating everything but i needed fullPath to only have the path up to the current call
fullPath.subList(layer, fullPath.size()).clear();
//i reuse the int[] pair so it needs to be cloned
fullPath.add(pair.clone());
//recursive call
recursiveFind(fullPath, layer + 1, x + dx, y + dy);
}
}
}
}
}
// memoStack.putIfAbsent(key, newPaths);
// memo thought! if layer, x and y are the same as a successful runs then you can use a
// previous run
}
}
}
问题是我的备忘录从未真正使用过。递归调用有点像深度优先搜索。前
1
/ | \
2 5 8
/\ |\ |\
3 4 6 7 9 10
因此，保存运行将不会与任何运行以任何性能节省的方式重叠，因为它在返回调用堆栈之前先在树的底部进行搜索。所以问题是...我该如何记住？或一旦我全面运行，如何将其递归回树的开头，以便我编写的备忘录起作用。
真正影响性能的测试字符串是{“ ABCDEFGHIJKLMNOPQRSTUVWXYZ”，“ ABCDEFGHIJKLMNOPQRSTUVWXYZ”，“ ABCDEFGHIJKLMNOPQRSTUVWXYZ”}; 对于所有长度为26的路径（应返回1000000000）
PS。作为第一次发布者，将对任何有关常规代码改进或不良代码习惯的评论表示赞赏。另外，由于我还没有发布过，因此请让我知道这个问题是否不清楚，格式不正确或时间太长等。
好吧，我想通了！部分感谢@\xd7\x92\xd7\x9c\xd7\xa2\xd7\x93\xd7\x91\xd7\xa8\xd7\xa7\xd7\x9f \的推荐。我最初只是想让它工作，如果任何两条路径有任何相同的索引，那么它就是一个完整的路径，所以我们不必进一步递归，这是一个严重的过度简化。我最终编写了一个小图形可视化工具，以便我可以准确地看到我正在查看的内容。（这是上面的第一个示例（长度为 3 的 { "ABC", "CBZ", "CZC", "BZZ", "ZAA" }））
\n\nL 代表层 - 每层对应一个字母即层 1 == \'A\'
\n\n
由此我确定每个节点都可以保存从它开始的已完成路径的数量。在图中，这意味着节点 L[2]X 1 Y 1将被赋予数字 4，因为无论何时到达该节点，都有 4 条完整路径。
\n\n无论如何，我记入了一个 int[][] ，所以我唯一想做的就是将其制作为哈希图，这样就不会浪费太多空间。
\n\n这是我想出的代码。
\n\npackage practiceproblems;\n\nimport java.util.ArrayDeque;\n\n\npublic class AlphabetCount {\n\n private int ofLength;\n private int paths = 0;\n private String[] grid;\n\n //this is the array that we memoize. could be hashmap\n private int[][] memoArray;// spec says it initalizes to zero so i am just going with it\n\n //entry point func\n public int count(String[] grid, int ofLength) {\n\n //initialize all the member vars\n memoArray = new int[grid[0].length()][grid.length];\n this.grid = grid;\n // this is minus 1 because we already found "A"\n this.ofLength = ofLength - 1;\n paths = 0;\n //saves the previous nodes visited.\n ArrayDeque<int[]> goodPathStack = new ArrayDeque<int[]>();\n\n\n long startTime = System.currentTimeMillis();\n for (int j = 0; j < grid.length; j++) {\n for (int index = grid[j].indexOf(\'A\'); index >= 0; index = grid[j].indexOf(\'A\', index + 1)) {\n //kinda wasteful to clone i would think... but easier because it stays in its stack frame\n recursiveFind(goodPathStack.clone(), 0, index, j);\n\n }\n\n }\n System.out.println(System.currentTimeMillis() - startTime);\n //if we have more than a bil then just return a bil\n return paths >= 1_000_000_000 ? 1_000_000_000 : paths;\n }\n\n //recursive func\n private void recursiveFind(ArrayDeque<int[]> fullPath, int layer, int x, int y) {\n\n //debugging\n System.out.println("Preorder " + layer + " " + (x) + " " + (y));\n\n //start pushing onto the path stack so that we know where we have been in a given recursion\n int[] pair = { x, y };\n fullPath.push(pair);\n\n if (paths >= 1_000_000_000) {\n return;\n\n //we found a full path \'A\' thru length\n } else if (layer == this.ofLength) {\n\n paths++;\n //poll is just pop for deques apparently.\n // all of these paths start at \'A\' which we find manually. so pop last.\n // all of these paths incluse the last letter which wouldnt help us because if\n // we find the last letter we already know we are at the end.\n fullPath.pollFirst();\n fullPath.pollLast();\n\n //this is where we save memoization info\n //each node on fullPath leads to a full path\n for (int[] p : fullPath) {\n memoArray[p[0]][p[1]]++;\n }\n return;\n\n } else if (memoArray[x][y] > 0) {\n\n //this is us using our memoization cache\n paths += memoArray[x][y];\n fullPath.pollLast();\n fullPath.pollFirst();\n for (int[] p : fullPath) {\n memoArray[p[0]][p[1]] += memoArray[x][y];\n }\n\n }\n\n// else if (memoStack.containsKey(key)) {\n// for (int[] path : memoStack.get(key)) {\n// recursiveFind(fullPath,layer + 1, path[0], path[1]);\n// }\n// } \n\n else {\n\n int xBound = grid[0].length();\n int yBound = grid.length;\n\n //search in all 8 directions for a letter that comes after the one that you are on.\n for (int dx = -1; dx <= 1; ++dx) {\n for (int dy = -1; dy <= 1; ++dy) {\n if (dx != 0 || dy != 0) {\n if ((x + dx < xBound && y + dy < yBound) && (x + dx >= 0 && y + dy >= 0)) {\n if (grid[y].charAt(x) + 1 == grid[y + dy].charAt(x + dx)) {\n\n recursiveFind(fullPath.clone(), layer + 1, x + dx, y + dy);\n\n }\n }\n\n }\n\n }\n }\n }\n\n // memoStack.putIfAbsent(key, newPaths);\n\n // memo thought! if one runs layer, x and y are the same then you can use a\n // previous run\n\n }\n\n}\n有用！完成1_000_000_000条路径所需的时间减少了很多。就像亚秒一样。
\n\n希望这个例子可以帮助那些被困了好几天的人。
\n| 归档时间： |
|
| 查看次数： |
128 次 |
| 最近记录： |