wyszukiwania siatkę punktów odwiedza każdy punkt jednorazowo

Question

mam siatki (d) wymiary, wszystkie wymiary są dzielone za pomocą delta = 0,25

Przykładem tego schematu jest to postać (D o oznacza 2, a każdy wymiar znormalizowany 0-1):

Każdy punkt przecięcia oznacza 1, na przykład, temperatura w środku jest przedstawiony jako:

double[] A={0.5, 0.5}; 

Moje pytanie brzmi: Chcę przeszukać tę siatkę, zaczynając od punktu wejścia A i jego sąsiadów. Następnie kontynuuj to. Z jednym warunkiem: każdy punkt jest odwiedzany tylko raz.

Aby wyjaśnić więcej, rozważmy następujący przykład: Punktem wyjścia jest:

double[] A={0.5, 0.5}; 

tak, to jest zaznaczone, potem jej sąsiedzi są generowane i wstawiane do kolejki (kolejka jest zamawiany opiera się na funkcja f).

tutaj punkt A jest ciemne koła. Sąsiadami są zielone kółka:

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

Teraz algorytm wykonuje pętle, aż kolejka stanie się pusta. W pętli, górny punkt jest usuwany (pop()), a następnie zaznaczony, a następnie jego sąsiadów są dodawane do kolejki.

Na przykład, w pierwszej pętli, niebieskie koło stało się górny punkt w kolejce. Jest on usuwany z kolejki, a następnie sprawdzany, a następnie sąsiedzi (czerwone kółka) są generowani i dodawane do kolejki.

Problem w tym, że mój kod generuje punkty sąsiednie, nie wie, czy poprzedni punkt jest odwiedzany przed, czy nie.

i nie mogę zachować listy wcześniej odwiedzonych punktów i sprawdzać je za każdym razem, gdy generowany jest nowy punkt (z wysokimi wymiarami i wysoką rozdzielczością, np. D = 8 i delta = 0,03125, to zajmie na zawsze!)

jest to algorytm wyszukiwania:

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

I to jest algorytm do generowania sąsiadów, jest to algorytm rekurencyjny.

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

Jak już wcześniej wspomniałem, posiadanie listy wcześniej odwiedzanych punktów nie jest możliwym rozwiązaniem. Jeśli to zrobię, lista stanie się bardzo duża, gdy mam wysoką rozdzielczość i wysoką rozdzielczość. Ta lista będzie musiała być przeszukiwana liniowo za każdym razem, gdy tworzony jest punkt!

Może powinienem uporządkować tę listę w indeksie przestrzennym? Nie wiem ... Byłbym wdzięczny za twój wkład.

Answer 1

Istnieje kilka potencjalnych skrótów można rozważyć:

1. Można usunąć punkty z listy „” poprzednio odwiedzanej raz wszystkie okoliczne punkty zostały dodane. Rozumowanie jest proste: można je dodawać tylko z otaczających punktów. Oznacza to, że tylko powierzchnia odwiedzonego woluminu musi znajdować się na liście. Przy wyższych wymiarach byłoby to znaczne oszczędności.

2. Bardziej skomplikowane byłoby przechowywanie kształtu objętości niż punktów. Oznaczałoby to zapisanie każdego punktu przegięcia na powierzchni objętości i sprawdzenie, czy każdy nowy punkt znajduje się na tej powierzchni.

Pierwsza jest prostsza, ale nie tak wydajna. Proponuję zacząć od tego i zobaczyć, czy to wystarczy.

Answer 2

Nie musisz przechowywać wszystkich odwiedzonych punktów. Przechodzę dookoła i zbieram pierwszych wszystkich sąsiadów i buduję hashkey z tych punktów, aby przechowywać to w hashmapie. Następnie sprawdź wszystkie te punkty za pomocą kodu i zbierz następny krąg sąsiadów. W najgorszym przypadku zacząłeś w środku. Następnie czas obliczania skrótów jest wysoki na końcu algortihm. Aby rozwiązać ten problem, możesz najpierw zbudować klaster i przeszukać w klastrze.

Możesz zacząć od klastrowania. Utwórz układ klastra i rozpocznij wyszukiwanie w tym klastrze za pomocą powyższej metody.

Answer 3

To brzmi podobnie do problemu odnajdywania ścieżki, w którym można również analizować siatkę i nie niepotrzebnie chcieć ponownie odwiedzać węzły. Jeśli to działa, ustaw wartość boolean dla każdego odwiedzanego węzła, więc jeśli algorytm znowu się pojawi, wie, że nie musi tego sprawdzać. Spójrz na Djikstras Algorithm, aby uzyskać inspirację.