поиск минимального количества ходов по жадному алгоритму
Существует двумерная сетка, которая содержит шоколад в случайных ячейках. За один ход я могу взять все шоколадные конфеты, содержащиеся в одном ряду или в одном столбце. Какое минимальное количество шагов потребуется, чтобы взять все шоколадные конфеты?
Пример: клетки, содержащие шоколадные конфеты:
0 0
1 1
2 2
минимум нет ходов = 3
0 0
1 0
0 1
мин нет ходов = 2
Я думаю, что есть жадное решение этой проблемы. Но как подойти к этой проблеме?
Решение
Я думаю, что это дисперсия классики Установить обложку проблема, которая оказалась NP-трудной.
Следовательно, жадный алгоритм может получить только приближение, но не оптимальное решение.
Другие решения
Для этой конкретной задачи это не NP-сложный. Это может быть решено за полиномиальное время. Решение как ниже:
Преобразуйте двумерную сетку в двудольный граф. Левая сторона содержит узлы, представляющие строку, а правая сторона содержит узлы, представляющие столбец. Для каждой ячейки, содержащей шоколад, предположим, что ее координата равна (x, y), добавьте ребро, связывающее row_x и column_y. После того, как двудольный граф установлен, используйте венгерский алгоритм для получения максимального соответствия. Поскольку в двудольном графе ответ максимального соответствия равен минимальному покрытию вершин, ответ будет именно тем, что вы хотите.
Венгерский алгоритм является алгоритмом O (V * E). Для более подробной информации, пожалуйста, обратитесь к Венгерский алгоритм
Для получения дополнительной информации о двудольном графе, пожалуйста, обратитесь к Двудольный граф, Вы можете найти, почему максимальное совпадение равно минимальному покрытию вершины здесь.
PS: Это не жадная проблема и не проблема динамического программирования. Это проблема графа.