我有一个非常有趣的算法问题(不是图像处理!),但我还是不理解。请帮帮我。
问题:
有10个大小为4×4的模式(二进制)。例如,
0001
0011
0111
0001
现在,有一个16×16的棋盘(初始设为0)。
现在,我们选择10个模式中的一个,并将其放置在16×16的棋盘上的随机位置上(位置和模式均随机选择)。例如:
000000000....
000100000....
001100000
001100000
000100000
000000000
000000000
........
接下来,每个值都将以10%的概率翻转。例如,
000000000....
000100010....
001000000
001100100
000100000
010000000
000000100
........
这里的问题是猜测最初存在的模式(允许70%以上的准确率)。换句话说,在100个查询中,必须成功70次或以上。
我的第一种方法是计算每个可能补丁和模式的准确率。例如,
int NOISE_IMAGE[16][16];
int PATTERN[10][4][4];
double getScore(int x, int y, int pIdx){
int confusion[2][2] = { 0, };
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
confusion[NOISE_IMAGE[x + i][y + j]][PATTERN[pIdx][i][j]]++;
}
}
return (double)(confusion[0][0] + confusion[1][1]) / 16.;
}
void solve(){
for (int pattern = 0; pattern < 10; pattern++){
for (int x = 0; x < 14; x++){
for (int y = 0; y < 14; y++){
double score = getScore(x, y, pattern);
}
}
}
}
然而,这种方法结果灾难性。我认为这是因为模式中的零越多,分数就越高。 成功的方法只计算模式为1的区域中的差异。
int getScore(int x, int y, int pIdx){
int confusion[2][2] = { 0, };
for (int i = 0; i < 4; i++){
for (int j = 0; j < 4; j++){
confusion[NOISE_IMAGE[x + i][y + j]][PATTERN[pIdx][i][j]]++;
}
}
return confusion[1][1] - confusion[0][1];
}
我不理解这个公式是怎么得出来的。为什么我们不需要考虑模式为零的区域?
经过更多的研究,我得到了以下的公式:
我们假设:
1 (pattern) | 0 (pattern) | |
---|---|---|
1 (noise image) | a | c |
0 (noise image) | b | d |
(9/10)(a+d) * (1/10)(b+c) 简而言之,
9(a+d)/1016 所以,它不应该与a+d成比例吗?但答案是与a-b成比例。
我的问题是,在上述问题中,为什么答案与a-d成比例,为什么在没有考虑它时,正确的答案是0?请帮我解决这个问题。