如何使用回溯搜索解决问题？

Question

N 人（<13）排成一排。我需要找到当 P 人看到左边的所有内容而 R 看到右边的所有内容时的排列数。也就是说，如果 N = 10，P = 4，R = 4，则“7 8 9 10 1 2 6 5 4 3”是正确的排列。

我尝试实现一个回溯算法。但是，输出始终为 0。我检查了明确表示此路径不会导致解决方案的条件。例如，如果 a[0] = 10，那么迭代剩余的 i 就没有意义，因为最左边的人最高，他关闭了视图。这是我的代码：

public class Backtracking {
    private static final int n = 10;
    private static final int left = 4;
    private static final int right = 4;
    static int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    static int was[] = new int[10];
    static int [] conditions = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    static int count = 0;

    public static void main(String[] args) {
        backtrack(0);
        System.out.println(count);
    }

    private static void backtrack(int i) {
       if(i > n) {
           count++;
           return;
       }

       for(int j = 0; j < n; j++) {
           if(was[j] == 0) {
                arr[i] = j;
                was[j] = 1;

                if(checkCondition(i)) {
                    backtrack(i + 1);
                    was[j] = 0;
                }
           }
       }
    }

    private static boolean checkCondition(int i) {
        if(i < left-1) {
            int constrain = left-i;
            if(arr[i] >= conditions[conditions.length - constrain]) {
                return false;
            }
        }

        else if (i > arr.length - right) {
            int constrain = arr.length-i;
            if(arr[i] >= conditions[conditions.length - constrain]) {
                return false;
            }
        }

        else {
            if(arr[i] > arr[left-1] || arr[i] > arr[arr.length - right - 1]) {
                return false;
            }
        }
        return true;
    }
}

更新：更改了代码，现在一切正常（但对于 n = 13，它确实需要很多时间）：

public class Backtracking {
    private static int n ;
    private static int left;
    private static int right;
    static int arr[];
    static int was[];
    static int count = 0;

    public static void main(String[] args) throws FileNotFoundException {
        long start = System.currentTimeMillis();

        Scanner scanner = new Scanner(new File("data/file.txt"));
        int inputs = scanner.nextInt();

        for(int i = 0; i < inputs; i++) {
            count = 0;
            n = scanner.nextInt();
            left = scanner.nextInt();
            right = scanner.nextInt();

            arr = new int[n];
            was = new int[n];

            backtrack(0);
            System.out.println(count);
        }

        long finish = System.currentTimeMillis();
        long elapsed = finish - start;
        System.out.println("Прошло времени, с: " + (double)elapsed / 1000.0);
    }

    private static void backtrack(int i) {
       if(i > n - 1) {
           count++;
           return;
       }

       for(int j = 0; j < n; j++) {
           if(was[j] == 0) {
                arr[i] = j + 1;
                was[j] = 1;

                if(checkCondition(i)) {
                    backtrack(i + 1);
                }
               was[j] = 0;
           }
       }
    }

    private static boolean checkCondition(int i) {
        /*
        if(i < left-1) {
            int constrain = left-i-1;
            if(arr[i] >= conditions[conditions.length - constrain]) {
                return false;
            }
        }
        */

        if(i == n-1) {
            if (countLeft(i) != left || countRight(i) != right) return false;
        }
        return true;
    }

    private static int countLeft(int n){
        int count = 0;
        for(int i = 0; i <= n; i++) {
            boolean flag = false;
            for(int j = 0; j < i; j++) {
                if(arr[i] < arr[j]) {
                    flag = true;
                    break;
                }
            }
            count = (flag) ? count : count + 1;
        }
        return count;
    }

    private static int countRight(int n) {
        int count = 0;
        for(int i = arr.length-1; i >= 0; i--) {
            boolean flag = false;
            for(int j = arr.length-1; j > i; j--) {
                if(arr[i] < arr[j]) {
                    flag = true;
                    break;
                }
            }
            count = (flag) ? count : count + 1;
        }
        return count;
    }
}

Answer 1

即使您由于最高人的位置而观察到了捷径，回溯解决方案仍然会通过太多可能性进行暴力破解。花费太长时间也就不足为奇了。组合思考。

固定最高人的位置（应该在P和N-R之间）。
观察左侧分区中的任何人都无法看到右侧的视图。正确的分区也是如此。问题自然分解为两个单向问题。
还请注意，究竟谁在左侧分区中并不重要。无论如何都有相同数量的排列。右分区同上。

现在，如果最高的人位于 k 位置，则有 (n-1) chose (k-1) 种方式填充左侧分区。假设一个单向视角问题有 F(p, k) 个解，则主要问题的答案是

sum[k: P..N-R] chose(n-1,k-1) F(P-1, k-1) * F(N-k-1, n-k)

要计算 F(p, k)，遵循相同的行。固定最高人的位置j（应该在p-1和k之间）。有 (k-1) chose (p-1) 种填充左侧分区的方法（同样，选择谁并不重要）；正确的分区可以是任何顺序。子问题的答案由递归给出

F(p, k) = sum[j: p-1..k] chose(j-1,k-1] (k-j)! F(p-1, j-1)

现在一个简单的记忆应该在合理的时间内给出结果。

如何使用回溯搜索解决问题？

How to solve a problem using backtracking search?

java

algorithm

recursion

backtracking