首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >SalesPath -计算最便宜路径

问SalesPath -计算最便宜路径
EN

Stack Overflow用户
提问于 2019-01-06 21:42:24
回答 1查看 56关注 0票数 0

我有一个树(代表一个SalesPath),每个节点都有一个代价。

对象是计算最小的SalesPath,即每个节点从根节点到叶节点的成本之和。

下面的代码使用递归来解决这个问题,代码工作得很好(SalesPath (0-3-2-1-1)在树中有最便宜的路径=7)。

我在可视化堆栈、阐明/解释Recursion如何能够跟踪多个分支之间最便宜的成本(即int便宜= cheapestCost + rootNode.cost)时遇到了困难

例如:从0-5- 4,最便宜的成本是9;从0-3 -2 -1 -1,最便宜的成本是7。

有谁能对此提供简单的解释?

​

代码:

代码语言:javascript
复制
 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;
            }
        }
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 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

考虑一个具有独特成本的节点示例树:

代码语言:javascript
复制
        0
       / \
      4   1
     /  
    5  

我们期望0->1是成本为1的最便宜的路径。让我们在这棵树上使用冗长的会话输出来运行算法。每当进行递归调用时,打印都会缩进。括号指的是特定的节点。看看是否可以跟踪执行:

代码语言:javascript
复制
(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

下面是另一棵更大的树,同样具有唯一的节点:

代码语言:javascript
复制
         0
       / | \
      4  1  7
     /  / \  
    5  6   2
            \
             3

我们期望0->1->2->3是成本为6的最便宜的路径。让我们看看详细的输出。再试一次跟踪执行情况。

代码语言:javascript
复制
(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

下面是生成上述输出的代码:

代码语言:javascript
复制
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;
}

试试看!

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/54066212

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档