如何记忆长度为n的搜索的递归路径
问题描述 投票：6回答：2
第一次发帖认为我会尝试这个社区。
我研究了几个小时，我似乎无法找到一个足够近的例子来获取想法。我不关心语言答案是什么，但更喜欢java，c / c ++或伪代码。
我希望在网格中找到长度为n的连续路径。
我找到了一个递归的解决方案，我认为它很干净并且始终有效，但如果路径数量太大，则运行时很差。我意识到我可以迭代地实现它，但我想首先找到一个递归解决方案。
我不在乎语言答案是什么，但更喜欢java，c / c ++。
问题是这个 - 对于String []和int pathLength那个长度有多少路径。
长度为3的{“ABC”，“CBZ”，“CZC”，“BZZ”，“ZAA”}
这是从下面开始的第3和第7条路径。
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)
返回7条长度为3的可能路径（A-B-C）
这是最初的递归解决方案
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个递归，因此复杂性会急剧上升。
我决定使用memoization来提高性能。
这就是我提出的。
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
}
}
}
问题是我的记忆永远不会被真正使用。递归调用有点模仿深度优先搜索。 EX-
1
/ | \
2 5 8
/\ |\ |\
3 4 6 7 9 10
因此，保存运行不会与任何性能保存方式中的另一次运行重叠，因为它在返回调用堆栈之前在树的底部进行搜索。所以问题是......我怎么记住这个？或者一旦我得到一个完整的运行如何我回到树的开头，所以我写的记忆工作。
真正杀死性能的测试字符串是{“ABCDEFGHIJKLMNOPQRSTUVWXYZ”，“ABCDEFGHIJKLMNOPQRSTUVWXYZ”，“ABCDEFGHIJKLMNOPQRSTUVWXYZ”};对于长度为26的所有路径（应返回1000000000）
PS。作为第一次海报，任何关于一般代码改进或不良编码习惯的评论都将受到赞赏。此外，因为我没有发布之前让我知道这个问题是不清楚或格式不佳或太长等。
2个回答
1
投票
投票
我不确定你的备忘录（也许你可以用文字解释它？）但这里似乎有重叠的子问题。如果我理解正确，除了“A”之外，任何特定的字母实例只能从字母表中相邻的前一个字母到达。这意味着我们可以存储来自每个特定字母实例的路径数。当在后续场合达到该特定实例时，我们可以避免重复进入它。
深度优先搜索：
d1 d2 d3 d4
c1 c2
b
a1 a2
.....f(c1) = f(d1) + f(d2) = 2
.....f(c2) = f(d3) + f(d4) = 2
...f(b) = f(c1) + f(c2) = 4
f(a1) = f(b) = 4
f(a2) = f(b) = 4
0
投票
投票
好吧我明白了！部分归功于@גלעדברקן的推荐。我本来只是试图让它工作，说任何两条路径都有任何相同的索引然后它是一个完整的路径，所以我们不得不进一步递减这是一个粗略的过度简化。我最后写了一个小图形可视化器，这样我就能看到我正在看的东西。 （这是上面的第一个例子（{“ABC”，“CBZ”，“CZC”，“BZZ”，“ZAA”}长度为3））
L代表层 - 每层对应一个字母，即第1层=='A'
由此我确定每个节点可以保存从中获得的已完成路径的数量。在图片中，这意味着节点L [2] X1Y1将被赋予数字4，因为任何时候到达该节点有4个完整路径。
无论如何，我记得进入了一个int [] []所以我想从这里做的唯一事情就是制作一个hashmap，这样就不会浪费太多空间。
这是我想出的代码。
package practiceproblems;
import java.util.ArrayDeque;
public class AlphabetCount {
private int ofLength;
private int paths = 0;
private String[] grid;
//this is the array that we memoize. could be hashmap
private int[][] memoArray;// spec says it initalizes to zero so i am just going with it
//entry point func
public int count(String[] grid, int ofLength) {
//initialize all the member vars
memoArray = new int[grid[0].length()][grid.length];
this.grid = grid;
// this is minus 1 because we already found "A"
this.ofLength = ofLength - 1;
paths = 0;
//saves the previous nodes visited.
ArrayDeque<int[]> goodPathStack = new ArrayDeque<int[]>();
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)) {
//kinda wasteful to clone i would think... but easier because it stays in its stack frame
recursiveFind(goodPathStack.clone(), 0, index, j);
}
}
System.out.println(System.currentTimeMillis() - startTime);
//if we have more than a bil then just return a bil
return paths >= 1_000_000_000 ? 1_000_000_000 : paths;
}
//recursive func
private void recursiveFind(ArrayDeque<int[]> fullPath, int layer, int x, int y) {
//debugging
System.out.println("Preorder " + layer + " " + (x) + " " + (y));
//start pushing onto the path stack so that we know where we have been in a given recursion
int[] pair = { x, y };
fullPath.push(pair);
if (paths >= 1_000_000_000) {
return;
//we found a full path 'A' thru length
} else if (layer == this.ofLength) {
paths++;
//poll is just pop for deques apparently.
// all of these paths start at 'A' which we find manually. so pop last.
// all of these paths incluse the last letter which wouldnt help us because if
// we find the last letter we already know we are at the end.
fullPath.pollFirst();
fullPath.pollLast();
//this is where we save memoization info
//each node on fullPath leads to a full path
for (int[] p : fullPath) {
memoArray[p[0]][p[1]]++;
}
return;
} else if (memoArray[x][y] > 0) {
//this is us using our memoization cache
paths += memoArray[x][y];
fullPath.pollLast();
fullPath.pollFirst();
for (int[] p : fullPath) {
memoArray[p[0]][p[1]] += memoArray[x][y];
}
}
// 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;
//search in all 8 directions for a letter that comes after the one that you are on.
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(fullPath.clone(), layer + 1, x + dx, y + dy);
}
}
}
}
}
}
// memoStack.putIfAbsent(key, newPaths);
// memo thought! if one runs layer, x and y are the same then you can use a
// previous run
}
}
有用！并且完成1_000_000_000路径所需的时间减少了很多。像次秒。
希望这个例子可以帮助那些最终难倒的人。
最新问题
- 图像在不应该被压缩的时候被压缩了
- Apple M2，~/.gitconfig 文件在运行源 ~/.gitconfig 时失败
- 为什么在JSP中点击提交按钮没有任何反应？
- 具有固定纵横比的 Matplotlib 颜色条
- kotlin，如何从函数返回类类型
- Visual Studio 代码“窗口意外终止（原因：‘崩溃’，代码：‘-2147483645’）”
- 如何在 python 3.7 和 Windows 10 上使用 matplotlib 绘制 .kml 文件中的数据？
- 如何用单个元素构成数组类型的限定表达式？
- 如果数据存在于另一个表中，则使用 Y 或 N 更新列
- 在 Spring 中处理 @GetMapping("") 的可选参数未通过 RestAssured 测试
- AWS CodePipeline 在部署前不提取工件
- apex 未安装
- 如何查看通过云功能发送的 Firebase Cloud Messaging 通知？
- 在 Spring 中处理 @GetMapping("") 的可选参数
- 我可以在导航到新页面并等待该页面完成加载后运行函数吗？
- 使列宽占据wxPython ListCtrl中的可用空间
- Terraform“azurerm_app_service_certificate”失败，退出代码“59716”
- Chrome 更新后不再可以通过 WebRTC 禁用私有 IP 匿名化？
- 在 Kotlin 中使用 Google 的生成式 AI 生成图像
- 如何使用 Android Kotlin 获取 Twitch 频道的实时状态？ [已关闭]
© www.soinside.com 2019 - 2024. All rights reserved.