问题:我们必须用集合 S 中的字符填充大小为 m*n 的 2D 网格,以使生成的网格中不同子矩阵的数量接近给定数量 k。
这个问题来自http://www.codechef.com/JULY14/problems/GERALD09
限制:
1<=n,m<16
1<=k <=m*n*m*n
|S|=4
时间限制=0.1 秒
假设:如果两个子矩阵的维度不同或至少有一对在其对应位置的字符不匹配,则它们是不同的。
我的方法:我们可以从随机网格和循环开始,同时找到可接受的解决方案,并且在每次迭代中,我们可以根据当前状态增加/减少随机性(但我们可以停留在局部最优状态)。
但问题是我不知道计算子网格中不同子矩阵数量的有效方法。我尝试用散列法进行计数,这非常快( O(n 2 m 2 )*生成/搜索的成本子网格的哈希值)。但是由于哈希值的冲突,这种方法并没有给出准确的答案,即使在使用@Vaughn Cato 的评论更正它之后,我也可以进行 15-25 次迭代以获得最佳状态查找,但这还不够。
最近,我了解到模拟退火可以用来解决这类问题。
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
我正在寻找任何有效的方法来解决这个优化问题。
提前致谢。