Нахождение X самых дешевых деревьев в графе

Question

У меня есть граф с N узлами и ребрами со стоимостью. (график может быть завершен, но также может содержать нулевые ребра).

Я хочу найти K деревьев на графике (K

Какие-нибудь рекомендации, каким может быть лучший подход?

Я пытался изменить проблему, чтобы найти только одно минимальное связующее дерево, но безуспешно. Спасибо за любую подсказку!

EDIT

маленькая деталь, которая может быть значительной. К стоимости не относится переход через край. Стоимость это цена, чтобы построить такой край. Как только край построен, вы можете пройти его вперед и назад без каких-либо затрат. Проблема не в том, чтобы «проехать по всем узлам», а в том, чтобы «создать сеть среди всех узлов». Прошу прощения за предыдущие объяснения

История Вот история, которую я слышал и пытался разгадать.

Есть город, без подключения к электричеству. Электротехническая компания может подключить только K домов с помощью электричества. Другие дома можно подключить, отсоединив кабели от уже подключенных домов. Но сброс этого кабеля чего-то стоил. Цель состоит в том, чтобы выбрать, какие K-дома будут подключены напрямую к электростанции, а какие будут подключены отдельными кабелями, чтобы обеспечить минимальную стоимость кабеля и охват всех домов:)

Answer 1

Как уже упоминали другие, это сложно для NP.Однако, если вы готовы принять хорошее решение, вы можете использовать имитационный отжиг.Например, задача коммивояжера является трудной для NP, но почти оптимальные решения могут быть найдены с помощью имитации отжига, например http://www.codeproject.com/Articles/26758/Simulated-Annealing-Solving-the-Travelling-Salesma

Answer 2

Я только что придумал простое решение:

N - количество узлов

C - прямое подключение к сети

E - доступные ребра

---

1, сортировка всех ребер по стоимости

2, повтор (N-C) раз:

1. Возьмите самое дешевое из доступных
2. Проверьте, не приведет ли добавление этого ребра к появлению окружностей в уже добавленном ребре
3. Если нет, добавьте это ребро

3, вот и все ... Вы получите C непересекающихся наборов ребер, подключите каждый набор к сетке

Answer 3

Вот попытка решить эту проблему ...

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

. Для X = 2 я создаю дополнительный узел (узел электростанции) рядом с моим графиком.Я соединяю его со случайным узлом (например, N0) по краю со стоимостью 0. Теперь я уверен, что у меня есть один штекер силовой установки (случайный узел обязательно будет в одном из деревьев, поэтому будет соединено все дерево).Теперь итерационная часть.Я беру другой узел (например, N1) и снова соединяюсь с PP с нулевым преимуществом.Теперь я вычисляю MST.Затем повторите этот процесс с заменой N1 на N2, N3 ... Итак, я протестирую каждую пару [N0, NX].MST выигрывает с наименьшей стоимостью.

Для X> 2 это действительно то же самое, что и для X = 2, но мне нужно проверить соединение с PP для каждого (x-1) -типа и вычислить MST

с x ^ 2 для MST У меня сложность с (N над X-1) * x ^ 2 ... Довольно сложная, но я думаю, что это даст мне ОПТИМАЛЬНОЕ решение

что вы думаете?

редактировать случайным узлом, я имею в виду случайный, но ИСПРАВЛЕННЫЙ узел

попытка визуализации для x = 2 (каждое описание принадлежит изображению над ним)

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

Только для изображения, это может быть решением

Пусть зеленый будет электростанцией, вот как может выглядеть соединение с одним деревом

Но это другое подключение действительно одно и то же (подключение к электростанции (pp) стоит одинаково, кабели остаются нетронутыми).Вот почему мы можем установить один из узлов в качестве фиксированной точки контакта с пп. Мы можем быть уверены, что узел будет в одном из деревьев, и не имеет значения, где находится дерево.

Итак, пусть это будет наша фиксированная ситуация с G в качестве PP.Добавлено ребро (B, G) с нулевой стоимостью.

Теперь я пытаюсь подключить второе соединение с PP (A, G, стоимость 0)

Теперь я вычисляю MST по ПП.Поскольку красные края являются самыми дешевыми (они могут иметь даже отрицательную стоимость), уверен, что оба они будут в MST.

Так что при запуске MST я получаючто-то вроде этого.Представьте себе отделение PP и двух деревьев МИНИМАЛЬНОЙ СТОИМОСТИ.Это лучшее решение для А и Б - это соединения с ПП.Я сохраняю стоимость и продолжаю.

Теперь я делаю то же самое для соединений B и C

Я могполучите что-то вроде этого, поэтому сравните стоимость с предыдущей и выберите лучшую.

Таким образом, я должен попробовать все пары соединений (B, A) (B, C) (B, D) (B, E) (B, F), и самый дешевый - победитель.

Для X = 3 я бы просто протестировал другие наборы с одним фиксированным снова.(A, B, C) (A, B, D) ... (A, C, D) ... (A, E, F)

Answer 4

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

Рассматривая доказательства правильности алгоритма Примав http://en.wikipedia.org/wiki/Prim%27s_algorithm, рассмотрите возможность взять минимальное связующее дерево и удалить самые дорогие ссылки X-1.Я думаю, что доказательство показывает, что результат имеет ту же цену, что и лучший ответ на вашу проблему: единственное отличие состоит в том, что при сравнении ребер вы можете обнаружить, что новое ребро объединяет два отдельных компонента, но в этом случае вы можетесохраняйте количество разделенных компонентов, удаляя ребро, стоимость которого не превышает стоимость нового ребра.

Поэтому я думаю, что ответом на вашу проблему является использование минимального связующего дерева и удаление самых дорогих ссылок X-1.,Это, безусловно, относится к X = 1!

Answer 5

Вы описываете что-то вроде ограничения мощности путь покрытия .Он входит в семейство проблем коммивояжеров и транспортных средств и является NP-Hard.Чтобы создать алгоритм, вы должны спросить

1. Запускаете ли вы его только на маленьких графиках..
2. Можете ли вы жить с эвристикой, которая примерно решает проблему.

Answer 6

Похоже на известную проблему коммивояжера.Проблема известна как NP-сложная.Взгляните на Википедию как отправную точку: http://en.wikipedia.org/wiki/Travelling_salesman_problem

Answer 7

Предположим, вы можете найти минимальное остовное дерево в O(V^2), используя алгоритм Прима.

Для каждой вершины найдите минимальное остовное дерево с этой вершиной в качестве корня.

Это будет O(V^3) при запуске алгоритма V раз.

Сортируйте их по общей массе (сумме весов их вершин) графа. Это O(V^2 lg V), который потребляется O(V^3), так что он абсолютно свободен с точки зрения сложности заказа.

Возьмите X наименее массивных графов - корни этих ваших «якорей», которые напрямую связаны с сеткой, так как они, скорее всего, имеют самые короткие пути. Чтобы определить, по какому маршруту он идет, вы просто следуете пути к корню в каждом узле каждого дерева и подключаетесь к тому, что является самым коротким. (Это может быть дополнительно оптимизировано путем сортировки всех путей к корню и использования сначала только самых коротких. Это позволит оптимизировать следующие итерации. Поиск пути к корню - O(V). Поиск его для всех времен VX - O(V^2 * X). Поскольку вы будете делать это для каждого V, вы смотрите на O(V^3 * X). Это больше, чем ваша самая большая сложность, но я думаю, что средний случай для них будет небольшим, даже если их наихудший случай велик).

Я не могу доказать, что это оптимальное решение. На самом деле, я уверен, что это не так. Но когда вы рассматриваете электрическую сеть из 100 000 домов, вы не можете рассматривать (с любым практическим применением) трудное решение NP. Это дает вам очень хорошее решение в O (V ^ 3 * X), ​​которое, я думаю, даст вам решение, очень близкое к оптимальному.