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

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

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

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

Предположим, вы можете найти минимальное остовное дерево в 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), ​​которое, я думаю, даст вам решение, очень близкое к оптимальному.

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

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

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

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

Для 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 over X-1) * x^2... Довольно сложно, но я думаю, что это даст мне ОПТИМАЛЬНОЕ решение

что ты думаешь?

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

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

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

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

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

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

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

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

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

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

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

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

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

Для X = 3 я бы просто проверил другие кортежи с одним фиксированным снова. (А,В,С) (А,В,D) ... (А,С,D) ... (А,Е,F)

Я просто придумал простое решение следующим образом:

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

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

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

1. Отсортировать все ребра по стоимости

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

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

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

Звучит как знаменитая задача коммивояжера. Известно, что задача является NP-трудной. Взгляните на Википедию в качестве отправной точки: http://en.wikipedia.org/wiki/Travelling_salesman_problem< /а>