N 행 N 격자의 모든 경로를 계산하는 알고리즘, non-repeat

Question

나는 NxN 셀의 그리드를 가지고있다 (Array [N] [N]으로 정의 된 2 차원 배열을 생각해 보라).

1. 어떤 셀이 단일 경로 내에서 두 번 포함되어 있지 :

   어떤 알고리즘 모든 셀에있는 모든 셀에서 모든 경로 A [I] [J]은 [K] [1]을 계산한다.

2. 인접한 대각선, 수평 및 수직 이동이 모두 허용됩니다.
3. 알고리즘은 평균 속도가 가장 빠릅니다.
4. 최소 메모리가 사용됩니다.

Answer 1

실제 경로는 물론 그 수가 아니라고 가정합니다.

당신은 동일한 경로 탐구 정점에 visited 설정을 유지하고, 이미 동일한 경로에서 발견 된 정점을 탐험 방지 DFS를 사용하여 얻을 수 있습니다.

의사 코드 :

DFS(v,target,visited): 
    if (v == target): 
     print path to v from the initial sorce 
     return 
    visited.add(v) 
    for each vertex u such that u is a neighbor of v: 
     if (u is not in visited): 
      u.parent <- v 
      DFS(u,target,visited) 
    visited.remove(v) 

는 with DFS(source,target,{}) 호출 [{} 빈 visited 세트이다].

Answer 2

너비 우선 검색은 원하는 것을 정확하게 수행합니다. 모든 경로를 생성 할 때 가장 빠르지 않습니다.