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

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个.输入中的第一个数字将包含数字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 |那么我的问题是

1. 这个可接受的算法是否存在问题

2. 我将如何在java中实现此算法或其他算法

@JuanLopes以此为例(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

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