Задача оптимизации - найти максимум

Question

У меня есть проблема, которая может быть сведена к следующему:

Предположим, что в двухмерной плоскости XY имеется группа случайных точек, где для каждого Y может быть несколько точек на X идля каждого X может быть несколько точек на Y.

Всякий раз, когда выбирается точка (Xi, Yi), никакая другая точка с X = Xi ИЛИ Y = Yi не может быть выбрана.Мы должны выбрать максимальное количество баллов.

Answer 1

Это можно свести к простой проблеме максимального расхода.Если у вас есть точка (xi, yi), на графике она должна быть представлена ​​путем от источника S до точки xi, от xi до yi и от yi до последнего узла (приемника) T.

Примечание,если у нас есть точки (2, 2) и (2, 5), остается только один путь от S до x2.Все пути (ребра) имеют емкость 1.

Поток в этой сети является ответом.

об общей проблеме
http://en.wikipedia.org/wiki/Max_flow

update
У меня сейчас нет графического редактора для визуализации проблемы, но вы можете легко нарисовать пример вручную.Скажем, точки: (3, 3) (3, 5) (2,5)

Тогда ребра (контуры) будут
S -> x2, S -> x3
y3 -> T, y5 -> T
x3 -> y3, x3 -> y5, x2 -> y5

Поток: S -> x2 -> y5 -> T и S -> x3 -> y3-> T
Количество «воды», идущей от источника к раковине, равно 2, и ответ таков.

Также есть учебник по алгоритмам максимального потока
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

Answer 2

Разве это не просто Венгерский алгоритм ?

Создать матрицу n × n , с 0 в отмеченных вершинах и 1 в немаркированных вершинах.Алгоритм выберет n вершин, по одной для каждой строки и столбца, что минимизирует их сумму.Просто посчитайте все выбранные вершины, которые равны 0, и вы получите свой ответ.

from munkres import Munkres

matrix = [[0, 0, 1],
          [0, 1, 1],
          [1, 0, 0]]

m = Munkres()
total = 0
for row, column in m.compute(matrix):
    if matrix[row][column] == 0:
        print '(%i, %i)' % (row, column)
        total += 1

print 'Total: %i' % total

Это выполняется за O (n ³ ) время, где n количество строк в матрице.Решение с максимальным расходом работает в O (V ³ ), где V - количество вершин.Пока есть более чем 1020 * n выбранных пересечений, это работает быстрее;на самом деле он работает на несколько порядков быстрее, так как количество выбранных вершин увеличивается.

Answer 3

Отличное решение. Оказывается, что есть много симметрии, и ответ намного проще, чем я первоначально думал. Максимальное количество вещей, которые вы когда-либо можете сделать, - это минимум уникальных X и уникальных Y, который равен O (NlogN), если вы просто хотите получить результат.

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

Таким образом, оптимальное решение не имеет ничего общего со связностью. Выберите любую точку, которая находится на краю наименьшего измерения (т. Е. Если len (unique-Xs)> len (unique-Ys), выберите все, что имеет максимальный или минимальный X). Неважно, сколько у него подключений, только то, какое измерение самое большое, что можно легко сделать, глядя на отсортированные уникальные списки, созданные выше. Если вы сохраняете счетчики unique-x и unique-y и уменьшаете их при удалении всех уникальных узлов в этом элементе списка, то каждое удаление равно O (1), а пересчет длин - O (1). Таким образом, повторение этого N раз в худшем случае O (N), а окончательная сложность - O (NlogN) (исключительно из-за сортировки).

Вы можете выбрать любую точку вдоль кратчайшего края, потому что:

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

По сути, вы максимизируете "max (uniqX, uniqY)" в каждой точке.

Обновление: IVlad поймал крайний случай:

Если размеры равны, возьмите край с наименьшим количеством точек. Даже если они не равны, возьмите верх или низ уникального стека, из которого вы удаляете, и который имеет наименьшее количество очков.

Показательный пример:

Поворот 1:

• Баллов: (1, 2); (3, 5); (10, 5); (10, 2); (10, 3)
• Есть 3 уникальных X: 1, 3, 10
• Есть 3 уникальных Y: 2, 3, 5
• "Ограничивающий прямоугольник" равен (1,5),(10,5),(10,2),(1,2)

Реакция 1:

• "Внешний край" (самый внешний список точек UniqueX или UniqueY), который имеет наименьшее количество точек, является левым. В основном, посмотрите на наборы точек в x = 1, x = 10 и y = 2, y = 5. Набор для x = 1 является наименьшим: одна точка. Выберите единственную точку для х = 1 -> (1,2).
• Это также исключает (10,2).

Поворот 2:

• Баллов: (3, 5); (10, 5); (10, 3)
• Есть 2 уникальных X: 3, 10
• Есть 2 уникальных Y: 3, 5
• «Ограничивающий прямоугольник» равен (3,5),(10,5),(10,3),(3,3)

Реакция 2:

• "Край" ограничивающего прямоугольника, который имеет наименьшее значение, находится либо внизу, либо слева. Мы достигли тривиального случая - 4 балла означают, что все ребра являются внешними ребрами. Устранить один. Скажите (10,3).
• Это также исключает (10,5).

Ход 3:

• Баллов: (3, 5)

Реакция 3:

• Удалить (3,5).

Answer 4

На основании рекомендации IVlad я изучил алгоритм Хопкрофта-Карпа .Обычно это лучше, чем алгоритм максимального потока и венгерский алгоритм для этой проблемы, часто значительно.Некоторые сравнения:

В общем :

• Макс. Расход: O (V ³ ), где V количество вершин.
• Венгерский: O (n ³ ), где n - количество строк в матрице
• Хопкрофт-Карп:O (V √2V) где V - количество вершин.

Для матрицы 50 × 50 с 50% выбранных вершин :

• Макс. Расход: 1250 ³ = 1 953 125 000
• Венгерский: 50 ³ = 125 000
• Хопкрофт-Карп: 1250 √2 500 = 62 500

Для матрицы 1000 × 1000 с 10 выбранными вершинами :

• Макс. Расход: 10 ³ = 1000
• Венгерский: 1000 ³ = 1 000 000 000
• Хопкрофт-Карп: 10 √20 ≅ 44,7

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

Для матрицы 100 × 100 с выбранным 90%вершины :

• Макс. расход: 9 000 ³ = 729 000 000 000
• Венгерский: 100 ³ = 1 000 000
• Хопкрофт-Карп: 9000 √18,000 ≅ 1 207 476,7

Алгоритм Max Flow никогда лучше.

На практике это также довольно просто.Этот код использует реализацию David Eppstein :

points = {
    0 : [0, 1],
    1 : [0],
    2 : [1, 2],
}

selected = bipartiteMatch(points)[0]

for x, y in selected.iteritems():
    print '(%i, %i)' % (x, y)

print 'Total: %i' % len(selected)

Answer 5

Самолет XY - красная сельдь.Сформулируйте его как набор элементов, каждый из которых имеет набор взаимоисключающих элементов.

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

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

Answer 6

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

Answer 7

Для каждой точки укажите количество других точек (N), которые будут дисквалифицированы при выборе этой точки (то есть точки с одинаковыми значениями X или Y). Затем выполните итерацию по недисквалифицированным точкам в порядке возрастания числа N дисквалифицированных точек. Когда вы закончите, вы удалите максимальное количество очков.