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

Вы можете построить граф, вершины которого будут вашими точками, а ребра - допустимыми шагами.

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

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

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

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

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

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

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

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

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

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

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