Комбинаторная оптимизация

Question

Предположим, у нас есть связный и ненаправленный граф: G = (V, E).

Определение связного множества: группа точек, принадлежащих V из G, образует действительное связное множество, если каждая точкав этой группе находится в пределах T-1 ребер от любой другой точки в той же группе, T является количеством точек в группе.

Просьба учесть, что связное множество является просто связным подграфом G без ребер, но с точками.

И у нас есть произвольная функция F, определенная на связном множестве, то есть, учитывая, что произвольное связное множество CS F (CS) даст нам реальное значение.

Два соединенных множества называются непересекающимися, если их объединение не является связным множеством.

Для наглядного объяснения, пожалуйста, см. График ниже: На графике наборы красной, черной, зеленой точек являются допустимыми связными наборами, зеленый набор не пересекается с красным набором, но черный набор не является непересекающимсяк красному.

Теперь вопрос: мы хотим найти группу непересекающихся связных множеств из G так, чтобы: (1) каждое связное множество имело как минимум K точек.(K является глобальным параметром).(2) сумма значений их функций, то есть max (Σ F (CS)), максимизирована.

Существует ли какой-либо эффективный алгоритм для решения такой проблемы, кроме исчерпывающего поиска?Thx!

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

Answer 1

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

Чтобы доказать, что ваша функция является субмодульной, вам нужно только доказать следующее:

Существует несколько доступных реализацийалгоритма минимальной точки нормы, например Matlab Toolbox для оптимизации субмодульной функции

Answer 2

Я сомневаюсь, что существует эффективный алгоритм, поскольку для полного графа, например, вы не можете решить проблему, не зная значения F на каждом подграфе (кроме случаев, когда у вас есть предположения о F: монотонности, например).

Тем не менее, я бы пошел на недетерминированный алгоритм.Попробуйте смоделированный отжиг с переходами:

• Удалить точку из набора (если она остается подключенной)
• Переместить точку из набора в другую (если они остаются подключенными)
• Удалить набор
• Добавить набор с одной точкой

Удачи, это кажется трудной проблемой.

Answer 3

Я бы использовал динамическое программирование.Вы можете перефразировать вашу проблему как проблему окраски узла:

• Ваша цель - назначить цвет каждому узлу.(Другими словами, вы ищете раскраску узлов)
• Доступные цвета - черный и белый.
• Чтобы судить о раскраске, вы должны изучить набор "максимальных связанныхнаборы черных узлов ".
  • Набор черных узлов называется связанным, если индуцированный подграф связан.
  • Связанный набор черных узлов называется максимальным. Ни один из узлов в наборе не имеет черного соседа в исходном графе.это не содержится в наборе)
• Ваша цель - найти раскраску, которая максимизирует ΣF (CS).(Здесь вы суммируете по «максимальным связным наборам черных узлов»)
• У вас есть некоторые дополнительные ограничения, указанные в исходном сообщении.

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

• Выберите узел
• Попробуйте раскрасить выбранный узел белым
  • Найдите раскраску оставшихся узлов, которая максимизирует ΣF (CS)
• Попробуйте покрасить выбранный узел в черный цвет
  • Найдите раскраску оставшихся узлов, которая максимизирует ΣF (CS)

Каждый раз, когда вы окрашиваете узел в белый цвет, вы можете проверить, стал ли график «разложимым» (я придумал это слово. Оно не является официальным):

• ЧастичноЦветной граф называется «разложимым», если он содержит пару небелых узлов, которые не связаны ни одним путем, не содержащим белый узел.

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

РЕДАКТИРОВАТЬ: Я добавил альтернативную идею и удалил ее снова.:)

Answer 4

Для такого общего F не так-то просто составить оптимизированный алгоритм, в отличие от подхода brute force .
Например, так как мы хотим найти связку из CS , где F ( CS ) максимизирована, мы должны предположить, что мы действительно хотим найти max (Σ F ( CS )) для всех CS или самое высокое F значение из всех возможных CS , не более (F (cs i ) )? Мы не знаем наверняка.
Кроме того, если F произвольно, мы не можем оценить вероятность наличия F(cs+p1) > F(cs) => F(cs+p1+p2) > F(cs).

Однако мы все еще можем это обсудить:

Кажется, мы можем вывести из проблемы, что мы можем обрабатывать каждую CS независимо, то есть, если n = F(cs1) добавить любую cs2 (будучи не связанной с cs1 ) не будет влиять на значение n.

Кажется также правдоподобным, и именно здесь мы должны быть в состоянии получить некоторую выгоду, что вычисление F может быть сделано, начиная с любой точки CS , и, в общем, если CS = cs1+cs2, F(CS) = F(cs1+cs2) = F(cs2+cs1).

Затем мы хотим внедрить памятку в алгоритм, чтобы ускорить процесс, когда CS постепенно увеличивается, чтобы найти максимум (F (* 1044). * cs )) [учитывая F general, подход к динамическому программированию, например, начиная с CS, состоящего из всех точек, а затем уменьшая его постепенно, не представляет большого интереса].

В идеале мы могли бы начать с CS, состоящего из точки, увеличив ее на единицу, проверяя и сохраняя значения F (для каждого подмножества). Каждый тест сначала проверяет, существует ли значение F, чтобы не вычислять его; затем повторите процедуру для другой точки и т. д., найдите лучшие подмножества, которые максимизируют F. Для большого количества точек это очень длительный опыт.

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

Но, опять же, из-за отсутствия свойств F, мы можем ожидать экспоненциального пробела в виде напоминаний (например, сохранение F (p1, ..., pn) для всех подмножеств). И экспоненциальная сложность.