は、Java

Question

で迷路のパスを辿りだから私は適切に迷路を解くプログラムを持っており、以下の何のように見える多次元整数配列solvedMaze溶液を格納します。ここで指摘して

110111 
110101 
010100 
110100 
011100 
000000 

開始および終了である：私は迷路のパスを解決し、リトレースする両方有する

S10111 
11010E 
010100 
110100 
011100 
000000 

コードを以下に示す：

public List<Location> solution() { 
    int[][] solvedMaze = new int[height][width]; 
    Location current; 

    PriorityQueue<Location> queue = new PriorityQueue<>(new Comparator<Location>() { 
     @Override 
     public int compare(Location a, Location b) { 
      double distanceA = distance(start, a)/1.5 + distance(a, end); 
      double distanceB = distance(start, b)/1.5 + distance(b, end); 
      return Double.compare(distanceA, distanceB); 
     } 

     private double distance(Location first, Location second) { 
      return Math.abs(first.i() - second.i()) + Math.abs(first.j() - second.j()); 
     } 
    }); 

    queue.add(start); 

    while ((current = queue.poll()) != null) { 
     if (solvedMaze[current.i()][current.j()] != 0) { 
      continue; 
     } 

     int mod = 1; 

     for (Location next : new Location[]{ 
      current.south(), current.west(), current.north(), current.east() 
     }) { 
      if (isInMaze(next) && isClear(next)) { 
       if (solvedMaze[next.i()][next.j()] == 0) { 
        queue.add(next); 
       } else { 
        mod = Math.min(solvedMaze[next.i()][next.j()], mod); 
       } 
      } 
     } 

     solvedMaze[current.i()][current.j()] = mod; 

     if (isFinal(current)) { 
      break; 
     } 
    } 

    for (int i = 0; i < height; i++) { 
     for (int j = 0; j < width; j++) { 
      System.out.print(solvedMaze[i][j]); 
     } 
     System.out.println(); 
    } 

    if (solvedMaze[end.i()][end.j()] != 0) { 
     List<Location> route = new ArrayList<>(); 
     Location temp = end; 

     while (!temp.equals(start)) { 
      route.add(temp); 

      Location best = null; 
      int bestNumber = solvedMaze[temp.i()][temp.j()]; 

      for (Location next : new Location[]{ 
       temp.north(), temp.south(), temp.west(), temp.east() 
      }) { 
       if (isInMaze(next) && solvedMaze[next.i()][next.j()] != 0) { 
        if (solvedMaze[next.i()][next.j()] < bestNumber) { 
         bestNumber = solvedMaze[next.i()][next.j()]; 
         best = next; 
        } 
       } 
      } 

      assert best != null; 
      temp = best; 
     } 

     route.add(start); 
     Collections.reverse(route); 

     return route; 
    } else { 
     return null; 
    } 
} 

を

Locationは、x座標とy座標を含むクラスであり、startとendはロケーションです。何らかの理由で私の出力は常にnullであり、私はその理由をよく分かりません。単純なprintのデバッグの後、私はリトレースロジックのsolvedMaze[next.i()][next.j()] < bestNumber状態が決して入力されないことを発見しました。メソッドの問題点は何ですか？それを解決するためのより良い（より効率的な）方法がありますか？

Answer 1

表示されたロジックは、solvedMazeの1に頼っていると思われます。これは「開始から最短距離」に置き換えられているため、より良いパス（降順）番号。

など。 solvedMazeは次のようになります。

1 2 0 12 13 14 
2 3 0 11 0 15 
0 4 0 10 0 0 
6 5 0 9 0 0 
0 6 7 8 0 0 
0 0 0 0 0 0