Расширение графика

Question

В настоящее время я работаю над интересной проблемой графов, я не могу найти никаких алгоритмов или других вопросов, связанных со стековым потоком, в которых упоминается что-либо подобное.

Если у меня есть график (ненаправленный, циклический) и список часто используемых путей, как лучше всего сократить среднюю длину пути, добавив еще N ребер? РЕДАКТИРОВАТЬ :: Важный момент, который может помочь, все пути начинаются на одном узле.

Answer 1

Вы можете просто попытаться вставить все возможные ребра и посмотреть, насколько уменьшается кратчайший путь для каждой из заданных вами начальных / конечных точек. Выберите лучший край и повторите.

Полезность ребер зависит от того, какие другие ребра были добавлены, поэтому, если вы действительно хотите оптимальности, вам придется попробовать все наборы из N ребер. Это звучит немного дороже. Меня не удивит, если это будет NP-хард.

Интересный вопрос!

Answer 2

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

Очевидно, что это работает, только если узлы как-то расположены в пространстве, но это хорошая аналогия.

Answer 3

Отвечая на мой собственный вопрос, чтобы охватить то, что я уже рассмотрел.

Очевидное решение заключается в простой сортировке общих путей по порядку и размещении в соединении между двумя концами, и продолжайте делать это, пока у вас не кончатся края для вставки. Тем не менее, я подозреваю, что есть более разумное решение.