如何记忆长度为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路径所需的时间减少了很多。像次秒。
希望这个例子可以帮助那些最终难倒的人。
最新问题
- 如何修改JavaFX中的ChoiceBox复选标记？
- 在pygame中实时播放带有alpha通道和同步音频的两个混合视频？
- 如何在cypher-shell中使用环境变量NEO4J_PASSWORD
- ASP Classic IPN 侦听器可以工作，但现在不行了
- 如何实际使用 cv2.estimateAffine3D 在 python 中对齐 3d 点？
- 如何在 R 中生成具有跨多个组的 FDR 校正 P 值的分层汇总表
- 我无法使用 Exact Alarm 进行颤振本地通知
- Azure OpenAI Studio Playground：在向任何函数提交输出时，我的助手总是返回未定义的错误
- 如何对Bull.js与Redis服务器的连接实现完整而非部分的TLS保护？
- Nuget 资源从 https 更改为 http
- 不同值时如何在同一行返回结果
- 我可以将 boost::intrusive::rbtree 与 stateful_value_traits 一起使用吗？
- 确定next.js中的客户端/服务器组件
- 按照Ieee-754单精度格式实现浮点加法器但移位错误
- 如何在Python中通过OR-Tools使用sorted()和min()函数？
- 来自 openai python SDK 的 AsyncAzureOpenAI 客户端支持自定义快速 API 端点
- 如果我想使用过去/未来数百万年的日期和时间，我该怎么做？
- 使用 docker-compose 进行 LangGraph 部署
- 如何使用 WebDriver Sampler (JMeter) 中的 JMeter 属性 props.get props.put
- 从 winit 获取 windows-rs HWND？
© www.soinside.com 2019 - 2024. All rights reserved.