A *實現總是返回相同的值

Question

我似乎不是失去理智或misimplementing A *算法：

下面是我的代碼，似乎無論什麼值我輸入後總是回到360上午我在這裏錯過了一些關鍵信息？還沒有人問是否與我收到的機器學習作業有關。

公共類A_Star {

private ArrayList<SearchNode> closedNodes = new ArrayList<SearchNode>(); 
private ArrayList<SearchNode> openNodes = new ArrayList<SearchNode>(); 
private ArrayList<SearchNode> siblingNodes = new ArrayList<SearchNode>(); 
private ArrayList<SearchNode> obstacleNodes; 
final SearchNode START_NODE = new SearchNode(0,115,655); 
final SearchNode END_NODE = new SearchNode(0,380,560); 
final int HEURISTIC = 1 * Math.abs((END_NODE.getxCoordinate() - START_NODE.getxCoordinate()) + (START_NODE.getyCoordinate() - END_NODE.getyCoordinate())) ; 

private int cost = 0; 
//Start: (115, 655) End: (380, 560) 

public int starSearch(SearchNode currentNode, Set<SearchNode> obstacleNodes) throws Exception { 
    //h(n) = D * (abs(n.x-goal.x) + abs(n.y-goal.y)) 

    boolean isMaxY = false; 
    boolean isMaxX = false; 
    int currentY = currentNode.getyCoordinate(); 
    int currentX = currentNode.getxCoordinate(); 
    System.out.println(currentNode.getxCoordinate() + " " + currentNode.getyCoordinate() + " Current Coordinates"); 

    int currentGScore = Math.abs(currentNode.getxCoordinate() - END_NODE.getxCoordinate()) + (currentNode.getyCoordinate() - END_NODE.getyCoordinate()); 

    currentNode.setgScore(currentGScore); 
    System.out.println("Current node G score at entry: " + currentNode.getgScore()); 

    if(!closedNodes.contains(currentNode)){ 
     closedNodes.add(currentNode); 

    } 

    if(currentNode.getyCoordinate() == END_NODE.getyCoordinate()){ 
       isMaxY=true; 
      } 
     if(currentNode.getxCoordinate() == END_NODE.getxCoordinate()) { 
       isMaxX =true; 
      } 

    SearchNode bottomCenter = new SearchNode(0,currentNode.getxCoordinate(), currentNode.getyCoordinate() -1); 
    SearchNode middleRight = new SearchNode(0,currentNode.getxCoordinate() +1, currentNode.getyCoordinate()); 
    SearchNode middleLeft = new SearchNode(0,currentNode.getxCoordinate() -1, currentNode.getyCoordinate()); 
    SearchNode topCenter = new SearchNode(0,currentNode.getxCoordinate(), currentNode.getyCoordinate()+1); 
    int middleRightGScore = Math.abs(middleRight.getxCoordinate() - END_NODE.getxCoordinate()) + (middleRight.getyCoordinate() - END_NODE.getyCoordinate()); 
    int bottomCenterGScore = Math.abs(bottomCenter.getxCoordinate() - END_NODE.getxCoordinate()) + (bottomCenter.getyCoordinate() - END_NODE.getyCoordinate()); 
    int middleLeftGScore = Math.abs(middleLeft.getxCoordinate() - END_NODE.getxCoordinate()) + (middleLeft.getyCoordinate() - END_NODE.getyCoordinate()); 
    int topCenterGScore = Math.abs(topCenter.getxCoordinate() - END_NODE.getxCoordinate()) + (topCenter.getyCoordinate() - END_NODE.getyCoordinate()); 
    middleRight.setgScore(middleRightGScore); 
    middleLeft.setgScore(middleLeftGScore); 
    bottomCenter.setgScore(bottomCenterGScore); 
    topCenter.setgScore(topCenterGScore); 
    for(SearchNode obstacleNode:obstacleNodes){ 
     int obstacleX = obstacleNode.getxCoordinate(); 
     int obstacleY = obstacleNode.getyCoordinate(); 

      if((middleRight != null) && (middleRight.getxCoordinate() == obstacleX)){ 
     if(middleRight.getyCoordinate() == obstacleY){ 

      // throw new Exception(); 
      System.out.println("REMOVING AND NULLING: " + middleRight.toString()); 
      siblingNodes.remove(middleRight); 
        middleRight = null; 

     } 
    } 



     if((middleLeft!=null)&&(middleLeft.getxCoordinate() == obstacleX)){ 
     if(middleLeft.getyCoordinate() == obstacleY){ 

      System.out.println("REMOVING AND NULLING: " + middleLeft.toString()); 
      siblingNodes.remove(middleLeft); 
        middleLeft=null; 
     } 
    } if((bottomCenter!=null) &&(bottomCenter.getxCoordinate() == obstacleX)){ 
     if(bottomCenter.getyCoordinate() == obstacleY){ 

      System.out.println("REMOVING AND NULLING: " + bottomCenter.toString()); 
      siblingNodes.remove(bottomCenter); 
        bottomCenter = null; 
     } 
    } if((topCenter!=null) && (topCenter.getxCoordinate() == obstacleX)){ 
     if(topCenter.getyCoordinate() == obstacleY){ 
        System.out.println("REMOVING AND NULLING: " + topCenter.toString()); 
      siblingNodes.remove(topCenter); 
        topCenter=null; 
     } 
    } 

    if((middleRight != null) && (middleRight.getxCoordinate() != obstacleX)){ 
     if(middleRight.getyCoordinate() != obstacleY){ 
        System.out.println("ADDING THE FOLLOWING: " + middleRight.toString()); 
        siblingNodes.add(middleRight); 
     } 
    } 



     if((middleLeft != null) && (middleLeft.getxCoordinate() != obstacleX)){ 
     if(middleLeft.getyCoordinate() != obstacleY){ 

        siblingNodes.add(middleLeft); 
     } 
    } if((bottomCenter != null) && (bottomCenter.getxCoordinate() != obstacleX)){ 
     if(bottomCenter.getyCoordinate() != obstacleY){ 

        siblingNodes.add(bottomCenter); 
     } 
    } if((topCenter !=null) && (topCenter.getxCoordinate() != obstacleX)){ 
     if(topCenter.getyCoordinate() != obstacleY){ 

        siblingNodes.add(topCenter); 
     } 
    } 
    } 

    int highestScore = currentNode.getgScore(); 
    for(SearchNode node: siblingNodes){ 
      if(node == null){ 
      continue; 
      } 
     if(node.getxCoordinate() == END_NODE.getxCoordinate() && node.getyCoordinate() == END_NODE.getyCoordinate()){ 
      System.out.println("Returning cost: " + ++cost + " of: " + node.toString()); 
      return cost; 
     } 
     // System.out.println("Current node size: " + siblingNodes.size()); 
     if(node.getgScore() < highestScore){ 

      highestScore = node.getgScore(); 
      currentNode=node; 
      cost++; 
      System.out.println("Changed highest score: " + highestScore); 
      System.out.println("Removing node: " + node.toString()); 
      siblingNodes.remove(node); 
      System.out.println("Incrementing cost the Current Cost: " + cost); 
      starSearch(currentNode,obstacleNodes); 
      break; 
     } 

    if(isMaxY && isMaxX){ 
        return cost; 
    } 
    } 
    return cost; 
    //Always move diagonal right downwards 
} 

public static void main(String[] args) throws Exception{ 
    System.out.println("Hello"); 
    A_Star star = new A_Star(); 
    HashSet<SearchNode> obstacles = new HashSet<SearchNode>(); 
    obstacles.add(new SearchNode(0,311,530)); 
    obstacles.add(new SearchNode(0,311,559)); 
    obstacles.add(new SearchNode(0,339,578)); 
    obstacles.add(new SearchNode(0,361,560)); 
    obstacles.add(new SearchNode(0,361,528)); 
    obstacles.add(new SearchNode(0,116, 655)); 
    int cost = star.starSearch(star.START_NODE, obstacles); 
    System.out.println(cost); 

    //((311, 530), (311, 559), (339, 578), (361, 560), (361, 528), (336, 516)) 
} 

}

和

公共類SearchNode {

private int xCoordinate; 
    private int yCoordinate; 
    private int cost; 

public int getfScore() { 
    return fScore; 
} 

public void setfScore(int fScore) { 
    this.fScore = fScore; 
} 

private int fScore; 

public int getgScore() { 
    return gScore; 
} 

public void setgScore(int gScore) { 
    this.gScore = gScore; 
} 

private int gScore; 

public SearchNode（int cost，int xCoordinate，int yCoordinate）{
this.cost = cost;
this.xCoordinate = xCoordinate;
this.yCoordinate = yCoordinate;
}
public int getCost（）{ return cost; }

public void setCost(int cost) { 
     this.cost = cost; 
    } 



    public int getxCoordinate() { 
     return xCoordinate; 
    } 

    public void setxCoordinate(int xCoordinate) { 
     this.xCoordinate = xCoordinate; 
    } 

    public int getyCoordinate() { 
     return yCoordinate; 
    } 

    public void setyCoordinate(int yCoordinate) { 
     this.yCoordinate = yCoordinate; 
    } 

public String toString(){ 
    return "Y Coordinate: " + this.yCoordinate + " X Coordinate: " + this.xCoordinate + " G Score: " + this.gScore; 
} 

}

Answer 1

我假設圖形是一個正常的矩形網格，其中沒有任何解決方案應該通過其中的障礙節點。此外，我假設從一個節點到鄰居節點的旅行是1.我也意識到曼哈頓距離被用作啓發式。

鑑於這些，我恐怕你是一個錯誤的實施。

首先，而不是遞歸的你應該使用迭代方法。考慮到圖的大小，如果它是一個正確的實現，你肯定會得到Stackoverflows。其次，GValue，HValue，FValue和/或成本的概念似乎存在問題。我覺得有必要對這些術語進行非正式的描述。

的簡化計算A *採用的是F = G + H其中

G是當前計算從起始節點行進到當前節點的成本。因此，對於起始節點，G值應該爲0，從startNode可到達的任何節點應該具有1的G值（我的假設是這樣的，從節點到鄰居節點）我想強調'當前'項這裏，因爲在算法運行期間節點的g值可能會改變。

H是成本的啓發式部分，表示從當前節點到終端節點的成本。與G部分不同，節點的H值根本不變（這裏我有疑問，可能會有這樣的啓發式嗎？，你們不會這樣繼續下去），它應該只計算一次。您的實現似乎將曼哈頓距離作爲啓發式，這絕對是這種圖形的最佳啓發式。但要小心我的朋友，這裏似乎也有一個小問題：差異的絕對值應該分開，然後加以總結。

而F是這些值的總和，表示從當前節點傳遞解決方案的可能成本（如果您的圖和啓發式任何計算的F值應該等於或小於實際成本，這是好的） 。

有了這些在手，我會用一個SearchNode這樣的：

private ArrayList<SearchNode> closedNodes = new ArrayList<SearchNode>(); 
private ArrayList<SearchNode> openNodes = new ArrayList<SearchNode>(); 
//create the start and end nodes 
SearchNode end = new SearchNode(380, 560, -1, null); 
SearchNode start = new SearchNode(115,655, 0, end); 


// add start node to the openSet 

openNodes.Add(start); 

while(openNodes.Count > 0) // while there still is a node to test 
{ 
    // I am afraid there is another severe problem here. 
    // OpenSet should be PriorityQueue like collection, not a regular Collection. 
    // I suggest you to take a look at a Minimum BinaryHeap implementation. It has a logN complexity 
    // of insertion and deletion and Constant Complexity access. 

    // take the Node with the smallest FValue from the openSet. (With BinHeap constant time!) 
    SearchNode current = openNodes.GetSmallestFvaluedNode(); // this should both retrieve and remove the node fromt he openset. 

    // if it is the endNode, then we are node. The FValue (or the Gvalue as well since h value is zero here) is equal to the cost. 
    if (current.EqualTo(end)) // not reference equality, you should check the x,y values 
{ 
    return current.getfScore(); 
} 

    //check the neighbourNodes, they may have been created in a previous iteration and already present in the OpenNodes collection. If it is the case, their G values should be compared with the currently calculated ones. 
// dont forget to check the limit values, we probably do not need nodes with negative or greater than the grid size coordinate values, I am not writing it 
// also here is the right place to check for the blocking nodes with a simple for loop I am not writing it either 

    double neighbourGValue = current.getgScore() + 1; 
if (openNodes.Contains(current.getXCoordinate(), current.getYCoordinate() + 1)) 
    { 
    // then compare the gValue of it with the current calculated value. 
    SearchNode neighbour = openNodess.getNode(current.getXCoordinate(), current.getYCoordinate() + 1); 
    if(neighbour.getgScore() > neighbourGValue) 
     neighbour.setgScore(neighbourGValue); 
    } 
    else if(!closedNodes.Contains(current.getXCoordinate(), current.getYCoordinate())) 
    { 
     // create and add a fresh Node 
    SearchNode n = new SearchNode(current.getXCoordinate(), current.getYCoordinate() + 1, neighbourGValue, endNode); 
    openNodes.Add(n); 
    } 
    // do the same for the other sides : [x+1,y - x-1,y - x, y-1] 

    // lastly add the currentNode to the CloseNodes. 
    closedNodes.Add(current); 
} 

// if the loop is terminated without finding a result, then there is no way from the given start node to the end node. 
return -1; 

唯一的問題彈出我的腦海裏有關上述實施：

public class SearchNode { 
    private int xCoordinate; 
    private int yCoordinate; 
    private double gScore; 
    private double hScore; 

    public double getfScore() { 
     return gScore + hScore; 
    } 

    public double getgScore() { 
     return gScore; 
    } 

    public void setgScore(int gScore) { 
     this.gScore = gScore; 
    } 


    public SearchNode(int xCoordinate,int yCoordinate, double gScore, SearchNode endNode) { 
     this.gScore=gScore; 
     this.hScore = //Manhattan distance from this node to end node 
     this.xCoordinate =xCoordinate; 
     this.yCoordinate = yCoordinate; 
    } 

    public int getxCoordinate() { 
     return xCoordinate; 
    } 

    public int getyCoordinate() { 
     return yCoordinate; 
    } 
} 

則該算法可等來實現是行

if (openNodes.Contains(current.getXCoordinate(), current.getYCoordinate() + 1)) 

即使開放集合被實現爲Min Binary Heap沒有簡單的方法來檢查非最小f值的節點。我不記得現在的細節，但我記得用logN複雜性來實現這個。此外，我的實現是在一次調用中訪問和更改該節點的g值（如果有必要），所以您不用再花時間檢索它。無論g值如何變化，如果有一個具有給定座標的節點，它將返回true，因此不會生成新節點。

當我寫完所有這些時，我意識到了最後一件事。你說過，在你實施的任何輸入都計算出相同的結果。那麼如果你提到的輸入是障礙節點，那麼它大多數情況下就是它會發現，無論它是什麼實現方式，因爲它正在尋找儘可能短的距離，所以它的距離相同。在下面的圖片中，我試圖解釋這一點。

Answer 2

下面是我的代碼，它似乎沒有 無論輸入怎樣的價值觀會 總是返回360

我的第一個猜測是您對每個節點都有固定的啓發成本。那麼360可能會從哪裏來？

final SearchNode START_NODE = new SearchNode(0,115,655); 
final SearchNode END_NODE = new SearchNode(0,380,560); 

假設你使用的是曼哈頓距離啓發式，（380-115）+（655-560）= 265 + 95 = 360

的代碼，因爲它的格式有點難以閱讀。但我的猜測是您計算了開始節點的h值，並且之後您將其用於每個節點。請記住h（x）< = d（x，y）+ h（y）併爲每個節點擴展計算它。