Как решить эту матричную задачу, чтобы собрать все семена?

Question

Описание проблемы:

Хомяк Хамми нашел здание с семенами. Помогите ему собрать их всех.

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

Он хочет собрать все семена в здании с минимальным количеством прогонов.

Вот примерная схема здания:

+---+---+---+---+---+
| * |   | * |   |   |
+---+---+---+---+---+
| * | * |   |   |   |
+---+---+---+---+---+
| * |   |   |   | * |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+

В этом здании 25 комнат (5X5), но только у 8 rooms есть семена (комнаты, содержащие *).

Нам нужно найти минимальные пробеги, чтобы собрать все семена.

Мой подход:

Я пытался решить его с некоторыми Greedy Approach , вот оно:

1) Start with row/column that contains maximum rooms of seeds (For example: column 1 for here).

2) Updating rows/columns (no of rooms that contain seeds).

3) Repeating steps 1 & 2 until all the seeds are collected.

Итак, для этого примера, когда я применяю свой подход,

Он начинается с Column 1 (содержит 3 комнаты),

после обновления следующая будет Column 4,

Вот ситуация со зданием прямо сейчас,

+--+---+---+--+---+
|  |   | * |  |   |
+--+---+---+--+---+
|  | * |   |  |   |
+--+---+---+--+---+
|  |   |   |  | * |
+--+---+---+--+---+
|  |   |   |  |   |
+--+---+---+--+---+
|  |   |   |  |   |
+--+---+---+--+---+

Теперь три комнаты содержат семена и все на разных rows или columns, Мне нужно взять все из них, в результате я закончил с 5 runs, то есть maximum (, берущий все строки или все столбцы, всегда является ответом на мысль нг про семена вообще ). Без каких-либо расчетов сюда можно добраться. Прогоны, содержащие все строки или столбцы.

Но эту проблему можно решить за 4 прогона.

Я ищу подход / алгоритм для поиска минимальных прогонов ( какие строки и / или столбцы мне нужно запустить).

Answer 1

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

Теперь все, что нам нужно, это выбрать набор вершин, чтобы хотя бы одна конечная точка каждого ребра будут включены в этот набор вершин. В теории графов это называется проблемой покрытия вершин. https://en.wikipedia.org/wiki/Vertex_cover

Чтобы достичь минимального покрытия вершин, нам нужно найти максимальное соответствие графа. Алгоритм Хопкрофта – Карпа позволяет нам найти максимальное совпадение за полиномиальное время (в худшем случае O(n^2.5). Как только мы получим максимальное совпадение, Теорема Кенига помогает нам найти минимальную вершину покрытие за O(n^2) время.

Как это работает:

Скажем M - максимальное совпадение, изначально оно установлено пустым. Из двудольного графа, нам нужно найти максимальное множество непересекающихся вершин кратчайших увеличивающих путей P.

здесь P = {r1c1, r2c2, r3c5, r4c4}

M = M (симметрия c разница) P = {r1c1, r2c2, r3c5, r4c4}

в этом примере больше не осталось пути расширения, поэтому достигается максимальное совпадение.

Теперь, используя теорему Кенига, нам нужно найти минимальное покрытие вершин из совпадающего M. Здесь покрытие вершин будет {r1, r2, r3, c4}

So the minimum run is 4.

Общая сложность этого процесса составляет O(E * (V^0.5)), E & v - длина множества ребер и вершин. разреженная матрица будет работать в почти линейное время.

Другой пример:

+---+---+---+---+---+
|   | * | * |   | * |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+
| * | * |   | * |   |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+

Двудольный график:

Максимальное соответствие M = {r1c2, r2c4, r3c1}

Минимальное покрытие вершин = {r1, r3, c4}

So the minimum run is 3.

Если вас интересует только минимальный прогон (только число, не нужно показывать детали), вам не нужно реализовывать теорему Кенига, потому что размер максимального соответствия - это длина минимального набора вершинных покрытий.

Answer 2

Эта проблема - в основном покрытие вершин в двудольном графе. Один набор узлов в графе соответствует строкам. Другой набор соответствует столбцам. Ребра соответствуют семенам, где конечные точки каждого ребра соответствуют координатам семени, соответствующего ребру.

По по теореме Кенига размер минимального покрытия равен размер максимального соответствия, который можно эффективно вычислить с помощью Hopcroft – Karp .

Answer 3

Чтобы оценить линию перед каждым прогоном, вы можете в основном проверить:

• Сколько противоположных (ортогональных) линий будет очищено, если мы отбросим текущую: + 1 для каждые
• Сколько параллельных линий останется для выполнения: -1 для каждого.

Результаты первого запуска:

 -4  -4  -4 (-2) -4
+---+---+---+---+---+
| * |   | * |   |   | -3
+---+---+---+---+---+
| * | * |   |   |   | -3
+---+---+---+---+---+
| * |   |   |   | * | -3
+---+---+---+---+---+
|   |   |   | * |   | -4
+---+---+---+---+---+
|   |   |   | * |   | -4
+---+---+---+---+---+

• Столбец 1 очистит 0 строк и оставит для запуска 4 других столбца = -4
• Столбец 4 очистит 2 строки и оставит 4 других столбца для запуска = -2
• Строка 1 очистит 1 столбец и оставит 4 другие строки для запуска = -3

Результаты для второго запуска:

 -3  -3  -3  -4  -3
+---+---+---+---+---+
| * |   | * |   |   | (-1)
+---+---+---+---+---+
| * | * |   |   |   | (-1)
+---+---+---+---+---+
| * |   |   |   | * | (-1)
+---+---+---+---+---+
|   |   |   |   |   | -3
+---+---+---+---+---+
|   |   |   |   |   | -3
+---+---+---+---+---+

Может быть решена за полиномиальное время (столбцы * строки) используя динамическое программирование c (рассчитайте первые оценки каждой строки и столбцов, а затем обновите только затронутые при использовании одной строки).

Answer 4

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

  3   1   1   2   1
+---+---+---+---+---+
| * |   | * |   |   | 2
+---+---+---+---+---+
| * | * |   |   |   | 2
+---+---+---+---+---+
| * |   |   |   | * | 2
+---+---+---+---+---+
|   |   |   | * |   | 1
+---+---+---+---+---+
|   |   |   | * |   | 1
+---+---+---+---+---+

Затем вы берете сумму строк с семенами в них в строке и делите их на количество семян. Это дает вам оценку для этого столбца. Сделайте это для всех строк и столбцов, как это.

Например, возьмите строку 1, которая разделяет начальные числа со столбцами 1 и 3. В столбце 1 содержится 3 начальных числа, а в столбце 3 - 1 вместе, то есть 4 начальных числа. Разделите это число на количество строк, и вы получите 2, поэтому оценка для строки 1 равна 2.

  2   2   2   1   2
+---+---+---+---+---+
| * |   | * |   |   | 2
+---+---+---+---+---+
| * | * |   |   |   | 2
+---+---+---+---+---+
| * |   |   |   | * | 2
+---+---+---+---+---+
|   |   |   | * |   | 2
+---+---+---+---+---+
|   |   |   | * |   | 2
+---+---+---+---+---+

Затем вы берете строку / столбец с наименьшим числом, отличным от нуля. При этом получится столбец 4 (освобождает две строки, оценка 1).

              ↓
+---+---+---+---+---+
| * |   | * |   |   |
+---+---+---+---+---+
| * | * |   |   |   |
+---+---+---+---+---+
| * |   |   |   | * |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+
|   |   |   | * |   |
+---+---+---+---+---+

А затем строки 1, 2 (каждая освобождает 1 столбец, оценка 2) и 3 (освобождает 2 столбца). , оценка 1) в любом порядке.

+---+---+---+---+---+
| * |   | * |   |   | ←
+---+---+---+---+---+
| * | * |   |   |   | ←
+---+---+---+---+---+
| * |   |   |   | * | ←
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Я не знаю, будет ли этот подход работать в общем случае.