Максимальная сумма несмежных элементов в 2D-массиве

Question

Я пытаюсь найти алгоритм, который поможет мне найти максимальную сумму несмежных элементов в 2D-массиве.

Для 1D массивов, я нашел полезные решения от: 1) http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/ 2) https://www.youtube.com/watch?v=UtGtF6nc35g

Например в 1D массива: {3, 2, 6, 2, 10} я получу максимальная сумма 19, потому что 3, 6 и 10 не смежны.

Однако я не могу найти тот, который может помочь мне с 2D-массивом. Как я могу найти максимальную сумму целых чисел в этом массиве без горизонтальных или вертикальных смежных элементов? Допускаются диагонально смежные элементы.

Например:

[3, 2, 6, 2, 10] 
[1, 5, 2, 5, 1] 
[5, 1, 7, 2, 9] 
[3, 9, 1, 8, 2] 

Есть ли существующий алгоритм для решения этой проблемы? Или это был бы другой метод для решения этой проблемы, если бы я использовал другую структуру данных вместо 2D-массива?

Answer 1

Проблема может быть указана как maximum-weight independent set или mixed integer linear programming проблема.

Чтобы преобразовать его в независимый набор максимального веса, создайте граф, где вершины являются элементами, а грани - смежными.

Я не эксперт по целочисленному программированию. Существует аналогичный (еще более сложный) question, где sascha продемонстрировал, как преобразовать проблему в MIP и мощность решателей.