Сначала пройдите из точки А во все оставшиеся точки через ближайшую соседнюю точку
У меня есть несколько точек, представленных на картинке. Расстояние между двумя ближайшими точками по вертикали (между A а также B, или же B а также C, или же D а также E и т. д.) distance_y, Расстояние между двумя ближайшими точками по горизонтали (между A а также Dи т. д.) distance_x,
Предположим, что:
distance_y < distance_x < 2*distance_y
distance_x
A <-------------> D <-------------> G
|
distance_y |
|
B <-------------> E <-------------> H
-
C <-------------> F <-------------> I
Я формулирую расстояние между двумя любыми точками следующим образом:
Distance(point P1, point P2) = m * distance_x + n * distance_y
Например, для точки A а также B, m = 0 а также n = 1;
Вопрос в том, с какой точки Pкак мне сначала пройти через все оставшиеся точки через ближайших соседей (т.е. в порядке убывания расстояния вдали от точки P)?
Я не хочу рассчитывать все расстояние от других точек до P а затем отсортировать эти точки в порядке убывания расстояния от P потому что это отнимает много времени. Я хочу найти алгоритм, который может быстро оценить положение соседа, не вычисляя положение дальнейших точек.
Например, из точки D, следующие пункты будут
E (m= 0, n = 1),
A (m= 1, n = 0),
G (m= 1, n = 0),
F (m =0, n = 2),
B (m= 1, n = 1),
H (m= 1, n = 1),
C (m= 1, n = 2),
I (m= 1, n = 2).
Как я могу определить порядок m а также n для поиска ближайших соседей?
Решение
Не уверен, что понял, но выглядит как приложение Dijkstra algoruthm:
http://en.wikipedia.org/wiki/Dijkstras_algorithm
Другие решения
У вас есть только 2 вида соединений: длинные и короткие.
Сохраните свой график в виде списка смежности, где каждый узел имеет 2 контейнера, а не список узлов. Первый контейнер имеет все короткие (y) расстояние между узлами, а у второго длинное (x) узлы расстояния.
Выполнить BFS Поиск на графике, единственная разница в том, что у вас будет две очереди поиска.
От начального узла: вы добавляете контейнер на короткое расстояние в первую очередь и длинный путь во вторую очередь. Вы извлекаете контейнер из первой очереди, просматриваете его элементы и группируете все контейнеры на короткие расстояния каждого узла в один и добавляете их в первую очередь и на большое расстояние (также все сгруппированные вместе) во второй, а затем извлекаете контейнер из во второй очереди и для каждого узла в этом контейнере вы добавляете контейнеры на короткие расстояния вместе в большую, а затем в большую очередь во вторую очередь и большое расстояние в первую очередь. Затем вы снова выдвигаете контейнер из первой очереди …
Подводя итог: вы поп по одному в каждой очереди. В результате получается контейнер с узлами, вы проходите через каждый узел, собираете все контейнеры на короткие расстояния и добавляете их в очередь, из которой вы извлекли контейнер, то же самое происходит и с контейнерами на большие расстояния, только когда они добавляются в первый. очередь.
Единственное, что с этим алгоритмом n долго всегда лучше n+1короткая.
Вот так будет выглядеть обход, начиная с C, бамбук рядом с каждым узлом показывает порядок их достижения.
A5---B2---C0---D2---E5
| | | | |
F8---G4---H1---I4---L8
| | | | |
M10--N7---O3---R7---P10
| | | | |
W11--Y9---X6---T9---S11