Tìm kiếm một mạng lưới các điểm, cách truy cập vào từng điểm một lần duy nhất

Question

Tôi có một mạng lưới các (d) kích thước, tất cả các khía cạnh được phân chia bằng đồng bằng = 0,25

Một ví dụ về lưới này là con số này (d đây là 2, và mỗi chiều là bình thường 0-1):

mỗi ngã tư đại diện cho 1 điểm, ví dụ, điểm ở giữa được biểu diễn dưới dạng:

double[] A={0.5, 0.5}; 

Câu hỏi của tôi là: Tôi muốn tìm kiếm lưới này, bắt đầu từ điểm đầu vào A và các điểm lân cận của nó. Sau đó tiếp tục làm điều đó. Với một điều kiện: Mỗi điểm chỉ được truy cập một lần.

Để làm rõ hơn, hãy xem xét ví dụ sau: Điểm khởi đầu là:

double[] A={0.5, 0.5}; 

Vì vậy, A sẽ được kiểm tra đầu tiên, sau đó các nước láng giềng được tạo ra và chèn vào một Queue (hàng đợi được sắp xếp dựa trên một hàm f).

Đây điểm A là vòng tròn tối. Những người hàng xóm của nó là các vòng tròn màu xanh lá cây:

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

Bây giờ, thuật toán lặp lại cho đến khi Hàng đợi trở nên trống. Trong vòng lặp, điểm trên cùng bị xóa (pop()), sau đó được chọn, sau đó được chọn hàng xóm được thêm vào Hàng đợi.

Ví dụ, trong vòng lặp đầu tiên, vòng tròn màu xanh đã xảy ra với là điểm hàng đầu trong Queue. Nó được lấy ra khỏi hàng đợi, sau đó kiểm tra, sau đó hàng xóm của nó (vòng tròn màu đỏ) được tạo ra và thêm vào hàng đợi.

Vấn đề ở đây là, mã của tôi tạo điểm lân cận, không biết liệu điểm trước đó có được truy cập trước đó hay không.

và tôi không thể lưu giữ danh sách các điểm đã truy cập trước đó và kiểm tra điểm mỗi lần tạo điểm mới (với kích thước cao và độ phân giải cao, d = 8 và delta = 0.03125, sẽ mất bao giờ!)

Đây là thuật toán tìm kiếm:

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)); 
    } 
} 

Và đây là các thuật toán để tạo ra những người hàng xóm, nó là một thuật toán đệ quy.

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); 
    } 
} 

Như tôi đã đề cập trước đây, việc lưu danh sách các điểm truy cập trước đây không phải là giải pháp khả thi. Nếu tôi làm điều này, danh sách trở nên rất lớn khi tôi có chiều cao và độ phân giải cao. Và danh sách này sẽ phải được tìm kiếm theo đường thẳng mỗi khi một điểm được tạo!

Có lẽ tôi nên tổ chức danh sách này trong chỉ mục không gian? Tôi không biết ... Tôi sẽ đánh giá cao ý kiến ​​của bạn.

Answer 1

Có một vài phím tắt tiềm năng bạn có thể xem xét:

1. Bạn có thể loại bỏ các điểm từ danh sách 'truy cập trước đó' của bạn một lần tất cả các điểm xung quanh đã được thêm vào. Lý do rất đơn giản: chúng chỉ có thể được thêm vào từ các điểm xung quanh. Điều này có nghĩa là chỉ có bề mặt của khối lượng truy cập cần phải có trong danh sách. Ở kích thước cao hơn, đây sẽ là một tiết kiệm đáng kể.

2. Phức tạp hơn là lưu trữ hình dạng khối lượng thay vì các điểm. Điều này có nghĩa là ghi lại từng điểm uốn trên bề mặt khối lượng và kiểm tra nếu mỗi điểm mới nằm trên bề mặt đó.

Cách thứ nhất đơn giản nhưng không hiệu quả. Tôi muốn đề nghị bắt đầu với điều đó và xem nếu nó là đủ.

Answer 2

Bạn không phải lưu trữ tất cả các điểm truy cập. Đi xung quanh và thu thập đầu tiên tất cả các nước láng giềng và xây dựng một hashkey ra khỏi điểm này để lưu trữ này trong một hashmap. Sau đó xác nhận tất cả các điểm này với mã của bạn và thu thập vòng tròn tiếp theo của hàng xóm. Trong trường hợp xấu nhất bạn bắt đầu ở giữa. Sau đó, tính toán của hashkeys cao ở cuối algortihm. Để giải quyết vấn đề này, bạn có thể xây dựng cụm và tìm kiếm trong cụm trước.

Bạn cũng có thể bắt đầu với phân cụm. Xây dựng bố cục cụm và bắt đầu tìm kiếm trong cụm này với phương pháp vòng tròn ở trên.

Answer 3

Điều này nghe có vẻ tương tự như vấn đề về đường dẫn nơi bạn cũng có thể phân tích lưới và không cần thiết phải truy cập lại các nút. Nếu nó hoạt động cho bạn, hãy đặt một boolean trên mỗi nút được truy cập, vì vậy nếu thuật toán xảy ra trên nó một lần nữa, nó biết nó không cần phải kiểm tra nó. Nhìn vào Djikstras Algorithm để lấy cảm hứng.