如何匹配两个函数，使得得分最高

dianyancao

由\(M\)个函数\(f_i(x)\)构成集合\(F=\{f_i(x)|i=1\space to\space M\}\)，
其中\(f_i(x)\)的定义域都为\(X=\{i|i=1\space to\space K\}\)，值域都为\(Y=\{i|i=1\space to\space L\}\)。
\(M,K,L\)有限，且为正整数。

现在，
随机生成在\(1\)到\(M\)之间均匀分布的一个整数\(i\)，从F中选择函数\(f_i(x)\),
随机生成在\(1\)到\(K\)之间均匀分布的一个整数\(n\),

令\(j=1\space to \space n\),对每个\(j\)
随机生成在\(1\)到\(K\)之间均匀分布的一个整数\(k\),
随机生成在\(1\)到\(L\)之间均匀分布的一个整数\(l\),
用整数\(l\)替换\(f_i(k)\)的值。

循环完毕，得到\(f_i(x)\)的值被替换后的函数\(g(x)\)。
___________________________________________________________________

若只有\(F,X,Y\)对应的数据，和\(g\)的输入与输出的对应关系，
如何回答\(g\)是由哪个\(f_i\)生成的？

答案可以是：
不确定，得\(a\)分
确定并且指出\(f_i(x)\)是\(F\)的第几个元素，得\(b=1\)分
错误答案，得\( 0 \)分
其中\( 0 \le a \le b = 1 \)

以上的随机试验重复\(n\)次，当\(n \to \infty \),
如何回答，能使得得分率\(S=\dfrac{总得分}{n}\)最多？

若存在方案使得得分率\(S\)最大，那么该得分率\(S\)是多少？

dianyancao

测试数据

M=32,K=8,L=2
a=0.5,b=1

F={{1,1,2,2,1,1,2,1},{2,1,2,1,2,1,2,2},{1,2,2,1,1,1,1,1},{2,2,2,2,2,1,2,1},{2,2,2,2,1,1,1,1},{2,1,1,2,2,1,1,1},{1,1,2,2,1,2,1,2},{1,2,1,1,1,1,1,1},{2,1,1,1,1,2,1,2},{1,1,2,2,1,2,2,1},{2,2,2,2,1,2,1,1},{2,2,1,1,2,2,1,1},{1,1,2,2,2,2,2,1},{2,1,1,1,1,1,2,2},{1,1,2,2,1,2,2,2},{1,2,1,1,2,2,2,2},{2,1,1,1,2,2,2,2},{2,2,2,2,2,2,2,1},{2,1,1,1,2,2,1,1},{1,2,2,2,2,2,2,1},{1,1,1,1,2,2,1,2},{1,2,2,2,1,1,1,2},{1,2,2,1,1,2,2,1},{2,1,2,1,1,2,2,2},{1,1,2,2,2,2,1,2},{1,1,2,1,2,2,2,1},{1,1,1,2,2,1,1,2},{2,2,1,2,1,1,1,1},{2,2,1,1,2,1,2,1},{1,2,2,2,1,1,2,2},{2,2,1,1,1,1,1,2},{1,2,2,2,1,1,2,2}}

策略总是按最小距离给出答案，不回答不确定
测试100000次，得到0.355546的得分率
这里正确率的误差要如何估计呢？

mathematica测试代码：

1. mM=32;kK=8;lL=2;
   
2. testcount=100000
   
3. 
   
4. 
   
5. correct=0
   
6. xX=Table[i,{i,1,kK}]
   
7. yY=Table[i,{i,1,lL}]
   
8. Table[f[i]=Table[RandomInteger[{1,lL}],{j,1,kK}],{i,1,mM}]
   
9. For[n=1,n<=testcount,++n,
   
10. i=RandomInteger[{1,mM}];
    
11. ff=f[i];
    
12. nn=RandomInteger[{1,kK}];
    
13. For[j=1,j<=nn,++j,
    
14. k=RandomInteger[{1,kK}];
    
15. l=RandomInteger[{1,lL}];
    
16. ff[[xX[[k]]]]=yY[[l]];
    
17. ];
    
18. match=Ordering[Table[Norm[f[j]-ff,1],{j,1,mM}],1];
    
19. If[match[[1]]==i,correct++];
    
20. ];
    
21. N[correct/testcount]

复制代码