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

Question

这是一个编程竞赛的问题

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

穿过大厅的最短路径 [作者：Hulsbos High 的 Alan Smithee]

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

@JuanLopes 以这个例子为例（0s代表一个space）。

第 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 行，每个 space 到下一行之间的距离是相等的，但是当您到达第 5 行时，如果您沿着所有 4 都丢失的路径前进，那么与沿着缺少所有 7 的路径，您的解决方案是否考虑到这一点？

Answer 1

你描述的算法是不可接受的，因为最多可以有 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}
        }));
    }
}

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

Shortest path in a custom binary search tree

java

algorithm

recursion

binary-search-tree

graph-theory

这是一个编程竞赛的问题