在二元矩阵中寻找最小成本 [英] Finding minimum cost in a binary matrix

问题描述

考虑一个 n * n 二进制矩阵.该矩阵的每个单元格最多有 4 个邻居(如果存在).如果这个矩阵的两个单元格是邻居并且它们的值不相等，我们称它们为不相容的.我们为每个不兼容的对支付 $b.我们也可以通过支付 $a 来更改单元格的值.

Consider a n * n binary matrix. Each cell of this matrix has at most 4 neighbors (if it exists). We call two cells of this matrix incompatible if they are neighbors and their values are not equal. We pay $b for each incompatible pair. Also we can change the value of the cell with paying $a.

问题是找到这个矩阵的最小成本.

The question is to find the minimum cost for this matrix.

我已经使用回溯并找到了O(2 ^ (n * n)) 的算法.有人能帮我找到一个更有效的算法吗?

I already used backtracking and found an algorithm of O(2 ^ (n * n)). Can someone help me find a more efficient algorithm?

推荐答案

这个想法是由 Greig、Porteous 和 Seheult 提出的.将矩阵视为具有容量的有向图，其顶点对应于矩阵条目和从每个顶点到其四个邻居的弧，每个顶点具有容量 b.引入另外两个顶点，一个源点和一个汇点，以及容量弧a:从源到每个具有对应 0 条目的顶点，以及从每个顶点到具有对应 1 条目的汇点.找到最小切割；更改后值为0的条目是切割源侧的顶点，更改后值为1的条目是切割源侧的顶点.

This idea is due to Greig, Porteous, and Seheult. Treat the matrix as a capacitated directed graph with vertices corresponding to matrix entries and arcs from each vertex to its four neighbors, each with capacity b. Introduce two more vertices, a source and a sink, and arcs of capacity a: from the source to each vertex with a corresponding 0 entry, and to the sink from each vertex with a corresponding 1 entry. Find a minimum cut; the entries with value 0 after changes are the vertices on the source side of the cut, and the entries with value 1 after changes are the vertices on the sink side of the cut.

这次削减的成本正是您的目标.在容量 -a 源弧中，穿过切割的那些对应于从 0 到 1 的变化.在容量 -a 到汇弧中，那些穿过切割切割对应于从 1 到 0 的变化.在容量-b 弧中，与切割相交的那些对应于从 0 到 1 的弧的那些实例.

The cost of this cut is exactly your objective. Of the capacity-a from-source arcs, the ones crossing the cut correspond to changes from 0 to 1. Of the capacity-a to-sink arcs, the ones crossing the cut correspond to changes from 1 to 0. Of the capacity-b arcs, the ones crossing the cut correspond to those instances where there is an arc from a 0 to a 1.

这篇关于在二元矩阵中寻找最小成本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！