O que é um algoritmo para minimizar algumas distâncias d entre n itens?

Question

Um colega de classe imprimiu um diagrama de um banco de dados para a classe, do tipo com linhas que representam relacionamentos entre tabelas. No entanto, suas falas cruzaram por todo o lugar e pareciam feias.

Então, eu comecei a pensar em uma maneira de mover a mesa para minimizar a distância total da linha, e não conseguia pensar em uma maneira de fazê -lo, além de apenas movê -las um no outro. Então, basicamente: dados n itens em algum espaço de coordenadas 2D e uma quantidade de conexões entre pares desses itens, como você move os itens para que a distância total entre os pares seja mínima, mas que nenhuma distância é menor que S? (para que as mesas não estivessem muito próximas) existe algum algoritmo para isso?

(Percebo que a menor distância total não tornará necessariamente o layout menos feio; as linhas ainda podem cruzar. Mas o layout da tabela é exatamente o que me fez pensar)

Answer 1

Algumas dicas:

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

http://en.wikipedia.org/wiki/force baseado_algorithms

O diagrama de esquema do banco de dados é um caso de gráfico (ou pode ser uma árvore, dependendo do seu esquema).

Felicidades