搜索点网格,仅对每个点进行一次访问

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}

现在,算法循环,直到Queue变空.在循环中,删除顶点(pop()),然后检查,然后将其邻居添加到队列中.

例如,在第一个循环中,蓝色圆圈恰好是队列中的顶点.它将从队列中删除,然后进行检查,然后生成其邻居(红色圆圈)并将其添加到队列中.

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

我不能保留以前访问过的点的列表,并在每次生成新点时检查它(具有高维度和高分辨率,例如,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. 更复杂的是存储体积的形状而不是点。这意味着记录体积表面上的每个拐点并测试每个新点是否位于该表面上。

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