Najkrótsza ścieżka i punkty sortowania w przestrzeni dwuwymiarowej

Question

Załóżmy, że mam obiekt w przestrzeni 2-wymiarowej i zbiór punktów, których potrzebuję do odwiedzenia tego obiektu. Punkty można dodawać w dowolnym momencie, ale nie można ich usunąć.

Co chcę jest aby móc określić następny najbliższy punkt do miejsca, gdzie mój obiekt jest w O (lg (n)) w czasie, a następnie udać się do niego, a następnie określić następny najbliżej, etc ..

Prosta kolejka priorytetów nie działa w tym przypadku, ponieważ obiekt zmienia pozycję, więc kolejka musiałaby zostać zmieniona przy każdym ruchu. Wyobrażałem sobie, jak sortuję punkty w BST, ale nie jestem pewien, jak posortować dane w odniesieniu do (x, y) lub jeśli jest to nawet możliwe.

Czuję, że mogę próbować rozwiązać traveling salesman, nie zdając sobie z tego sprawy, jeśli tak, przepraszam haha.

Answer 1

Jedną z opcji jest użycie drzewa podziału przestrzeni, takiego jak drzewo czwórkowe lub drzewo k-d, do przechowywania wszystkich punktów w przestrzeni. Te struktury danych wydajnie (zwykle w podlinie) obsługują zapytania o formę "jakie są najbliższe punkty do punktu p?" Następnie można wykonać następujące czynności:

1. Utwórz drzewo partycjonowania przestrzeni dla punktów w przestrzeni.
2. Użyj drzewa, aby znaleźć punkt p najbliżej punktu początkowego.
3. Powtórz następujące czynności:
   1. Przejdź do punktu p.
   2. Usunąć p z drzewa.
   3. Ustaw p, aby był punktem najbliższym Twojej bieżącej lokalizacji.

Mam nadzieję, że to pomoże!