Алгоритм минимальной стоимости с 1 стоимостью для ребер и 2 стоимостью для вершин

Question

Я пытаюсь найти алгоритм для следующей ситуации: я хочу запустить алгоритм минимальной стоимости на неориентированном графике. Ребра имеют стоимость, связанную с ними, а вершины имеют 2 стоимости, связанные с ними. Вот где это становится немного сложнее. Я должен выбрать одну из двух затрат, связанных с вершиной. Если я выберу cost1, вершина будет иметь тип 1, если я выберу cost2, вершина будет иметь тип 2. Вершины можно считать связанными только ребром, ЕСЛИ они разных типов. Большую часть времени будет логично выбрать самую низкую стоимость для вершины, но в зависимости от стоимости ее ребер, связанных с ней, и типа соседней вершины, вы предпочтете выбрать самую высокую стоимость для вершины, в результате на меньшую общую стоимость. Будем весьма благодарны за любые предположения, например, какой алгоритм или какие методы мне следует применить.

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

редактировать: орфография.

Answer 1

Проблема, которую вы описываете, может быть тривиально преобразована в задачу минимального разреза, а затем решена с помощью алгоритма Stoer-Wagner . Создайте еще две вершины, каждая из которых имеет ребра для всех остальных вершин (кроме друг друга). С одной стороны, граничные затраты берутся из соответствующих вершин cost1s; с другой стороны, от их стоимости. Теперь найдите минимальный разрез; это будет разрезать между двумя новыми узлами и разделить исходные вершины на type1 и type2.

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