Базовый рекурсивный алгоритм в Java

Question

Я пытаюсь реализовать базовый алгоритм RRT (быстрое исследование случайного дерева) в Java. У меня есть класс 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 ближайший сосед shoudl будет сохранен в 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; 

}

Answer 1

Я должен исправить себя: Метод NEAREST_NEIGHBOUR имеет неудовлетворительную логику. Посмотрите:

При запуске метода сравнивается полученный minAbstand с расстоянием до текущего оцениваемого узла. И, если он ниже, значение minAbstand будет обновлено, чтобы рестриктивно ограничивать критерий поиска в текущем поддереве. Все идет нормально.

Но, а как насчет сестринских поддерев? Я имею в виду: когда текущее поддерево полностью просматривается, текущий вызов метода заканчивается и, таким образом, возвращает элемент управления вызывающему методу, который сам по себе, в предыдущем рекурсивном фрейме. Но значения локальных переменных не пройдены (например, minAbstand).

Вам нужно вернуть minAbstand в качестве возвращаемого значения NEAREST_NEIGHBOUR и обновлять его каждый раз, когда он рекурсивно вызывается.