Numărați numărul de trasee într-o rețea folosind programarea dinamică? (Programare, C++, Algoritm, Programare Dinamică, Căutare În Profunzime Mai Întâi, Backtracking)

utilizator3182811 a intrebat.

Un robot așezat în colțul din stânga sus al unei grile NxN. Robotul se poate deplasa doar în două direcții: dreapta și jos, În cazul în care unele dintre celule sunt moarte, adică robotul nu poate intra în acea celulă, câte căi posibile există pentru robot?
Această problemă poate fi rezolvată folosind Backtracking, dar complexitatea în timp este prea mare. Am rezolvat această problemă folosind Backtracking, dar durează O(2^n) în cel mai rău caz.

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.
    }

Aici, celula cu 1 reprezintă celula moartă.Există vreo modalitate de a reduce complexitatea timpului folosind DFS sau programarea dinamică, e.t.c.?

Comentarii

  • Și care este întrebarea? –  > Por Salutări și hth. – Alf.
  • Reducerea complexității timpului… –  > Por user3182811.
  • Aceasta nu este o întrebare… –  > Por Curse de luminozitate pe orbită.
3 răspunsuri
justmscs

Având în vedere o NxN grid, , fie ways[i][j] = number of possible paths from grid[0][0] to grid[i][j]

se inițializează grid[0][0] = 1

dacă grid[i][j] is dead, , ways[i][j] = 0

altfel ways[i][j] = ways[i-1][j] + ways[i][j-1] (dar aveți grijă cu marginea)

Un exemplu:

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

Cred că complexitatea este O(n^2) deoarece există n*n grile.

Comentarii

  • îmi puteți da un link? Este posibil ca grid[0][0] să fie mort? –  > Por justmscs.
Sonic

Acest lucru poate fi rezolvat prin recunoașterea faptului că numărul de căi către un anumit nod este doar suma numărului de căi către nodul din stânga + numărul de căi către nodul de deasupra. Trebuie doar să găsiți un algoritm care să proceseze nodurile în ordinea corectă, adică să procesați un nod numai după ce au fost procesați „părinții” acestuia. Cred că acest lucru poate fi O(n).

Comentarii

  • Când n este latura rețelei, cred că vă referiți la n ^2. –  > Por Noroc și bună ziua. – Alf.
  • Da, O(n^2) pentru o grilă n x n, sau O(n) dacă n reprezintă numărul de noduri. –  > Por Sonic.
utilizator4478738

Să presupunem următoarea grilă 3×3 unde 1 în grile reprezintă obstacolul

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

Numărul de căi unice în acest caz este 2. Putem folosi abordarea programării dinamice pentru a reduce complexitatea timpului de găsire a căilor unice și iată codul pentru același lucru în C++

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];
}

Complexitatea timpului în acest caz este O(mn).

Comentarii

  • Există vreun motiv pentru care sugerați să se elimine eticheta [queue] din atât de multe întrebări? –  > Por Justin.
  • Filtrez întrebările care au etichete inutile în coadă în întrebare, astfel încât să nu fie dificil pentru cei care caută întrebări pe baza etichetei coadă – user4478738
  • @Bector Am implementat codul dvs. în python, dar nu am putut să-l fac să funcționeze. Cred că unul dintre motive ar putea fi faptul că setează arr[0][0]=1; în timp ce această valoare ar putea fi 2 (și în exemplul tău, este). –  > Por aarslan.