0

私は頭がおかしくなっているか、A* アルゴリズムを誤って実装しているようです。

以下は私のコードです。入力した値に関係なく、常に 360 が返されるようです。重要な情報が欠落していませんか? また、誰かが「はい」と尋ねる前に、これは私が受けた機械学習の課題に関連しています。

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

}

と

public class 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() { コストを返します。}

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

}

4

2 に答える 2

1

グラフは、どの解も通過してはならない障害物ノードを含む通常の長方形グリッドであると想定しています。さらに、ノードから隣接ノードへの移動は1であると想定しています。また、ヒューリスティックとしてマンハッタン距離が使用されていることに気付きました。

これらを考えると、私はあなたが誤った実装であると思います。

まず、再帰的なアプローチではなく、反復的なアプローチを使用する必要があります。グラフのサイズを考えると、それが正しい実装であれば、間違いなくStackoverflowsを取得します。

第二に、GValue、HValue、FValue、および/またはコストの概念に問題があるようです。私はこれらの用語を非公式に説明する義務があると感じています。

A*が使用する簡単な式はF=G+Hです。

Gは、開始ノードから現在のノードに移動するために現在計算されているコストです。したがって、開始ノードの場合、G値は0である必要があり、startNodeから到達可能なノードはすべてG値が1である必要があります（私の仮定では、ノードから隣接ノードに移動します）「現在」の用語を強調したいと思いますここでは、ノードのgValueがアルゴリズムの実行中に変更される可能性があるためです。

Hはコストのヒューリスティックな部分であり、現在のノードからエンドノードまでのコストを示します。G部分とは異なり、ノードのH値はまったく変化しません（ここで疑問がありますが、そのようなヒューリスティックがあるかもしれませんか？、続行しません）。1回だけ計算する必要があります。あなたの実装は、そのようなグラフに間違いなく最高のヒューリスティックであるヒューリスティックとしてマンハッタン距離を使用しているようです。しかし、私の友人に注意してください。そこにも小さな問題があるようです。差の絶対値を個別に取得してから合計する必要があります。

また、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の複雑さでこれを実装したことを覚えています。さらに、私の実装では、1回の呼び出しでそのノードのg値にアクセスして変更することでした（必要な場合）ので、再度取得するのに時間を費やすことはありません。g値が変更されても、指定された座標のノードがある場合はtrueを返していたため、新しいノードは生成されません。

これらすべてを書き終えたときに気付いた最後のこと。あなたは、あなたの実装が同じ結果を計算していると与えられたどんな入力でも言った。言及している入力が障害物ノードである場合、ほとんどの場合、実装がどのようなものであっても、可能な限り最短の距離を探しているため、同じ距離が検出されます。下の画像で私はそれを説明しようとしました。

代替テキスト

于 2010-09-18T01:32:01.027 に答える
1

以下は私のコードです。入力した値に関係なく、常に 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) であることを思い出し、ノード展開ごとに計算してください。

于 2010-09-17T23:13:43.503 に答える