Points d'emballage rapproché dans l'avion?

Question

Supposons que j'ai un graphe G complet non orienté avec une distance associée à chaque arête. La signification du bord (u, v) ayant la longueur l est "les points u et v ne peuvent pas être plus proches l'un de l'autre que l." Mon but est de placer les noeuds de ce graphe dans un plan afin qu'aucune de ces contraintes de distance ne soit violée et que la coque convexe des points ait la plus petite surface totale. À titre d'exemple, supposons que j'ai un tas de composants électriques que je veux mettre sur une puce, dont chacun génère une certaine quantité d'interférences électriques. Si je mets les composants trop près l'un de l'autre, ils commenceront à interférer les uns avec les autres, rendant tout le système inutile. Compte tenu des distances minimales que chaque point doit être l'un par rapport à l'autre, quelle est la manière la plus efficace sur le plan spatial de placer les composants sur une puce?

Je ne sais pas comment commencer à y penser. Je ne sais pas non plus comment le problème pourrait se généraliser au cas de dimension supérieure (empiler les points dans un hyperplan). Est-ce que quelqu'un sait d'un bon moyen de s'attaquer à ce problème? Je suppose qu'il sera difficile de trouver l'algorithme optimal.

Answer 1

J'ai une solution optimale, mais vous ne l'aimerez pas :).

label Let nos nœuds x , x , ..., x _n. Soit B = max _{i, j < n} (dist (x _i, x _j)), où dist (x _i, X _j) est la distance minimum entre x _i et x _j.Pour chaque i, placer le nœud x _i à la position (0, i * B). Maintenant, chaque nœud est au moins B à l'écart de tous les autres, et la coque convexe a une aire de 0.

Le point réel ici est que minimiser la surface de la coque convexe seule vous donnera une solution absurde. Une mesure éventuellement meilleure serait le diamètre de la coque convexe.

Answer 2

Je ne serais pas surpris si cela s'avérait être un problème NP-difficile. Cependant, si vous êtes intéressé par un algorithme pratique qui donne des solutions décentes, je recommande de jeter un oeil à force-based graph drawing algorithms.

Voici l'idée générale (des mathématiques plus élevées apparaîtront). Il généralise à n'importe quel nombre de dimensions.

Construire une fonction f qui attribue une valeur à chaque disposition de nœud - une valeur que vous voulez minimiser. Dans votre cas, la fonction pourrait calculer la surface de la coque convexe pour une disposition donnée + une grosse pénalité pour chaque contrainte qui n'a pas été respectée. Ou il pourrait s'agir d'une fonction plus simple, qui se rapproche raisonnablement de la précédente: en bref, nous voulons que g devienne plus petit chaque fois que f devient plus petit, et vice versa. Il est bon de choisir une fonction relativement simple, car vous aurez besoin de calculer ses dérivées partielles (par rapport aux coordonnées des nœuds).

Maintenant, disons que vous avez 100 nœuds et que vous voulez les disposer en 3D. Cela signifie que vous avez 300 numéros inconnus (100 nœuds fois 3 coordonnées pour chaque nœud). Fonction f est une fonction de R à R, et idéalement, nous voulons trouver son minimum global. Plus réaliste, un minimum local suffisamment profond suffira. Il existe des algorithmes numériques bien connus pour trouver un tel minimum, par exemple: Conjugate gradient, BFGS. La bonne chose est, vous n'avez pas vraiment à les comprendre dans les détails, ces algorithmes sont mis en œuvre dans de nombreuses langues. Tout ce que vous avez à faire est de fournir une méthode de calcul f(x) et f'(x) pour tout x demandé par l'algorithme, et une mise en page initiale x₀.

Answer 3

C'est 2D bin packing problem (qui est NP dur) avec des contraintes supplémentaires. J'ai entendu recuit simulé fonctionne assez bien pour la conception de circuit/puce. Je suis actuellement looking for real-world test-data of a big bin packing problem pour Drools Planner.