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