Поиск минимальной стоимости в двоичной матрице

Question

Рассмотрим двоичную матрицу n * n. Каждая ячейка этой матрицы имеет не более 4 соседей (если она существует). Мы называем две ячейки этой матрицы несовместимыми, если они являются соседями, а их значения не равны. Мы платим $ b за каждую несовместимую пару. Также мы можем изменить значение ячейки с оплатой $ a.

Вопрос заключается в том, чтобы найти минимальную стоимость для этой матрицы.

Я уже использовал backtracking и нашел алгоритм O(2^(n * n)). Может ли кто-нибудь помочь мне найти более эффективный алгоритм?

Answer 1

Эта идея принадлежит Грейгу, Портфею и Сеууту. Рассматривайте матрицу как емкостный ориентированный граф с вершинами, соответствующими элементам матрицы, и дуги от каждой вершины до четырех ее соседей, каждая с емкостью b. Введем еще две вершины: источник и приемник, а дуги емкости a: от источника до каждой вершины с соответствующей записью 0 и для приемника из каждой вершины с соответствующей 1 записью. Найдите минимальный разрез; записи со значением 0 после изменений - это вершины на стороне источника разреза, а записи со значением 1 после изменений - это вершины на стороне раковины разреза.

Стоимость этого разреза - именно ваша цель. Из емкости - a из-дуги источника, пересекающие разрез, соответствуют изменениям от 0 до 1. Из емкости-a к-раковины, пересекающие разрез, соответствуют изменениям от 1 до 0. Из емкости - b дуги, пересекающие разрез, соответствуют тем случаям, когда имеется дуга от 0 до 1.

Answer 2

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

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

Так что ваша дп матрица будет что-то вроде:

dp[top_bound][n][n]; 

И прежде чем делать возвраты вы должны сделать:

if(dp[acc_cost][this_i][this_j] != -1) 
    return dp[acc_cost][this_i][this_j]; 

// Perform your calculations 
// ... 

dp[acc_cost][this_i][this_j] = result; 
return result; 

Здесь я предполагаю, что -1 является недопустимым значением в результате, если не вы просто выбираете какое-либо недопустимое значение и инициализируете свою матрицу. Поскольку эта матрица имеет размер n * n * top_bound, тогда правильно реализованный DP должен решить проблему в O (n * n * top_bound).