算法来区分N个画面 [英] Algorithm to differentiate n pictures

问题描述

假设你是给长度为k的N比特阵列。这意味着每个向量v <子>我的形式{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 ₀ ，我 ₁ ...，I <子> Q-1 } ，用0℃= I _我＆LT; = K-1这样

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

当V <子>我评估了S，它给出了一个二进制序列{V <子>我 [I ₀ ]，V <子>我< /分> [我 ₁ ] ..}是唯一的各V <子>我。

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 <子> 0 ... v ₆₃ }，设置最低指数| S |有容量的6给出v <子>我是pretty的长期和充分的不同。由于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难的问题，但我敢肯定它是一个NP难。我希望有人能挖一上来，我想我已经在几个不同的形式遇到这个问题。如果不是这样，我可能会尝试降低以后，如果我有时间。

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 [Ⅰ]！= 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. 在A柱提供了相同的鉴别能力，如果你改变它的全1到0，反之亦然。因此，canonicalise列颠倒他们，如果他们的第一个元素是，比如说，1。
2. 关闭全部相同的列成一列，由于它们是完全一样好其他。这很容易做到，首先对它们进行排序：那么所有相同的列形成一个连续的块。执行第一还原后这样做将导致更多的降低。
3. 您当然可以删除任何常数列 - 也没有办法，他们可以在区分图像使用
4. 如果您有任何对相同的行，那么有没有办法解决：那就是，甚至包括所有的k位不会使您能够区分这两种行（图像）

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