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

Question

У меня есть несколько декартовых точек вида: (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)
такое расположение невозможно.

Я не уверен, как это назвать
, но я бы назвал это Манхэттенский заказ .

Кто-нибудь может помочь?

Answer 1

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

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

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

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

---

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

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

---

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

Как насчет грубой рекурсивной процедуры 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

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

Answer 6

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

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