整數遞歸A的每個循環中被重置*算法

Question

我一直停留在這個棘手的錯誤，在過去幾個小時，我在想，如果這裏有人可以幫助我。

基本上我實現通過遞歸A *，我想每個節點（稱爲代碼中的一個瓦片）來存儲它已經通過先前的節點的數目的一個整數值。這是這樣的，一旦算法找到了出口，它可以返回並返回最短路線。

然而轉彎計數器正在每次遍歷函數時間復位。但是，如果我刪除行：

map[y][x].setID(path); 

它細支起來，當然生成一個堆棧溢出錯誤，但我真的不能明白爲什麼這會導致問題。

代碼的主比特是在這裏：

private static Tile[][] findSquares(IntVector v, Tile[][] map, int wall, int empty, int end, int start, int path, int turns) 
{ 
    // System.out.println(turns); 
    if (!isHit) 
    { 
     for (int y = v.y - 1; y <= v.y + 1; y++) 
     { 
      for (int x = v.x - 1; x <= v.x + 1; x++) 
      { 
       if (map[y][x].id == end) 
       { 
        isHit = true; 
       } 
       else if (map[y][x].id != wall && map[y][x].id != path && map[y][x].id != end && !isHit && map[y][x].id != start) 
       { 
        map[y][x].turns++; 
        System.out.println(map[y][x].turns); //Always Results in 1 

        map[y][x].setID(path); 
        findSquares(new IntVector(x, y), map, wall, empty, end, start, path, turns); 
        break; 
       } 
      } 
     } 
    } 
    return map; 
} 

與表示節點瓦片。這裏是瓷磚類：

static private class Tile 
{ 
    int id; 
    int turns = 0; 

    Tile(int id) 
    { 
     this.id = id; 
    } 

    public void addTurn() 
    { 
     turns++; 
    } 

    public void setID(int id) 
    { 
     this.id = id; 
    } 

    public int getTurns() 
    { 
     return turns; 
    } 

    public Tile setTurns(int turns) 
    { 
     this.turns = turns; 
     return this; 
    } 
} 

也許這是關於瓦類是靜態的？

Answer 1

的問題不在於轉計數器是被「復位」，那就是你永遠遞增一次以上。其中turns僅增加分支時發生id != path，但你設置id到path隨即，所以它不會再增加。

什麼你可能打算是 map[y][x].turns = map[v.y][v.x].turns + 1;

無論如何，即使您修復的距離計算，你的代碼幾乎類似於A *。它看起來像你的代碼實際上做的是深度優先搜索，隱式地在程序調用堆棧上維護你的搜索堆棧。

A *算法包括保持待搜索節點的優先級隊列，並使用啓發函數加上當前距離來計算插入節點的新的優先級。