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

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

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

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

Ответ 1

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

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

Ответ 2

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

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

Итак, ваша dp-матрица будет примерно такой:

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).