¿Qué es un algoritmo para minimizar algunas distancias D entre N elementos?

Question

Un compañero de clase imprimió un esquema de una base de datos para la clase, el tipo de líneas que representan las relaciones entre tablas. Sin embargo, sus líneas se cruzaron por todo el lugar y se veía fea.

Así que me puse a pensar en una manera de mover las mesas para minimizar la distancia total de la línea, y no podía pensar en una manera de hacerlo, que no sea sólo mover a todos en uno encima del otro. Así que, básicamente: Dada N elementos en algunas coordenadas 2D espacio y una cierta cantidad de conexiones entre pares de dichos elementos, cómo se mueven los elementos de forma que la distancia total entre pares es mínima, pero que no hay distancia es menor que S? (De modo que las tablas no serían demasiado juntos) ¿Hay algún algoritmo para esto?

(me di cuenta de que la distancia total más corta no necesariamente va a hacer el diseño menos feo;. Líneas aún podría cruz Sin embargo, el diseño de la mesa es justo lo que me hizo pensar)

Answer 1

Algunos consejos:

http://en.wikipedia.org/wiki/Graph_drawing

http://en.wikipedia.org/wiki/Force-based_algorithms

diagrama de esquema de base de datos es un caso de gráfico (o podría ser el árbol dependiendo de su esquema).

Saludos