Алгоритм размещения декартовых точек

У меня мало декартовых точек вида: (x, y)
где x и y оба являются целыми неотрицательными.

Например,
(0,0), (1,1), (0,1)

Мне нужен алгоритм для упорядочивания вышеуказанных пунктов
таким образом, что переход от одного пункта к другому изменяет либо x, либо y на 1.

Другими словами, я хотел бы избежать диагональное движение.

Итак, вышеупомянутые пункты будут устроены так:
(0,0), (0,1), (1,1).

Аналогично для (0,0), (1,1), (0,2)
такой возможности не существует.

Я не уверен, что назвать его
но я бы назвал его Manhattan ordering.

Может ли кто-нибудь помочь?

Ответ 1

Если вы ищете схему, которая не повторяет вершины:

То, что вы, похоже, ищете, - это гамильтонов путь в грид-графе.

Это, как известно, NP-Complete для общих грид-графиков, см. Гамильтоновские пути в сетчатых графах.

Таким образом, вы, вероятно, можете испытать свою удачу с помощью любого из приближенных/эвристических алгоритмов /etc, известных для проблемы гамильтоновского пути/евклидова перемещающегося коммивояжера.

Если вы ищете схему, которая может повториться, но хотите минимально возможное количество точек в расположении:

Это снова NP-Complete. Вышеупомянутая проблема может быть сведена к ней. Это связано с тем, что минимально возможный ход имеет n вершин тогда и только тогда, когда граф имеет гамильтонов путь.

Если вы просто ищете какое-то расположение точек,

Затем все, что вам нужно сделать, это проверить, подключен ли граф. Если он не подключен, такой компоновки не может быть.

Вы можете сделать первый поиск глубины, чтобы понять это. Первый поиск глубины также даст вам такую компоновку в случае подключения графика.

Если вам нужно что-то ближе к оптимальному (но в достаточно быстром времени), вы, вероятно, можете использовать алгоритмы аппроксимации для проблемы евклидова перемещающегося коммивояжера.

Ответ 2

Вы можете построить граф с вершинами, являющимися вашими точками, а ребрами являются действительные шаги.

То, что вы ищете, это гамильтонов путь для этого графика. Это, в общем виде, является NP-полной проблемой, а это означает, что нет эффективного решения (т.е. Хорошо масштабируемого с количеством точек). Википедия описывает рандомизированный алгоритм, который является "быстрым на большинстве графиков" и может быть полезен:

Начните с произвольной вершины и продолжайте, если сосед не будет посещен. Если нет более невидимых соседей, и образовавшийся путь не является гамильтонианным, выбирайте соседа равномерно случайным образом и вращайте его с помощью этого соседа. (То есть, добавьте ребро к этому соседу и удалите один из существующих ребер из этого соседа, чтобы не образовать цикл.) Затем продолжите алгоритм на новом конце пути.

Более эффективное решение может существовать для этой конкретной ситуации.

Ответ 3

Подумайте об этом как о графе, где каждый node, как максимум четыре ребра. Затем выполните поиск глубины/ширины.

Ответ 4

Это может быть упрощено как минимизация расстояния между каждой последовательной точкой. Переход от (0,0) к (0,1) - это просто 1 единица, но переход от (0,0) к (1,1) является фактически sqrt (2). Поэтому, если вы упорядочиваете точки в графе, а затем выполняете простой обход минимальной общей длины (коммивояжер), он должен правильно их расположить.

Изменить: Если вам никогда не нужен шаг, который будет больше 1, просто не добавляйте никаких ребер, которые больше 1. Обход будет работать корректно и игнорировать любые пути, для которых требуется движение > 1.

Изменить 2: Чтобы уточнить, вы можете использовать любой алгоритм выбора края, который вы пожелаете. Если вы согласны с тем, что он перемещает 2 пробела, если пространство не диагонально, вы можете поместить ребро между (0,2) и (0,4). Алгоритм минимального расстояния будет работать. Просто поместите края в разумный путь, и вы можете использовать любое количество критериев выбора для определения результата.

Ответ 5

Один из способов сделать это - создать два отсортированных списка координат. Один отсортирован по x и один сортируется по y. Затем рекурсивно найдем решение.

Приход кода (не уверен, какой язык еще, может быть, псевдокод?)... Редактировать - неважно, так как мой ответ не так хорош, как некоторые из других в любом случае.

Ответ 6

Как насчет рекурсивной рутинной процедуры REXX... Попробуйте все возможное пути и распечатать те, которые работают.

/* rexx */
point. = 0  /* Boolean for each existing point */
say 'Enter origin x and y coordinate:'
pull xo yo
point.xo.yo = 1  /* Point exists... */
say 'Enter destination x and y coordinate:'
pull xd yd
point.xd.yd = 1  /*  Point exists... */
say 'Enter remaining x and y coordinates, one pair per line:'
do forever
  pull x y
  if x = '' then leave
  point.x.y = 1
end

path = ''
call findpath xo yo path
say 'All possible paths have been displayed'
return

findpath: procedure expose point. xd yd
arg x y path
if \point.x.y then return               /* no such point */
newpoint = '(' || x y || ')'
if pos(newpoint, path) > 0 then return  /* abandon on cycle */
if x = xd & y = yd then                 /* found a path */
  say path newpoint
else do                                 /* keep searching */
  call findpath x+1 y path newpoint
  call findpath x-1 y path newpoint
  call findpath x y+1 path newpoint
  call findpath x y-1 path newpoint
  end
return

Пример сеанса:

Path.rex
Enter origin x and y coordinate:
0 0
Enter destination x and y coordinate:
2 2
Enter remaining x and y coordinates, one pair per line:
0 1
1 1
2 1
1 2

 (0 0) (0 1) (1 1) (2 1) (2 2)
 (0 0) (0 1) (1 1) (1 2) (2 2)
All possible paths have been displayed

Не пробуйте это ни на что большее, хотя - может занять очень много времени! Но тогда этот вопрос никогда не упоминал ничего о том, чтобы быть оптимальным решением.