Минимальное остовное дерево для пар смежных ребер

avatar
Ashton Six
9 августа 2021 в 01:39
147
1
4

Для некоторого графа существует стоимость, связанная с каждой парой смежных ребер. Я надеюсь найти такой подграф, в котором все точки связаны, а стоимость минимальна (минимальное остовное дерево).

graph, with edges AB, BC, CD, and DA. ABC costs 15, BCD costs 13, CDA costs 63, DAB costs 81

Для приведенного выше примера решение будет включать ребра AB, BC и CD, но не DA, избегая дорогостоящих троек CDA и DAB и получая оценку 28 (вес ABC + BCD).

Чтобы мотивировать этот вопрос, давайте представим, что мы проектируем дорожную сеть между местами, и всякий раз, когда автомобиль поворачивает на крутом повороте, он замедляется. Создание идеальной сети с небольшим количеством крутых изгибов может выиграть от того, что мы примем во внимание триплеты узлов.

Графы, к которым я собираюсь применить этот алгоритм, будут иметь от 5 000 до 20 000 узлов и от 15 000 до 80 000 ребер. Предположительно функция будет такого типа или похожей:

(
  nodes: [T],
  edges: [(int, int)],
  distance: (a: T, b: T, c: T) => float
) => [(int, int)]

Где b соединен с обоими a и c, но a и c не обязательно связаны.

Какой алгоритм решает эту задачу?

Спасибо за любую помощь, которую вы можете оказать.

Источник
Richard
9 августа 2021 в 04:05
1

Уместно ли думать о вашей проблеме как о попытке найти MST графа со взвешенными ребрами и стоимостью вершин, пропорциональными углу между этими ребрами? Если да, то как определяется угол, если к вершине примыкает много ребер?

Ashton Six
9 августа 2021 в 04:51
0

@Richard Хм ... если для любой пары смежных ребер distance(a,b,c) = edgeCost(a,b) + edgeCost(b,c) + vertexCost(a,b,c), то для вершины V с 3 смежными вершинами W, X и Y ее стоимость вершины будет vertexCost(W,V,X) + vertexCost(W,V,Y) + vertexCost(X,V,Y). Это помогает?

Ashton Six
9 августа 2021 в 04:58
0

@ Ричард Хм ... Интересно, следует ли делить стоимость V, вершины с 3 смежными вершинами, на 3 ^ 2, чтобы степень ветвления не была непреднамеренно минимизирована.

David Eisenstat
9 августа 2021 в 12:27
0

Я предложил проблему в ее нынешнем виде, но, как отмечает @Richard, если бы мы знали структуру на расстоянии, мы могли бы лучше ее использовать.

Ответы (1)

avatar
David Eisenstat
9 августа 2021 в 12:24
0

Квадратичная цель кажется достаточной свободой действий для создания устройств для снижения NP-твердости, хотя на данный момент у меня нет доказательств.

Поскольку ваш график разреженный, я надеюсь, что максимальная степень невелика, особенно с учетом вашего комментария о дорожных сетях. Я бы предложил следующую формулировку целочисленного программирования:

  • Переменные: для каждого ребра {v, w} пусть существует 0-1 переменная x(v, w), равная 1, если {v, w} принадлежит остовному дереву, и 0 в противном случае. Кроме того, для каждой вершины v и каждого непустого подмножества S ребер, инцидентных e, пусть существует 0-1 переменная y(v, S), равная 1, если подмножество ребер, инцидентных e в дереве, равно S, и 0 в противном случае .

  • Цель: минимизировать ∑v,S{u,w}⊆S Distance(u, v, w) y(v, S).<2225781321585>

  • Исходные ограничения: мы требуем, чтобы ∑v,S y(v, S) = 1, то есть каждая вершина должна выбирать ровно одну окрестность в дереве. Мы также требуем для каждого ребра {v, w}, чтобы ∑v,S∋w y(v, S) = x(v, w), то есть окрестность, которую выбирает v, должна быть согласованной с тем, существует ли ребро.

  • Ограничения связности: прямо сейчас ничто не заставляет решатель вообще выбирать какие-либо ребра. Можно сформулировать ограничения связности статически, но вместо этого я бы рекомендовал следующий подход. Запустите решатель с ограничениями на данный момент и вычислите его связанные компоненты. Если есть ровно один компонент, отлично, это оптимальное решение. В противном случае для каждой компоненты C требуем, чтобы ∑{v,w}∈E(C,V∖C) x(v, w) ≥ 1, т. е. дерево содержит хотя бы одно ребро с одна конечная точка в C и одна конечная точка не в C — и попробуйте еще раз.

Обычно я использую OR-Tools, потому что это предпочтительная библиотека, где я работаю, но у вас есть много вариантов.