寻找最低成本的二元矩阵 [英] Finding minimum cost in a binary matrix

问题描述

考虑A N * N二进制矩阵。此矩阵的每个单元具有至多4邻居（如果存在）。我们称这种基质不相容的两个小区，如果他们是邻居，它们的值不相等。我们将支付$ B每一个不兼容的对。我们也可以用支付$一个改变单元格的值。

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.

我已经用回溯，发现 0的算法（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?

推荐答案

这个想法是由于基利，波蒂厄斯和Seheult。对待矩阵作为获能向图，顶点对应矩阵的元素和弧从每个顶点到它的四个邻国，每个容量的 B 的。引入两个以上的顶点，源极和一个接收器，和容量的圆弧的一的：从源到每个顶点与对应的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.

该切割的成本究竟是你的目标。在能力中的在的从源弧，那些穿越切割对应于从0变为1的能力的在应用于散热器弧线，那些穿越切割对应于从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屋！