Пусть у нас будет график. Когда мы удаляем ребро, создаются 2 «машины», по одному от каждой вершины ребра. когда эти 2 машины встречаются, они останавливаются. Задача состоит в том, чтобы создать остовное дерево таким образом, чтобы сумма количества автомобилей, проходящих через каждую вершину, была минимальной.
Дополнительная сложность заключается в том, что если у вершины есть n автомобилей, проезжающих из нее, то стоимость K ^ n, а не n * K.
некоторые мысли. Мы могли бы найти самые короткие аккордовые циклы в качестве начала, но положение этих аккордовых циклов, то есть касаются ли они друг друга, изменяет метрику и, следовательно, каков самый короткий цикл.
Это не минимальная проблема связующего дерева. Я хочу решить эту проблему, потому что каждая машина представляет собой переменную, а связующее дерево является наиболее эффективным способом вычисления задачи оптимизации. Когда встречаются и останавливаются 2 машины с одного края, у меня получается сокращение на одну переменную из оптимизации.
редактирование:
Процесс такой. Мы удаляем ряд ребер, чтобы сделать граф остовным деревом. Каждый удаленный край создает 2 машины, по одному на каждую вершину удаленного края, которые должны встретиться друг с другом. Мы устанавливаем путь для каждой из этих машин-близнецов. Затем мы проверяем, сколько машин (со всех удаленных нами ребер) проходит через каждую вершину. Если количество автомобилей, которые проезжают из вершины, равно n, стоимость равна K ^ n, где K - это константа. Затем мы добавляем все затраты, и это глобальные затраты, которые необходимо минимизировать.
пожалуйста, скажите мне, если что-то неясно.
https://mathoverflow.net/questions/86301/spanning-tree-that-minimizes-a-dynamic-metric