algorithm - racionales - puntos en el plano cartesiano

Algoritmo para la ordenación de puntos cartesianos.

Question

Tengo pocos puntos cartesianos de la forma: (x, y)
donde x e y ambos son enteros no negativos.

Por ejemplo
(0,0), (1,1), (0,1)

Necesito un algoritmo para arreglar los puntos anteriores.
De tal manera que ir de un punto a otro.
cambia x o y por 1.

En otras palabras, me gustaría evitar
movimiento diagonal

Así, los puntos mencionados anteriormente se ordenarán como:
(0,0), (0,1), (1,1).

Similarmente para (0,0), (1,1), (0,2)
No hay tal arreglo posible.

No estoy seguro de como llamarlo
pero yo lo llamaría orden de manhattan .

¿Alguien puede ayudar?

Answer 1

¿Qué tal una rutina de REXX recursiva de fuerza bruta ... Pruebe todos los caminos posibles e imprima aquellos que funcionan?

/* 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 

Ejemplo de sesión:

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

Sin embargo, no intentes esto con algo grande, ¡podría llevar mucho tiempo! Pero entonces la pregunta nunca mencionó nada acerca de ser una solución óptima.

Answer 2

Esto podría simplificarse al minimizar la distancia entre cada punto consecutivo. Pasar de (0,0) a (0,1) es simplemente 1 unidad, pero de (0,0) a (1,1) es en realidad sqrt (2). Por lo tanto, si organiza los puntos en un gráfico y luego realiza un recorrido de recorrido total mínimo (recorrido), debería organizarlos correctamente.

Edición: si nunca desea un paso que sea mayor que 1, simplemente no agregue ningún borde que sea mayor que 1. El recorrido aún funcionará correctamente e ignorará cualquier ruta que requiera un movimiento> 1.

Edición 2: para aclarar aún más, puede utilizar cualquier algoritmo de selección de bordes que desee. Si está de acuerdo con que se mueva 2 espacios, siempre que el espacio no sea diagonal, puede optar por poner un borde entre (0,2) y (0,4). El algoritmo de distancia mínima todavía funcionará. Simplemente coloque los bordes de una manera inteligente, y puede utilizar cualquier número de criterios de selección para determinar el resultado.

Answer 3

Piense en ello como un gráfico en el que cada nodo tiene como máximo cuatro aristas. Luego haz la búsqueda de profundidad / amplitud.

Answer 4

Puedes construir una gráfica con los vértices que son tus puntos y los bordes como pasos válidos.

Lo que estás buscando es una ruta hamiltoniana para este gráfico. Esto, en su forma general, es un problema NP-completo, lo que significa que no hay una solución eficiente conocida (es decir, que se adapte bien al número de puntos). Wikipedia describe un algoritmo aleatorio que es "rápido en la mayoría de los gráficos" y podría ser de utilidad:

Comience desde un vértice aleatorio y continúe si hay un vecino no visitado. Si no hay más vecinos no visitados, y la ruta formada no es Hamiltoniana, elija un vecino de manera uniforme al azar, y gire utilizando ese vecino como un pivote. (Es decir, agregue un borde a ese vecino y elimine uno de los bordes existentes de ese vecino para no formar un bucle). Luego, continúe con el algoritmo en el nuevo extremo de la ruta.

Sin embargo, podría existir una solución más eficiente para esta situación particular.

Answer 5

Si está buscando un arreglo que no repita vértices:

Lo que parece que estás buscando es una ruta hamiltoniana en un gráfico de cuadrícula.

Se sabe que esto es NP-Completo para los gráficos de cuadrícula generales, consulte Rutas de Hamilton en los gráficos de cuadrícula .

Por lo tanto, probablemente pueda probar suerte con cualquiera de los algoritmos aproximados / heurísticos / etc. conocidos por Hamiltonian Path / Euclidean Travelling Problem Salesman Problem.

Si está buscando un arreglo que se pueda repetir, pero desea el número mínimo de puntos en el arreglo:

Esto es de nuevo NP-Complete El problema anterior puede reducirse a él. Esto se debe a que el recorrido mínimo posible tiene n vértices si y solo si el gráfico tiene una ruta hamiltoniana.

Si solo buscas un arreglo de puntos,

Entonces todo lo que necesita hacer es verificar si el gráfico está conectado. Si no está conectado, no puede haber tal disposición.

Puedes hacer una primera búsqueda en profundidad para darse cuenta de eso. La primera búsqueda en profundidad también le proporcionará dicha disposición en caso de que el gráfico esté conectado.

Si desea algo más cercano a lo óptimo (pero en un tiempo razonablemente rápido), probablemente pueda usar algoritmos de aproximación para el problema del vendedor ambulante euclidiano.

Answer 6

Una forma de hacerlo es crear dos listas ordenadas de las coordenadas. Una ordenada por x y otra ordenada por y. Entonces, recursivamente encuentra una solución.

Código que viene (no estoy seguro de qué idioma todavía; ¿quizás pseudocódigo?) ... Editar: no importa, ya que mi respuesta no es tan buena como algunas de las demás.