Algoritmo para organizar puntos cartesianos

Question

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

Por ej.
(0,0), (1,1), (0,1)

Necesito un algoritmo para disponer los puntos anteriores
de tal manera que va de un punto a otros
cambios ya sea x o y por 1.

En otras palabras, me gustaría evitar
movimiento diagonal.

Por lo tanto, los puntos mencionados anteriormente se organizarán como:
(0,0), (0,1), (1,1).

Similarmente para (0,0), (1,1), (0,2)
no hay tal disposición posible.

No estoy seguro acerca de cómo llamarlo
pero yo diría que es Manhattan ordenar.

¿Alguien puede ayudar?

Answer 1

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

Lo que parece estar en busca de un camino hamiltoniano en un gráfico de la red.

Esto se sabe que es NP-completo para Grid Graphs general, vea Hamilton Paths in Grid Graphs.

Probablemente pruebe suerte con cualquiera de los algoritmos aproximados/heurísticos/etc conocidos para Hamiltonian Path/Euclidean Traveling Salesman Problem.

---

Si usted está buscando un arreglo que puede repetir, pero quiere que el mínimo número posible de puntos en la disposición:

Esto es de nuevo NP-completo. El problema anterior se puede reducir a eso. Esto se debe a que la caminata mínima posible tiene n vértices si y solo si el gráfico tiene una ruta hamiltoniana.

---

Si estás en busca de un arreglo de puntos,

Entonces todo lo que tiene que hacer es comprobar si está conectado el gráfico. Si no está conectado, no puede haber tal arreglo.

Puede hacer una primera búsqueda en profundidad para descubrirlo. La primera búsqueda en profundidad también le dará esa disposición en caso de que el gráfico esté conectado.

Si quiere algo más cerca de lo óptimo (pero en un tiempo razonablemente rápido), probablemente pueda usar algoritmos de aproximación para el problema de Euclidean Traveling Salesman.

Answer 2

Esto podría simplificarse ya que se minimiza la distancia entre cada punto consecutivo. Pasar de (0,0) a (0,1) es simplemente 1 unidad, pero pasar de (0,0) a (1,1) es en realidad sqrt (2). Entonces, si organiza los puntos en un gráfico y luego realiza un recorrido mínimo de distancia total total (vendedor ambulante), debe organizarlos correctamente.

Editar: Si nunca desea un paso que sea mayor que 1, simplemente no agregue ningún borde que sea mayor que 1. El cruce seguirá funcionando correctamente, e ignorará las rutas que requieran un movimiento> 1.

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

Answer 3

Una forma de hacerlo es crear dos listas ordenadas de las coordenadas. Uno ordenado por x y uno ordenado por y. Luego, recursivamente encuentra una solución.

Viene el código (no estoy seguro de qué idioma aún, tal vez pseudocódigo?) ... Editar - no importa, ya que mi respuesta no es tan buena como algunas de las demás de todos modos.

Answer 4

Puede construir un gráfico con los vértices siendo sus puntos, y los bordes son los pasos válidos.

Lo que estás buscando es un Hamiltonian path 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, una que se adapte bien al número de puntos). Wikipedia describe un randomized algorithm que es "rápido en la mayoría de los gráficos" y podría ser de utilidad:

de inicio desde un vértice al azar, y continuar si hay un vecino no visitado.Si no hay más vecinos no visitados, y la ruta formada no es hamiltoniana, elija a un vecino uniformemente al azar, y rote usando ese vecino como 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 final de la ruta.

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

Answer 5

Piense en ello como un gráfico donde cada nodo tiene como máximo cuatro bordes. Luego haga una búsqueda de profundidad/amplitud.

Answer 6

¿Qué tal una rutina recursiva de fuerza bruta REXX ... Intente todas las posibles rutas e imprima las que funcionen. sesión

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

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 

no intenta esto en algo grande, aunque - podría tomar un tiempo muy largo! Pero luego la pregunta nunca mencionó nada acerca de ser una solución óptima.