У меня есть граф DAC, реализованный на Python, где мне нужно подключить X-листья к корню. Есть ли способ рассчитать количество и расположение внутренних узлов для оптимального пути?
Я бы сравнил это с вычислением оптимального проекта дороги в Поселенцах, где у вас есть X зданий, которым нужно отправить свои продукты вцентральное хранилище.
Я сделал простую реализацию, используя A *, которая соединяет все листья, но если посмотреть на стоимость (листьев и ребер), то она, конечно, не оптимальна.