Java bir labirent yolunu retracing

Question

yüzden düzgün bir labirent çözer ve aşağıda ne gibi görünen bir çok boyutlu tamsayı dizisi solvedMaze çözümü depolayan bir program var:

110111 
110101 
010100 
110100 
011100 
000000 

işaret etmek nerede başlangıç ​​ve bitiş şunlardır:

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

:

S10111 
11010E 
010100 
110100 
011100 
000000 

ben çözmek ve bir labirentin yolu tekrar ikisine de sahip kod aşağıda verilmiştir

Burada Location, x ve y koordinatlarını içeren bir sınıftır ve start ve end konumlarıdır. Nedense çıkışım her zaman null ve neden emin değilim. Bazı basit print hata ayıklamalarından sonra, yeniden hesaplama mantığında solvedMaze[next.i()][next.j()] < bestNumber koşulunun hiçbir zaman girilmediğini keşfettim. Yöntemle ilgili sorun nedir? Bunu çözmek için daha iyi (daha verimli) bir yolu var mı?

Answer 1

Görüntülediğiniz mantık, solvedMaze'daki 1'lere "başlangıçtan en kısa mesafe" ile değiştirilmek üzere güveniyor gibi görünmektedir, bu nedenle daha iyi bir yolda Sondan Baştan sona geriye doğru hareket eder (azalan azalan)) sayılar.

E.g. solvedMaze aşağıdaki gibi olmalıdır:

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