java - Java中的基本递归算法

我正在尝试在Java中实现基本的RRT(快速探索随机树)算法。我有一个TreeNode类，它保存节点的x和y位置，并在ArrayList中保存它具有的所有子节点。在我的主程序中，我有树的根。如果我想在树中找到最近的邻居，请调用此代码。以根节点为“node”的方式调用该方法，minAbstand为Integer.MAX_VALUE

private void NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
    if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) <= minAbstand){//normal method to find the distance
        minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
        xnearest = node;
    }
    for(int i = 0; i < node.getNodes().size(); i++){
        NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
    }
}

我以为我要遍历所有节点并找到距离最小的那个节点。使用NEAREST_NEIGHBOUR方法后，最近的邻居应保存在xnearest中。现在，我通过此方法将新节点添加到最近的节点:
xnearest.addNode(xnew)。

addNode是TreeNode类中的一个方法，该方法调用arraylist.add(node)，因此只需将节点添加到ArrayList中即可。在此之后，新节点应该是最近节点的“子节点”。然后一切都从头开始:-创建随机节点，-将最近的节点查找到随机节点，-将随机节点添加到最近的节点，...
但是实际上这不是发生的事情。

在突出显示的区域中，您可以看到它没有选择距离最小的节点。我在那里做错了什么？

整个代码:

    private void doRRT(Canvas canvas, PaintEvent e, int K, int deltaT){
      for(int i = 0; i < K; i++){
          xrand = new TreeNode(new Random().nextInt(canvas.getSize().x * 2) - 500, new Random().nextInt(canvas.getSize().y * 2) - 300);

          NEAREST_NEIGHBOUR(xrand.getxPos(), xrand.getyPos(), xstart, Integer.MAX_VALUE);

          NEW_STATE(xrand.getxPos(), xrand.getyPos(), deltaT);

          e.gc.drawRectangle(xnearest.getxPos() - 1, xnearest.getyPos() - 1, 2, 2);
          e.gc.drawLine(xnearest.getxPos(), xnearest.getyPos(), xnew.getxPos(), xnew.getyPos());
      }
  }

  private void NEW_STATE(int xrand, int yrand, int deltaT) {
      int nearx = xnearest.getxPos(), neary = xnearest.getyPos();
      if(Math.sqrt(Math.pow(nearx - xrand, 2) + Math.pow(neary - yrand, 2)) > deltaT){
          float faktor = (float) (Math.sqrt(Math.pow(nearx - xrand, 2) + Math.pow(neary - yrand, 2)) / deltaT);
          xnew = new TreeNode((int) (nearx + (xrand - nearx)/ faktor), (int) (neary + (yrand - neary)/ faktor));
      } else {
          xnew = new TreeNode(xrand, yrand);
      }
      xnearest.addNode(xnew);
  }

private void NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
    counter2++;
      if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) < minAbstand){
          minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
          xnearest = node;
      }
      for(int i = 0; i < node.getNodes().size(); i++){
          NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
      }
  }

和TreeNode类:

TreeNode(int x, int y){
    xPos = x;
    yPos = y;
    nodes = new ArrayList<TreeNode>();
}

public ArrayList<TreeNode> getNodes() {
    return nodes;
}

public int getxPos() {
    return xPos;
}

public int getyPos() {
    return yPos;
}

public void addNode(TreeNode node){
    nodes.add(node);
}

解决方案？

这是现在吗？递归真的很棘手

private int NEAREST_NEIGHBOUR(int xrand, int yrand, TreeNode node, int minAbstand) {
  if((Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2))) < minAbstand){
      minAbstand = (int) Math.sqrt(Math.pow(node.getxPos()-xrand, 2) + Math.pow(node.getyPos()-yrand, 2));
      xnearest = node;
  }
  for(int i = 0; i < node.getNodes().size(); i++){
      minAbstand = NEAREST_NEIGHBOUR(xrand, yrand, node.getNodes().get(i), minAbstand);
  }
  return minAbstand;

}

最佳答案

我必须纠正自己:NEAREST_NEIGHBOUR方法的逻辑失败。看:

方法开始时，将接收到的minAbstand与到当前评估节点的距离进行比较。并且，如果它较低，则更新minAbstand值，以便将搜索条件递归地限制在当前子树中。到目前为止，一切都很好。

但是， sibling 子树呢？我的意思是:当完全浏览了当前子树时，当前方法调用结束，因此将控件返回给调用方法，该方法本身在先前的递归框架中。 但是局部变量的值丢失了(如minAbstand)。

您需要返回minAbstand作为NEAREST_NEIGHBOUR的返回值，并在每次递归调用时对其进行更新。