Подсчитать количество путей в сетке с помощью динамического программирования?

Робот сидит в верхнем левом углу сетки NxN. Робот может двигаться только в двух направлениях: вправо и вниз, где некоторые из ячеек мертвы, т.е. робот не может войти в эту ячейку. Сколько возможных путей есть для робота?
Это можно решить с помощью обратного отслеживания, но сложность времени слишком высока. Я решил эту проблему с помощью обратного отслеживания, но в худшем случае требуется O (2 ^ n).

bool exist(bool a[][], int i, int j,int N){
        return i>=0 && j >=0 && i < N && j < N;
    }
    int search(bool  a[][], int i, int j,int N){
        if(!exist(a,i,j,N) || a[i][j] == 1)
            return 0; // no path here.
        if(i == N-1 && j == N - 1){
            return 1; // 1 path here.
        }
        a[i][j] = 1; // mark that we have seen this spot here
        int paths = 0; // introduce a counter...
        paths += search(a, i,j+1,N); // add the additional paths as we find them
        paths += search(a, i+1,j,N);
        a[i][j] = 0;
        return paths; // return the number of paths available from this point.
    }

Здесь ячейка с 1 представляет собой мертвую ячейку.Есть ли способ уменьшить временную сложность с помощью DFS или динамического программирования и т. д.?


c++ algorithm dynamic-programming backtracking depth-first-search
person user3182811    schedule 21.12.2014    source источник
comment
А в чем вопрос?   -  person Cheers and hth. - Alf    schedule 21.12.2014
comment
Уменьшение временной сложности...   -  person user3182811    schedule 21.12.2014
comment
Это не вопрос...   -  person Lightness Races in Orbit    schedule 22.12.2014

Ответы (3)


arrow_upward
0
arrow_downward

Учитывая NxN grid, пусть ways[i][j] = number of possible paths from grid[0][0] to grid[i][j]

инициализировать grid[0][0] = 1

if grid[i][j] is dead, ways[i][j] = 0

else ways[i][j] = ways[i-1][j] + ways[i][j-1] (но будьте осторожны с краем)

Пример:

grid:(1 means dead)   ways:

0 0 1 0 0             1 1 0 0 0
0 0 0 0 0             1 2 2 2 2
0 1 0 0 1             1 0 2 4 0
1 0 0 0 0             0 0 2 6 6
0 0 0 0 0             0 0 2 8 14

Думаю сложность O(n^2) так как там n*n сеток.

person justmscs    schedule 21.12.2014
comment
можешь дать мне ссылку? Возможно ли, что grid[0][0] мертв? - person justmscs; 21.12.2014

arrow_upward
1
arrow_downward

Эту проблему можно решить, признав, что количество путей к конкретному узлу — это просто сумма количества путей к узлу слева + количество путей к узлу выше. Вам просто нужно придумать алгоритм для обработки узлов в правильном порядке, то есть обрабатывать узел только после обработки его «родителей». Я считаю, что это может быть O (n).

person Sonic    schedule 21.12.2014
comment
Когда n является стороной сетки, я думаю, вы имеете в виду n ^2. - person Cheers and hth. - Alf; 21.12.2014
comment
Да, O(n^2) для сетки n x n или O(n), если n представляет количество узлов. - person Sonic; 21.12.2014

arrow_upward
1
arrow_downward

Предположим, что у нас есть следующая сетка 3x3, где 1 в сетке обозначает препятствие.

[0, 0, 0]
[0, 1, 0]
[0, 0, 0]

Количество уникальных путей в этом случае равно 2. Мы можем использовать подход динамического программирования, чтобы уменьшить временную сложность поиска уникальных путей, и вот код для того же на С++.

int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
       int m = obstacleGrid.size();
       int n = obstacleGrid[0].size();

    vector<vector<int> > arr(m,vector<int>(n,0));

    if (obstacleGrid[0][0]==1){return 0;}
    arr[0][0]=1;
    for (int i=1;i<m;i++){
        if (obstacleGrid[i][0]!=1){
            arr[i][0] = arr[i-1][0];
        }
    }
    for (int i=1;i<n;i++){
        if (obstacleGrid[0][i]!=1){
            arr[0][i] = arr[0][i-1];
        }
    }
    for (int i=1;i<m;i++){
        for(int j=1;j<n;j++){
            if (obstacleGrid[i][j]!=1){
                arr[i][j] = arr[i][j-1] + arr[i-1][j];
            }
        }
    }   
    return arr[m-1][n-1];
}

Временная сложность в этом случае O(mn).

person Community    schedule 22.01.2015
comment
Есть ли причина, по которой вы предлагаете удалить тег [queue] из стольких вопросов? - person Justin; 24.01.2015
comment
Я отфильтровываю вопрос, в котором есть ненужная очередь с тегами, чтобы людям не было сложно искать вопросы на основе тега очереди. - person ; 24.01.2015
comment
@Bector Я реализовал ваш код на Python, но не смог заставить его работать. Я думаю, что одной из причин может быть то, что вы устанавливаете arr[0][0]=1;, тогда как это значение может быть 2 (и в вашем примере это так). - person aarslan; 03.02.2016