Самый быстрый алгоритм решения лабиринта

Question

Допустим, вам дали лабиринт. Например:

# ######## 
# # # 
# #### # # 
# # # # 
# # # #### 
# # # # 
# ### ## # 
# #  # 
####### # 

Вы можете представлять лабиринт с точки зрения какой-либо структуры данных вы хотите, например, граф, массив и т.д. Что бы самый быстрый/самый эффективный алгоритм для решения лабиринты любой произвольный размер?

Алгоритмы, которые сначала приходят на ум, - это алгоритм Дейкстры, BFS и DFS. Я не уверен, что эти (или любые другие алгоритмы) будут «лучшими».

Answer 1

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

A* Algorithm

Answer 2

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

пХт является размером матрицы массива

public static int min(int x , int y ,int endx,int endy,int n ,int m,int[][] dp){ 
     int[] dirx ={1,-1,0,0 }; 
      int[] diry={0,0,1,-1}; 
      LinkedList<Point> s = new LinkedList<Point>(); 
      s.add(new Point(x,y)); 
      dp[x][y]=0; // For starting point 

      while(!s.isEmpty()){ 
       Point xx = s.pop(); 
       for(int i=0;i<4;i++){ 

        int x1 = xx.x + dirx[i]; 
        int y1 = xx.y + diry[i]; 

        if(x1>=0 && x1<n && y1>=0 && y1<m && dp[x1][y1]!=-1){ 


          som.add(new Point(x1,y1)); 
          dp[x1][y1] = dp[xx.x][xx.y]+1; 

         } 

        } 
       } 





     return dp[endx][endy]; 
    }