代码之家 › 专栏 › 技术社区 › Woot4Moo

实现总是返回相同的值

a-star shortest-path algorithm java

Woot4Moo · 技术社区 · 14 年前

我似乎是疯了,或者是误执行了A*算法:

下面是我的代码,不管输入什么值,它都会返回360。我是否遗漏了一些关键信息?另外,在任何人问“是”之前,这与我收到的机器学习任务有关。

公共甲级明星{

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

}

和

公共类搜索节点{

    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;

公共搜索节点(int cost,int xcoordinate,int ycoordinate){
this.cost=成本;
this.xcoordinate=xcoordinate;
this.ycoordinate=ycoordinate;
}
public 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;
}

}

2 回复 | 直到 14 年前

tafa 14 年前

我假设这个图是一个规则的矩形网格,其中有障碍节点,所有的解都不应该通过这个网格。此外,我假设从一个节点到相邻节点的旅行是1。我也意识到曼哈顿的距离是用来启发式的。

考虑到这些,恐怕你的做法是错误的。

首先,您应该使用迭代方法,而不是递归方法。考虑到图的大小,如果它是正确的实现,您肯定会得到stackoverflows。

第二,关于价值、价值、价值和/或成本的概念似乎存在问题。我觉得有必要对这些术语作一个非正式的描述。

a*使用的简单公式是f=g+h,其中

g是当前计算的从起始节点到当前节点的旅行成本。因此,对于起始节点,g value应该是0,从start node可以到达的任何节点的g值应该是1(我的假设是,从一个节点到一个相邻的节点旅行),我想强调这里的“当前”术语,因为在算法运行期间,节点的g value可能会发生变化。

h是成本的启发式部分,表示从当前节点到最终节点的成本。与G部分不同,一个节点的H值根本不会改变(好吧,我有一个疑问,这里可能有这样一个启发式的?,您的不会,让我们继续),它应该只计算一次。您的实现似乎使用了曼哈顿距离作为启发式,这绝对是此类图的最佳启发式。但要注意,我的朋友,这里似乎也有一个小问题:差异的绝对值应该单独考虑,然后再加以总结。

f是这些值的总和,表示从当前节点传递解决方案的可能成本(假设您的图形和启发式算法,任何计算出的f值应该等于或小于实际成本,这是好的)。

有了这些,我就可以使用这样的搜索节点:

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,因此不会生成新节点。

最后一件事是,当我写完这些东西后,我意识到了。您说,对于给定的任何输入,您的实现都在计算相同的结果。如果你提到的输入是障碍节点,那么大多数情况下,不管它是什么实现,它都会找到相同的距离,因为它在寻找尽可能短的距离。在下面的图片中,我试图解释这一点。

alt text

Shaggy Frog 14 年前

下面是我的代码,似乎没有不管我输入了什么值,它都会总是返回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值。记住h(x)<=d(x,y)+h(y),并为每个节点扩展计算它。