我有一个树(代表一个SalesPath),每个节点都有一个代价。
对象是计算最小的SalesPath,即每个节点从根节点到叶节点的成本之和。
下面的代码使用递归来解决这个问题,代码工作得很好(SalesPath (0-3-2-1-1)在树中有最便宜的路径=7)。
我在可视化堆栈、阐明/解释Recursion如何能够跟踪多个分支之间最便宜的成本(即int便宜= cheapestCost + rootNode.cost)时遇到了困难
例如:从0-5- 4,最便宜的成本是9;从0-3 -2 -1 -1,最便宜的成本是7。
有谁能对此提供简单的解释?

代码:
static class SalesPathRecursion{
static int getCheapestCost_Recursion(Node rootNode){
int cheapestCost = Integer.MAX_VALUE;
Node[] children = rootNode.children;
int tempCost =0;
if(children == null){
System.out.println(" Children == null, returning rootNode.cost => " + rootNode.cost);
return rootNode.cost;
}else{
for(int i=0; i< children.length; i++){
tempCost = getCheapestCost_Recursion(children[i]);
if(tempCost < cheapestCost){
cheapestCost = tempCost;
}
System.out.println(" CheapestCost is " + cheapestCost);
}
}
int cheapest = cheapestCost + rootNode.cost;
System.out.println(" Returning : rootNode.cost => " + rootNode.cost + " cheapest is => " + cheapest);
return cheapest;
}
}发布于 2019-01-07 02:03:52
这是一个典型的递归示例!
调用者调用递归函数,传入根节点并询问“叶的最低成本是什么?”呼叫树底部的根节点(0)回答说:“我还不确定。请稍等,让我的每个子节点看看哪一个的成本最低”。然而,没有一个孩子对这个问题有答案,所以他们问每个孩子完全相同的问题,以此类推。
最后,到达一个叶节 (例如,从您的例子中,4 )并说:“我知道!从我到一个叶节点的最便宜的成本是我自己的值,4!我要告诉我的父母。”这叫做基箱。到目前为止,基本情况是第一个函数调用,它提供了对一个非常小的子问题的明确答案,从这个子问题中获得的信息将用于构建更大问题的解决方案。将大到不能立即解决的问题分解成小的、容易解决的问题的过程称为分治。
节点4的父节点节点5现在知道从自身到叶(4,它的独生子)最便宜的成本是5 + 4 = 9,并告诉它的父节点根节点0。根节点现在从其最左边的子节点获得了一个确定的值(根到叶路径的成本9比无穷大便宜,因此它被存储为迄今为止最好的),但仍然需要向它的其他子节点询问它们的成本,它是这样做的。最终,所有的孩子都会报告他们各自的成本,而0->3->2->1->1证明是最便宜的。
该算法使用深度优先搜索,对一个分支进行完全的挖掘,然后再对其它分支进行挖掘。换句话说,0->5->4是在0->3->2->1->1之前被完全研究过的。
示例1
考虑一个具有独特成本的节点示例树:
0
/ \
4 1
/
5 我们期望0->1是成本为1的最便宜的路径。让我们在这棵树上使用冗长的会话输出来运行算法。每当进行递归调用时,打印都会缩进。括号指的是特定的节点。看看是否可以跟踪执行:
(0), what's your min cost?
(0) says: Hang on, I need to ask my children...
(0) says: I'm asking (4) for its min cost...
(4), what's your min cost?
(4) says: Hang on, I need to ask my children...
(4) says: I'm asking (5) for its min cost...
(5), what's your min cost?
(5) says: I'm a leaf! My min cost is 5
(4) says: I got the cost 5 from (5), a new best!
(4) says: I checked my children and I know my min cost is 9
(0) says: I got the cost 9 from (4), a new best!
(0) says: I'm asking (1) for its min cost...
(1), what's your min cost?
(1) says: I'm a leaf! My min cost is 1
(0) says: I got the cost 1 from (1), a new best!
(0) says: I checked my children and I know my min cost is 1示例2
下面是另一棵更大的树,同样具有唯一的节点:
0
/ | \
4 1 7
/ / \
5 6 2
\
3我们期望0->1->2->3是成本为6的最便宜的路径。让我们看看详细的输出。再试一次跟踪执行情况。
(0), what's your min cost?
(0) says: Hang on, I need to ask my children...
(0) says: I'm asking (4) for its min cost...
(4), what's your min cost?
(4) says: Hang on, I need to ask my children...
(4) says: I'm asking (5) for its min cost...
(5), what's your min cost?
(5) says: I'm a leaf! My min cost is 5
(4) says: I got the cost 5 from (5), a new best!
(4) says: I checked my children and I know my min cost is 9
(0) says: I got the cost 9 from (4), a new best!
(0) says: I'm asking (1) for its min cost...
(1), what's your min cost?
(1) says: Hang on, I need to ask my children...
(1) says: I'm asking (6) for its min cost...
(6), what's your min cost?
(6) says: I'm a leaf! My min cost is 6
(1) says: I got the cost 6 from (6), a new best!
(1) says: I'm asking (2) for its min cost...
(2), what's your min cost?
(2) says: Hang on, I need to ask my children...
(2) says: I'm asking (3) for its min cost...
(3), what's your min cost?
(3) says: I'm a leaf! My min cost is 3
(2) says: I got the cost 3 from (3), a new best!
(2) says: I checked my children and I know my min cost is 5
(1) says: I got the cost 5 from (2), a new best!
(1) says: I checked my children and I know my min cost is 6
(0) says: I got the cost 6 from (1), a new best!
(0) says: I'm asking (7) for its min cost...
(7), what's your min cost?
(7) says: I'm a leaf! My min cost is 7
(0) says: I got the cost 7 from (7) but it's not the best
(0) says: I checked my children and I know my min cost is 6下面是生成上述输出的代码:
static void say(String message, int depth) {
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
System.out.println(message);
}
static int getCheapestCostRecursion(Node node, int depth) {
say("(" + node.cost + "), what's your min cost?", depth);
if (node.children.length == 0) {
say(
"(" + node.cost +
") says: I'm a leaf! My min cost is " +
node.cost, depth
);
return node.cost;
}
say(
"(" + node.cost +
") says: Hang on, I need to ask my children...",
depth
);
int cheapestCost = Integer.MAX_VALUE;
for (Node child : node.children) {
say(
"(" + node.cost +
") says: I'm asking (" + child.cost +
") for its min cost...", depth
);
int childCost = getCheapestCostRecursion(child, depth + 6);
say(
"(" + node.cost +
") says: I got the cost " + childCost +
" from (" + child.cost + ")", depth
);
if (childCost < cheapestCost) {
say(
"(" + node.cost +
") says: I got the cost " + childCost +
" from (" + child.cost + "), a new best",
depth
);
cheapestCost = childCost;
}
else {
say(
"(" + node.cost +
") says: I got the cost " + childCost +
" from (" + child.cost +
"), but it's not the best", depth
);
}
}
say(
"(" + node.cost +
") says: I checked my children and I know " +
"my min cost is " + (cheapestCost + node.cost),
depth
);
return cheapestCost + node.cost;
}https://stackoverflow.com/questions/54066212
复制相似问题