在自定义的二叉搜索树中找到最短路径。

Question

在自定义的二叉搜索树中找到最短路径。

javaalgorithmrecursionbinary-search-treegraph-theory

6

这是一道编程竞赛中的问题

原问题可以在此找到 http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-PO-Question-Paper.pdf 第五题

穿过教室的最短路径 [由Hulsbos High的Alan Smithee撰写]

教室里挤满了排成一行的椅子，但每排中都缺少两张椅子。每排椅子从1到100编号。编写一个程序，计算从前到后的最短路径长度。每个椅子的宽度为1单位，每排深度为1单位（从椅子前面到后面的椅子前面）。不可能对角行走。你可以从第一排前面的任何间隙开始并结束于最后一排后面的任何间隙之间。您总是通过间隙的中心行走。下图显示了穿过教室的最短路径，共有五排椅子，而图示教室的宽度只有10个椅子，而非100个。输入的第一个数字将包含数字n-行数。接下来的n行将有两个数字，由空格分隔，表示间隙的位置。例如：输入： 5 3 6 2 8 4 5 7 8 3 10

我认为我有一个有效的算法可以解决这个问题，但我不确定如何在Java中实现它。

我的想法是将每个选择分解成一个搜索树，例如，如果用户的输入为：

行数：3

间隙: 4 7 2 9 8 11

生成2棵搜索树：

              4                               7            
       2           9                     2           9
     8   11      8   11             8      11     8      11

然后找到每个节点之间差异最小的路径。因此，在第二棵树中，最短路径是7->9->8，总距离为5（||7-9|-8|）。那么我的问题是：

在给定的问题中是否可接受该算法？
我应该如何使用Java实现这个算法或另一个算法？

例如，以以下示例为例（0表示空格）。

Row6: 0 2 3 4 5 6 0 8 9

Row5: 0 2 3 4 5 6 0 8 9

Row4: 1 2 3 0 5 6 0 8 9

Row3: 1 2 3 0 5 6 0 8 9

Row2: 1 2 3 0 5 6 0 8 9

Row1: 1 2 3 0 5 6 0 8 9

我从您的算法中了解到它逐个查看每一行。因此，通过1-4行，每个空格与下一行之间的距离相等，但是当您到达第5行时，如果您沿着所有缺少4的路径走，与沿着所有缺少7的路径走相比，需要更长的时间，您的解决方案是否考虑到了这一点？

- Tamir Shklaz

实际上，你所举的例子答案是6，而不是5。（7到9=2）+（9到8=1）+3行=6。 - Juan Lopes

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juan Lopes · Accepted Answer

你描述的算法不可行，因为最多只能有100行，所以如果每一行中树中节点数量翻倍，最坏情况下，你将拥有2^101个节点。

可以通过简单的动态规划来解决这个问题，在每一步中，你需要选择第一个和第二个间隔之间的最小值。

T(0, j) = 1
T(i, j) = 1+min(
              abs(pos(i, j)-pos(i-1, 0)) + T(i-1, 0),
              abs(pos(i, j)-pos(i-1, 1)) + T(i-1, 1))

当 i 是第 i 行，j 要么是 0 要么是 1，表示我们在上一轮选择的间隙。以下是一些示例 Java 实现：

import static java.lang.Math.abs;
import static java.lang.Math.min;

public class Main {
    public static int solve(int[][] P) {
        int a = 1, b = 1;
        for (int i = 1; i < P.length; i++) {
            int na = 1 + min(
                    abs(P[i][0] - P[i - 1][0]) + a,
                    abs(P[i][0] - P[i - 1][1]) + b);

            int nb = 1 + min(
                    abs(P[i][1] - P[i - 1][0]) + a,
                    abs(P[i][1] - P[i - 1][1]) + b);

            a = na;
            b = nb;
        }
        return min(a, b);
    }

    public static void main(String... args) {
        System.out.println(solve(new int[][]{
                {3, 6},
                {2, 8},
                {4, 5},
                {7, 8},
                {3, 10},
        }));


        System.out.println(solve(new int[][]{
                {4, 7},
                {2, 9},
                {8, 11}
        }));
    }
}