1

我正在尝试以递归深度优先方式找到最近的邻居。在达到这一点之前涉及许多元素,为了简单起见,我只包括了我目前遇到问题的部分。

我的想法是根据某个阈值距离找到给定点的最近邻居,我决定将过程 int 分为两种方法。一个真正找到最近邻居是否存在的方法,以及其他方法来一遍又一遍地递归调用该函数。

我有带有双值的 ArrayList,我将其视为点...如果返回 0.0,则意味着我没有找到最近的邻居(想知道我是否真的使用 Object,一旦我清理逻辑可能会这样做)。

/**
 * Find the nearest neighbor based on the distance threshold.
 * TODO:
 * @param currentPoint current point in the memory.
 * @param threshold dynamic distance threshold.
 * @return return the neighbor.
 */

private double nearestNeighbor(double currentPoint) {

    HashMap<Double, Double> unsorted = new HashMap<Double, Double>();
    TreeMap<Double, Double> sorted = null; 
    double foundNeighbor = 0.0;

    for (int i = 0; i < bigCluster.length; i++) {
        if (bigCluster[i] != 0.0 && bigCluster[i] != currentPoint) {
            double shortestDistance = Math.abs(currentPoint - bigCluster[i]);
            if (shortestDistance <= this.getDistanceThreshold())
                unsorted.put(shortestDistance, bigCluster[i]);
        }
    }
    if (!unsorted.isEmpty()) {
        sorted = new TreeMap<Double, Double>(unsorted);
        this.setDistanceThreshold(avgDistanceInCluster());
        foundNeighbor = sorted.firstEntry().getValue();
        return foundNeighbor;
    } else {
        return 0.0;
    }
}

这是我的方法,我计划以递归 dfs 方式调用上述方法。

/**
 * Method will check if a point belongs to a cluster based on the dynamic 
 * threshold.
 */
public void isBelongToCluster(double point) {

    for (int i = 0; i < tempList.size(); i++) {

        double aPointInCluster = point;
        cluster.add(aPointInCluster);
        isVisited[i].visited = true;
        double newNeighbor = nearestNeighbor(aPointInCluster);
        if (newNeighbor != 0.0) {
            cluster.add(newNeighbor);
            if (i + 1 != tempList.size() && (isVisited[i].visited != true)) {
                isBelongToCluster(newNeighbor);
            }
        }

    }
    for (int i = 0; i < cluster.size(); i++) {
        if (cluster.get(i) != 0.0)
            System.out.println("whats in the cluster -> " + cluster.get(i));
    }
}

我正在努力的是递归深度优先搜索。除此之外,我的访问者实现看起来不正确。

这就是我试图处理访客的方式

public class VisitedPoint {

    public double point;
    public boolean visited;

    public VisitedPoint(double pointToCheck) {
        point = pointToCheck;
        visited = false;
    }
}

然后我会创建一个 VisitedPoint 对象,private VisitedPoint[] isVisited;但是当我在 isBelongTo() 方法中使用它时,我得到一个空指针异常。

提前感谢您的帮助。

4

2 回答 2

1

查看用于求解最近邻的最佳性能关键算法。我希望它有所帮助。

于 2009-11-04T23:00:42.260 回答
1

感觉就像您正在使这变得更加复杂。

如果我理解正确,您有一系列一维点数据。您正在尝试将这些点分组,在一个组中,任何一对点之间的距离都小于“阈值距离”。

我将从对一维点数据进行排序开始。从第一个元素开始,我为该元素创建了一个集群对象。如果第一个元素和第二个元素之间的增量小于阈值,我将它添加到集群中。现在我看看第二个和第三个之间的增量;沿着排序的数据前进,并创建一个新的集群,当我发现一个大于阈值的增量时将事物分类,直到我在数据的末尾。

这能解决问题还是我错过了一个关键要求?

于 2009-11-04T18:27:46.233 回答