java - 自定义二叉搜索树中的最短路径

Question

这是一个编程竞赛的问题

原始问题可以在这里找到http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-PO-Question-Paper.pdf问题5

穿过大厅的最短路径[作者:Hulsbos 高中的 Alan Smithee]

大厅里挤满了成排的椅子，但每一排正好有两把椅子丢失的。每排的椅子都有编号从 1 到 100。编写一个程序来计算从前面到前面的最短路径的长度大厅的后面。每把椅子是 1 个单位宽，每排是 1 个单位深(从椅子的前面到椅子的前面它后面的椅子)。无法移动对角地。你可以从前面的任何差距开始前排并在最后一排的任何空隙后面结束。你总是从缝隙中间走过。图示是通过大厅的最短路径，其中五排椅子。在插图中大厅是只有 10 把椅子宽，而不是 100 把。输入中的第一个数字将包含number n – 行数。接下来的 n 行将有两个数字，以空格分隔，指出差距在哪里。例子输入:5个3 62 84 57 83 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|)那么我的问题是

1. 给定问题这个算法是否可以接受

2. 我将如何在 java 中实现这个算法或另一个算法

@胡安洛佩斯以这个例子为例(0代表一个空格)。

第 6 行:0 2 3 4 5 6 0 8 9

第 5 行:0 2 3 4 5 6 0 8 9

第 4 行:1 2 3 0 5 6 0 8 9

第 3 行:1 2 3 0 5 6 0 8 9

第 2 行:1 2 3 0 5 6 0 8 9

第 1 行:1 2 3 0 5 6 0 8 9

我从您的算法中了解到，它会单独查看每一行。因此，通过第 1-4 行，每个空间到下一行之间的距离是相等的，但是当您到达第 5 行时，如果您沿着所有 4 都丢失的路径前进，那么与沿着所有 4 的路径前进相比，您会花费更长的时间缺少 7，您的解决方案是否考虑到了这一点？

Answer 1

您描述的算法是 Not Acceptable ，因为最多可以有 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}
        }));
    }
}