java - Searching a grid of points, visting each point once only -
i have grid of (d) dimensions, dimensions partitioned using delta = 0.25
an example of grid figure (d here 2, , each dimension normalized 0-1):
each intersection represents 1 point, example, point in middle represented as:
double[] a={0.5, 0.5};
my question is: want search grid, starting input point , neighbors. continue doing that. 1 condition: each point visited once.
to clarify more, consider example: starting point is:
double[] a={0.5, 0.5};
so, checked first, neighbours generated , inserted queue (the queue ordered based on function f).
here point dark circle . neighbors green circles:
{0.25, 0.25} {0.25, 0.5} {0.25, 0.75} .. .. .. {0.75, 0.75}
now, algorithm loops until queue becomes empty. in loop, top point removed (pop()), checked, neighbors added queue.
for example, in first loop, blue circle happened top point in queue. removed queue, checked, neighbors (red circles) generated , added queue.
the problem here is, code generates neighbors points, not know if previous point visited before or not.
and cannot keep list of visited points, , check every time new point generated ( high dimensions , high resolution e.g., d=8 , delta= 0.03125, take ever!)
this search algorithm:
public void search(int d, double delta, double[] inpoint) { queue queue = new queue(); queue.push(inpoint); while( !queue.isempty() ) { // remove top point queue double[] = queue.pop(); // check point , calculations // ;;;;;;;;;;;;;;;; // generate neighbours of current point: arraylist<double[]> neighbors = new arraylist<double[]>(); nextmoves(a, new double[d], delta, d, neighbors); // each point in neighbors, push queue: for( int i=0 ; < neighbors.size(), i++ ) queue.push(neighbors.get(i)); } }
and algorithm generating neighbors, recursive algorithm.
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); } }
as mentioned before, keeping list of visited points not possible solution. if this, list becomes large when have high dimensionality , high resolution. , list have searched linearly each time point created!
perhaps should organize list in spatial index? don't know... appreciate input.
there couple of potential shortcuts consider:
you remove points 'previously visited' list once surrounding points have been added. reasoning simple: can added surrounding points. means surface of visited volume needs in list. @ higher dimensions substantial saving.
more complicated store shape of volume rather points. mean recording each inflection point on surface of volume , testing if each new point on surface.
the first simpler not efficient. i'd suggest starting , seeing if it's enough.
Comments
Post a Comment