java - A* 搜索实现

Question

我正在尝试在 Java 中实现 A* 搜索算法来查找给定迷宫的路径。迷宫具有起始状态和目标状态，并且可能包含障碍物。

这是我解决给定迷宫的代码:

  public Solver(Maze maze) 
  {

  explored = new HashSet<Square>(); // Set of squares that A* has investigated
  path = new ArrayList<Square>(); // List of squares to the goal
  Square currentSquare = maze.getStart();
  Square goalSquare = maze.getGoal();

  while (currentSquare.equals(goalSquare) != true)
  {
      System.out.println("Im here");


      // Calculate each direction from the current node
      Square left = new Square(currentSquare.getRow(), currentSquare.getColumn()         - 1);
      Square right = new Square(currentSquare.getRow(), currentSquare.getColumn() + 1);
      Square top = new Square(currentSquare.getRow() - 1, currentSquare.getColumn());
      Square bottom = new Square(currentSquare.getRow() + 1, currentSquare.getColumn());

      // Check if each direction is blocked. If it is, we cant go there.
      List<Square> possibilities = new ArrayList<Square>();

      if (maze.isBlocked(left) != true && path.contains(left) != true)
      {
          possibilities.add(left);
      }
      if (maze.isBlocked(right) != true && path.contains(right) != true)
      {
          possibilities.add(right);
      }
      if (maze.isBlocked(top) != true && path.contains(top) != true)
      {
          possibilities.add(top);
      }
      if (maze.isBlocked(bottom) != true && path.contains(bottom) != true)
      {
          possibilities.add(bottom);
      }

      // find which square we should go to next
      Square choice = currentSquare;
      int choicegx =  1000;//path.size();
      int choicehx = 1000;//Math.abs(goalSquare.getRow() - choice.getRow()) + Math.abs(goalSquare.getColumn() - choice.getColumn());
      int choicefx = 1000;//choicegx + choicehx;
      for (Square possibility : possibilities)
      {
          int fx = 0;
          int gx = 0;
          int hx = 0;

          // Calculate gx (distance traveled)
          gx = path.size();

          // Calculate hx (Manhatten distance)
          hx = Math.abs(goalSquare.getRow() - possibility.getRow()) + Math.abs(goalSquare.getColumn() - possibility.getColumn());

          // Calculate fx
          fx = gx + hx;

          if (fx < choicefx)
          { // Possibility is a better choice based on fx
              choicefx = fx;
              choicehx = hx;
              choicegx = gx;
              choice = possibility;
              if (choice.equals(goalSquare) != true && choice.equals(maze.getStart()) != true)
              {
                  explored.add(choice);
              }
          }
          else if (fx == choicefx)
          { // Squares are tied based on fx
              if (hx < choicehx)
              { // Possibility is better based on hx
                  choicefx = fx;
                  choicehx = hx;
                  choicegx = gx;
                  choice = possibility;
                  if (choice.equals(goalSquare) != true && choice.equals(maze.getStart()) != true)
                  {
                      explored.add(choice);
                  }
              }
              else if (hx == choicehx)
              { // Squares are tied based on hx
                  if (possibility.getRow() < choice.getRow())
                  {// Possibility is better based on row
                      choicefx = fx;
                      choicehx = hx;
                      choicegx = gx;
                      choice = possibility;
                      if (choice.equals(goalSquare) != true && choice.equals(maze.getStart()) != true)
                      {
                          explored.add(choice);
                      }
                  }
                  else if (possibility.getRow() == choice.getRow())
                  { // Squares are tied based on row
                      if (possibility.getColumn() < choice.getColumn())
                      { // Squares are tied based on column
                          choicefx = fx;
                          choicehx = hx;
                          choicegx = gx;
                          choice = possibility;
                          if (choice.equals(goalSquare) != true && choice.equals(maze.getStart()) != true)
                          {
                              explored.add(choice);
                          }
                      }
                  }
              }
          }
      }

      // Move to the square we have chosen and add to path
      currentSquare = choice;
      if (currentSquare.equals(goalSquare) != true)
      {
          path.add(currentSquare);
      }

  }
}

我正在尝试决定设计此部分的更好方法:

Square choice = currentSquare;
      int choicegx =  1000;//path.size();
      int choicehx = 1000;//Math.abs(goalSquare.getRow() - choice.getRow()) +     Math.abs(goalSquare.getColumn() - choice.getColumn());
      int choicefx = 1000;//choicegx + choicehx;

在本节中，我在查看要采取的方 block 选择之前确定初始效果。最初，我一直使用当前节点的 fx 来设置这些值。然而，我随后陷入了搜索从未探索比当前节点更糟糕的节点的问题。我希望始终取得进步，永远不要停在不是目标的节点上。

有什么建议吗？

Answer 1

尝试查看Priority queue 。它是一个用于“安排”您尚未访问的节点访问的结构。当访问一个节点时，可以计算从当前节点开始可以访问的所有节点的gx，然后将节点按照gx排序存储到优先级队列中值，以便具有最低 gx 的节点位于顶部。

然后从队列顶部挑选下一个要访问的节点，因此它可以是当前节点之一，但如果它的 gx 低于剩下的任何其他节点。这样你就可以随时探索当前最有趣的路径。