A* 实现总是返回相同的值

Question

我似乎要么失去了理智，要么错误地实现了 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;  

公共SearchNode（int成本，int x坐标，int y坐标）{
this.cost=成本；
this.x坐标=x坐标;
this.y坐标 = y坐标;
}
公共 int getCost() { 退货费用； }

   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，从起始节点可到达的任何节点的 G 值应为 1（我的假设是这样，从一个节点移动到邻居节点）我想强调“当前”术语这里，因为节点的gValue在算法运行过程中可能会发生变化。

H是成本的启发部分，表示从当前节点到结束节点的成本。与 G 部分不同，节点的 H 值根本不会改变（好吧，我在这里有疑问，可能有这样的启发式吗？，你的没有，所以让我们继续），它应该只计算一次。您的实现似乎使用曼哈顿距离作为启发式，这绝对是此类图的最佳启发式。但请注意我的朋友，那里似乎也存在一个小问题：应该单独取差异的绝对值，然后再求和。

F 是这些值的总和，表示从当前节点传递解决方案的可能成本（考虑到您的图表和启发式，任何计算出的 F 值都应该等于或小于实际成本，这很好）。

有了这些，我就可以使用这样的 SearchNode：

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

那么该算法可以这样实现：

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;

关于上述实现，我想到的唯一问题是行

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

即使开放集实现为最小二叉堆，也没有简单的方法检查非最小 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) 并为每个节点扩展计算它。