У меня есть DAG, которая слабо представляет сетчатую генеалогию («семейное« дерево ») из потенциально миллионов узлов, с фиксированными 2D пространственными положениями некоторых узлов (в основном листовых или« приемных »узлов, как это бывает). Я хочу найти возможные пространственные положения для всех других узлов, чтобы длина ребер была минимизирована в соответствии с некоторой функцией (я мог бы использовать наименьшие квадраты, но в идеале я бы мог определить свою собственную функцию вероятности для длин ребер, особенно такую, которая позволяет каждому ребру иметь различный «вес»). Меня не волнуют вершины, пересекающие друг друга.
Является ли это проблемой теории / построения графов или чем-то более похожим на проблему минимизации энергии в вычислительной химии? Какие существуют алгоритмы и реализации для решения такого рода проблем компоновки?