区分n个图片的算法 [英] Algorithm to differentiate n pictures

问题描述

假设你给出长度为k的N位数组。意味着每个向量v i 具有{1,0,0,1 ... 1}（k个分量）的形式等。

Suppose you are give N bit arrays of length k. meaning each vector v_i is of form {1,0,0,1...1} (k components) etc.

现在我想找到最小索引集合S = {I 0，I 1，...，I q-1 }，其中0 < ;当v对S求值时，使得

now I want to find the minimal index set S = {I₀, I₁..., I_q-1}, with 0 <= I_i <= k-1 such that

，其给出二进制序列{v sub [i <0>]，v sub [i <1>]，...}是唯一的对于每个v sub。

when v_i evaluated on S, which gives a binary sequence {v_i[I₀], v_i[I₁] ..} is unique for each v_i.

因此，例如，如果有64个向量{v ₀ ... v <63>集合| S |可以具有尺寸6给定v i 是相当长且充分不同。因为2 ⁶ = 64。

So for example if there are 64 vectors {v₀...v₆₃}, the minimal index set |S| could have size 6 given v_i are pretty long and sufficiently different. Because 2⁶ = 64.

应用程序是给定一个固定的黑白图片列表0 ... 63，知道输入将是那些图片之一，用图片足够大，你只需要检查输入的6个像素，以确定它是哪个图片。

The application is that given a fixed list of black-white pictures, 0...63, and you know the input would be one of those pictures, with picture sufficiently large, you only need to check 6 pixel of the input to figure out which picture it is.

这个问题似乎应该被证明是NP或解决的地方。

This problem seems should already be proved NP or solved somewhere.

任何提示？谢谢。

推荐答案

我无法找到一个NP-hard问题对应这个，虽然我确定是NP -硬。我希望有人可以挖一个，因为我认为我遇到了这个问题在几个不同的guises。

I wasn't able to find an NP-hard problem that corresponds to this, though I'm certain it is NP-hard. I hope someone can dig one up, as I think I have run into this problem in a few different guises. If not, I might attempt a reduction later if I get time.

每列都将图像分为两部分：我们从包含所有图像的单个集合开始，我们的目标是到达一个分区，其中每个部分（在分区中设置）由单个图像组成，并且使用尽可能少的列。

Each column partitions the set of images into two parts; we start with a single set containing all images, and our goal is to reach a partition in which every part (set in the partition) consists of a single image, and which uses the fewest possible columns.

一种方法是制作和解决最低限额封面问题其中地面集由所有k（k-1）/ 2对图像组成，并且对于每个列v_r，我们做出由该列区分的所有图像对组成的集合> - 即所有图像对（i，j），使得v_r [i]！= v_r [j]。然后任何封面将每个图像和每个其他图像区分开，最小尺寸的封面将使用尽可能少的列。

One approach would be to make and solve a Minimum Set Cover problem in which the ground set consists of all k(k-1)/2 pairs of images, and for each column v_r we make a set consisting of all image pairs that this column distinguishes -- i.e. all pairs of images (i, j) such that v_r[i] != v_r[j]. Then any cover will distinguish every image from every other image, and a cover of minimum size will do so using the fewest possible columns.

实际解决这个集合的最快方法封面问题很可能是通过制定和解决 ILP ，但分支和绑定也可以工作，也可以很容易地变成（快速但可能次优）启发式。

The fastest way to actually solve this set cover problem is likely to be by formulating and solving an ILP, but branch and bound would also work, and can also be easily turned into a (fast but possibly suboptimal) heuristic.

无论如何，这里有一些简单的还原规则，您可以在尝试解决问题之前（以及在添加每个列之后，如果使用B& B），通常会减少问题大小有点：

Either way, here are a few simple reduction rules you can apply before trying to solve the problem (and after each column is added, if you use B&B) that will often reduce the problem size a bit:

1. 如果您将其所有的1更改为0，则列提供相同的区别能力，反之亦然。因此，如果列的第一个元素为1，则通过反转列来规范化列。


2. 将所有相同的列折叠到单个列中，因为其中任何列都与其他列一样好。这可以通过首先对它们排序来容易地完成：然后所有相同的列形成单个连续块。


3. 您当然可以删除任何常量列 - 它们无法用于区分图像。
/ li>

4. 如果你有任何一对相同的行，那么没有解决方案：即，即使包括所有k位也不能使你区分这两行（图像）。

1. A column provides the same "distinguishing power" if you change all its 1s to 0s and vice versa. Therefore "canonicalise" the columns by inverting them if their first element is, say, 1.
2. Collapse all identical columns into a single column, since any of them is exactly as good as any other. This can easily be done by first sorting them: then all identical columns form a single contiguous block. Doing this after performing the first reduction will result in more reduction.
3. You can of course delete any "constant columns" -- there is no way they can be of use in distinguishing images.
4. If you have any pair of identical rows, then there is no solution: that is, even including all k bits would not enable you to distinguish these two rows (images).

这篇关于区分n个图片的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！