Qu'est-ce qu'un algorithme pour minimiser des distances D entre les éléments N?

Question

Un camarade de classe a imprimé un schéma d'une base de données pour la classe, le genre avec des lignes représentant les relations entre les tables. Cependant, ses lignes croisées dans tous les sens et il semblait laid.

Je suis arrivé à penser à une façon de déplacer les tables pour minimiser la distance totale de la ligne, et je ne pouvais pas penser à une façon de le faire, autre que simplement les déplacer tous les uns sur les autres. Donc, en gros: articles Compte tenu de N sur certains 2d espace de coordonnées et un certain nombre de connexions entre les paires de ces éléments, comment pouvez-vous déplacer les éléments de telle sorte que la distance totale entre les paires est minime, mais qu'aucune distance est inférieure à S? (De sorte que les tables ne seraient pas trop proches) Y at-il un algorithme pour cela?

(je me rends compte que la distance totale la plus petite ne rendra pas nécessairement la mise en page moins laid. Lignes pourraient encore croix, mais la mise en page de table est juste ce qui me fait penser)

Answer 1

Quelques conseils:

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

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

diagramme de schéma de base de données est un cas de graphique (ou pourrait être l'arbre en fonction de votre schéma).

Vive