Простой способ найти все пути от верхнего ряда матрицы до нижнего ряда - PullRequest
Новая
       19

Простой способ найти все пути от верхнего ряда матрицы до нижнего ряда

0 голосов
/ 09 января 2020

Учитывая матрицу A, как вы найдете количество всех возможных путей от строки 1 до последней строки, при условии, что каждый '1' может соединиться с 3 элементами, смежными с ним в строке ниже (кроме ребер 1, если они есть, они очевидно, соединиться с 2).

Я ищу способы реализовать это без использования сложных языковых или c библиотек или функций.

Я использую fortran95 и пробовал в течение нескольких часов, но до сих пор не удалось найти все пути.

A = 

 0 1 0 1
 1 1 1 0
 1 0 1 0
 0 1 0 1

Ответы [ 2 ]

4 голосов
/ 09 января 2020

Вы можете использовать небольшую модификацию алгоритма заливки для решения этой проблемы. По сути, мы рассматриваем двумерную сетку как неявный граф, в котором каждый единичный квадрат является вершиной, и две вершины соединены при условии, что одна из вершин находится непосредственно над или по диагонали над другой вершиной. К сожалению, я не знаком с Fortran, но вот некоторый код C ++, смешанный с каким-то псевдокодом, который может вам помочь. Я оставлю вам конкретные детали реализации c. 

int count_paths(vector<vector<int>> grid) {
   int sum = 0;
   for (int i = 0; i < number of columns; i++) {
      sum += floodfill(0, i);
   }
   return sum;
}

int floodfill(int row, int column) {
   if (row, column) is out of bounds, return 0.
   if the value in the grid at (row, column) is 0, return 0.
   if we are in the last row, return 1. 

   return  floodfill(row + 1, column) + floodfill(row + 1, column + 1) + 
           floodfill(row + 1, column - 1) 
}
3 голосов
/ 13 января 2020

Проблема с поиском в глубину для этой проблемы заключается в том, что в худшем случае это O (3ⁿm), потому что он пересекает все возможные пути. поиск в ширину может быть более эффективным, поскольку он всегда использует примерно 3 млн шагов для генерации всех возможных дуг графа только один раз, если только массив A не очень разреженный. Пример обоих, основанный на @ Eke sh псевдокоде Кумара для поиска в глубину: 

module functions
   implicit none
   contains
      recursive function depth_first(A,i,j) result(r)
         logical, intent(in) :: A(:,:) ! The map
         integer, intent(in) :: i      ! Row
         integer, intent(in) :: j      ! Column
         integer r                     ! Result variable
         if(j < 1 .OR. j > size(A,2)) then
            r = 0
         else if(.NOT. A(i,j)) then
            r = 0
         else if(i == size(A,1)) then
            r = 1
         else
            r = depth_first(A,i+1,j-1)+depth_first(A,i+1,j)+depth_first(A,i+1,j+1)
         end if
      end function depth_first

      function breadth_first(A)
         logical, intent(in) :: A(:,:) ! The map
         integer breadth_first         ! Result variable
         integer row(size(A,2))        ! Number of path to elements of current row
         integer i                     ! Current row
         row = merge(1,0,A(1,:))
         do i = 2, size(A,1)
            row = merge(eoshift(row,-1)+row+eoshift(row,1),0,A(i,:))
         end do
         breadth_first = sum(row)
      end function breadth_first
end module functions

program paths
   use functions
   implicit none
   integer, parameter :: m = 4 ! Number of rows
   integer, parameter :: n = 4 ! Number of columns
   ! Using a LOGICAL array is more 'Fortranny' :)
   logical :: A(m,n) = reshape([ &
      0, 1, 0, 1, &
      1, 1, 1, 0, &
      1, 0, 1, 0, &
      0, 1, 0, 1], &
      [m,n], order = [2,1]) == 1
   integer j                  ! Current column in first row
   write(*,'(*(g0))') 'Results of depth-first search: paths = ',sum([(depth_first(A,1,j),j=1,n)])
   write(*,'(*(g0))') 'Results of breadth-first search: paths = ',breadth_first(A)
end program paths
...