Как выбрать минимальный подграф графа, содержащего любые k узлов

Я пытаюсь решить проблему ниже. Это похоже на k-минимальное остовное дерево и задачу дерева Штейнера, но с графом.

  • У нас есть неотрицательный неориентированный взвешенный граф G = (V, E).
  • Для каждой пары вершин v1 и v2 существует ребро e12. Другими словами, каждая вершина связана с любой другой вершиной.
  • Мы создадим подмножество вершин U, содержащее k вершин.
  • Наша цель — выбрать n вершин в U так, чтобы сумма ребер от каждой вершины в U до любой другой вершины была минимальна. Другими словами, мы хотим выбрать вершины в U так, чтобы сумма всех ребер от узлов в U наружу была минимальна.
  • 1 ‹ n ‹ количество вершин

Правильно ли я понимаю, что ни k-MST, ни аппроксимация дерева Штейнера не будут работать? Если да, то как называется эта проблема? И какие есть решения? Я согласен с использованием эвристики или приближений для решения этой проблемы и не нуждаюсь в формальных доказательствах.


graph tree graph-theory graph-algorithm subgraph
person bluepanda    schedule 24.08.2017    source источник
comment
У меня не так много опыта в подобных задачах, поэтому я должен задать пару, возможно, глупых вопросов: k и n — одно и то же? У и В это одно и то же? Является ли ваш третий пункт просто упрощенной версией вашего четвертого пункта?   -  person BenZinra    schedule 25.08.2017
comment
Не совсем. V представляет собой набор всех вершин некоторого графа. E представляет набор ребер в этом графе. k — это просто целое число, которое представляет, сколько вершин нам нужно (это входные данные для задачи, наряду с графом G, содержащим V и E). U представляет собой подмножество из k вершин, которые мы хотим выбрать с помощью некоторого алгоритма (U — это результат задачи). Таким образом, пункт 4 говорит о том, что k вершин, которые наш алгоритм выбирает в U, должны быть выбраны таким образом, чтобы сумма длин их ребер до всех вершин (включая те, которые не принадлежат U) была минимизирована.   -  person bluepanda    schedule 25.08.2017
comment
Итак, если вы думаете о матрице, где каждый столбец/строка является вершиной, а каждая ячейка - весом. Итак, U — это подмножество строк, и тогда вы хотите минимизировать сумму весов в каждой строке?   -  person juancn    schedule 25.08.2017

Ответы (2)


arrow_upward
1
arrow_downward

Вы правы в том, что K-MST или дерево Штейнера не будут работать - они создают только дерево, а вам нужен граф со специальными свойствами, например. с нулевой стоимостью между вершинами внутри U и минимальной стоимостью для всех остальных ребер, если я понял вашу проблему.

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

Для метаэвристики:

  1. Вычислить стоимость ребра для каждой вершины
  2. Жадно выберите k вершин — это сформирует ваше исходное решение
  3. В случае SA начните модифицировать исходное решение, включая/исключая новые вершины одну за другой (возможно, есть лучший подход, вы должны изучить его самостоятельно)
  4. Учитывая достаточно времени, он должен сходиться к достаточно хорошему решению

Для удовлетворения ограничений:

  1. Цель: выбрать k вершин из заданного графа. Для каждой вершины ввести булеву переменную, если она 1 — вершина является частью U, иначе — 0. Тогда ваша цель:

сумма (вершины==1) = k

  1. С учетом: минимальной суммы весов ребер между k-вершинами и другими. Если я прав, стоимость ребер в U равна 0. Я не знаю, как правильно сформулировать такие ограничения, но они должны быть довольно простыми.
  2. Запустите решатель с тайм-аутом, скажем, на несколько часов.

Для последнего подхода, удовлетворения ограничений, память может быть проблемой — вам нужно много памяти для представления полносвязного графа и всех ограничений. Тем не менее проверьте Minizinc, lpsolve и coin-or.

person CaptainTrunky    schedule 25.08.2017

arrow_upward
1
arrow_downward

Я не знаю, есть ли более быстрый алгоритм, но тривиальный (если я правильно понял ваше объяснение):

  • Создайте массив/карту, где вы храните сумму весов для каждого ребра от vi до любой другой вершины. Если вы думаете о матричном представлении графа, где каждая строка/столбец является вершиной, а каждая ячейка является весом на ребре. Массив будет суммой каждой строки.
  • Сгенерируйте все подмножества вершин размером k, оставьте тот, сумма которого наименьшая.

Если есть n вершин, это исследует n!/(k! (n-k)!) таких комбинаций.

person juancn    schedule 25.08.2017