Что такое алгоритм для минимизации некоторых дистанций между n элементами?

Question

Одноклассник распечатал диаграмму базы данных для класса, вид с линиями, представляющими отношения между таблицами. Тем не менее, его линии пересекли повсюду, и это выглядело уродливым.

Поэтому я должен был подумать о способе перемещения таблиц, чтобы минимизировать общее расстояние линии, и я не мог придумать способ сделать это, кроме как просто перемещения их всех друг на друга. Таким образом, в принципе: указываются n элементов на одном 2-м координатном пространстве и некоторое количество соединений между парами этих элементов, как вы перемещаете элементы, чтобы общий расстояние между парами минимально, но это расстояние меньше, чем S? (Так что таблицы не будут слишком близко друг к другу) Есть ли какой-то алгоритм для этого?

(Я понимаю, что самая маленькая общая дистанция не обязательно сделает макет менее уродливым; линии все еще могут креститься. Но макет стола - это просто то, что заставило меня думать)

Answer 1

Некоторые подсказки:

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

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

Диаграмма схемы базы данных - это случай графика (или может быть деревом в зависимости от вашей схемы).

Ваше здоровье