Java中的基本递归算法

Question

我试图在Java中实现基本的RRT（快速探索随机树）算法。我有一个类TreeNode，它保存了节点的x和y位置，并且在一个ArrayList中保存了它所有的子节点。在我的主程序中，我有树的根。如果我想在树中找到最近的邻居，我会调用这个代码。该方法被称为根节点为“节点”和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.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(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; 

}

Answer 1

我必须纠正我：该NEAREST_NEIGHBOUR方法有一个失败的逻辑。看：

当方法开始时，比较已收到的minAbstand与到当前评估节点的距离。并且，如果它较低，则minAbstand值为更新以便递归地限制当前子树内的搜索标准。到现在为止还挺好。

但是，兄弟子树呢？我的意思是：当当前子树被完全浏览时，当前方法调用结束，并且因此将控制返回到它自己在先前递归帧中的调用方法。 但是局部变量的值错过了（如minAbstand）。

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