Быстрый алгоритм для решения уникальных путей с возвратом

Question

Робот, расположенный в верхнем левом углу сетки XxX, пытается достичь правого нижнего угла. Робот может двигаться вверх, вниз, влево или вправо, но не может посещать одно и то же место дважды. Сколько возможных уникальных путей есть в правом нижнем углу?

Что такое быстрое алгоритмическое решение для этого? Я потратил огромное количество времени, пытаясь найти быстрый алгоритм для этого. Но все еще застрял.

Это, в основном, проблема уникального пути Leetcode , за исключением обратного отслеживания.

Уникальные пути без обратного отслеживания могут быть решены с помощью динамического программирования, например:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> cur(n, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] += cur[j - 1];
            }
        }
        return cur[n - 1];
    }
};

Каким было бы быстрое алгоритмическое решение, использующее динамическое программирование для уникальных путей, кроме как с возвратом ? Что-то, что может быстро найти результат 1 568 758 030 464 750 013 214 100 для сетки 10X10.

Reddit , Википедия и Youtube имеют ресурсы, иллюстрирующие сложность этой проблемы. Но у них нет ответов.

Answer 1

Проблема не может быть решена с помощью динамического программирования, потому что рекуррентное отношение не разбивает проблему на подзадачи. Динамическое программирование предполагает, что вычисляемое состояние зависит только от подсостояний в повторении. В этом случае это не так, потому что могут быть циклы, т.е. идти вверх и вниз.

Общим случаем этой задачи для подсчета количества простых путей в ориентированном циклическом графе считается # P-Complete .

Это также может быть перечисление самостоятельных обходов в двух измерениях. Согласно википедии,

Предполагается, что определение количества таких путей является NP-трудной задачей ^{[ссылка на источник]} .

Однако, если рассматривать движения только в положительном направлении, т.е. справа и вниз он имеет решение в закрытой форме ^{m + n} C _m . По сути, общее число ходов всегда устанавливается равным m + n, где m, n - декартовы расстояния до конечной точки диагонали, и нам просто нужно выбрать m право (я) или n вниз (ы). Решение динамического программирования по сути то же самое.