java - 搜索点网格，每个点只访问一次

Question

我有一个 (d) 维度的网格，所有维度都使用 delta = 0.25 进行分区

这个网格的一个例子是这个图(这里的d是2，每个维度都归一化为0-1):

每个交点代表1个点，例如中间的点表示为:

double[] A={0.5, 0.5};

我的问题是:我想搜索这个网格，从输入点 A 及其邻居开始。然后继续这样做。有一个条件:每个点只被访问一次。

为了更清楚地说明，请考虑以下示例:出发点是:

double[] A={0.5, 0.5};

因此，首先检查 A，然后生成其邻居并将其插入队列(队列根据函数 f 排序)。

这里A点就是黑眼圈。它的邻居是绿色圆圈:

{0.25, 0.25}
{0.25, 0.5}
{0.25, 0.75}
..
..
..
{0.75, 0.75}

现在，算法循环直到队列变空。在循环中，顶部点被移除 (pop())，然后检查，然后它的 neighbors 被添加到队列中。

例如，在第一个循环中，蓝色圆圈恰好是队列中的顶端点。它从队列中移除，然后检查，然后生成它的邻居(红色圆圈)并添加到队列中。

这里的问题是，我生成邻居点的代码不知道之前是否访问过前一个点。

而且我无法保留以前访问过的点的列表，并且每次生成新点时都检查它(具有高维度和高分辨率，例如 d=8 和 delta= 0.03125，这将永远存在!)

这是搜索算法:

public void search(int d, double delta, double[] inpoint)
{
    Queue queue = new Queue();
    queue.push(inpoint);

    while( !queue.isEmpty() )
    {
        // remove top point from Queue
        double[] a = queue.pop();

        // Check point a and do some calculations
        // ;;;;;;;;;;;;;;;;

        // Generate neighbours of current point:
        ArrayList<double[]> neighbors = new ArrayList<double[]>();
        nextMoves(a, new double[d], delta, d, neighbors);

        // For each point in neighbors, push to Queue:
        for( int i=0 ; i < neighbors.size(), i++ )
            queue.push(neighbors.get(i));
    }
}

这是生成邻居的算法，它是一个递归算法。

public static void nextMoves(double[] inatt, double[] outatt, double delta, int d, ArrayList<double[]> neighbors) 
{
    if( d == inatt.length )
    {
        if( !outOfBound(outatt,d) )
        {
            moves.add(outatt);   
        }
    }
    else
    {
       // first case: add delta:
       outatt[d] = inatt[d]+delta; 
       nextMoves( inatt, outatt, delta, d+1, moves);

       // second case: subtract delta:
       outatt[d] = inatt[d]-delta; 
       nextMoves( inatt, outatt, delta, d+1, moves);

       // third case: no change:
       outatt[d] = inatt[d]; 
       nextMoves( inatt, outatt, delta, d+1, moves);
    }
} 

正如我之前提到的，保留一个以前访问过的点的列表不是一个可行的解决方案。如果我这样做，那么当我具有高维度和高分辨率时，列表会变得非常大。并且每次创建点时都必须线性搜索此列表!

也许我应该在空间索引中组织这个列表？我不知道...非常感谢您的意见。

Answer 1

您可以考虑几个潜在的捷径:

1. 一旦添加了所有周围的点，您就可以从“以前访问过的”列表中删除点。推理很简单:它们只能从周围的点相加。这意味着只有被访问体积的表面需要在列表中。在更高的维度上，这将节省大量资金。

2. 更复杂的是存储体积的形状而不是点。这意味着记录体积表面上的每个拐点并测试每个新点是否在该表面上。

第一个更简单但效率不高。我建议从那开始，看看它是否足够。