c++ - 网格中的高效方法

标签 c++ algorithm optimization counting simulated-annealing

<分区>

关闭。这个问题需要debugging details .它目前不接受答案。

编辑问题以包含 desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem .这将有助于其他人回答问题。

关闭 8 年前。

Improve this question

问题:我们必须用集合 S 中的字符填充大小为 m*n 的二维网格，使得结果网格中不同子矩阵的数量接近给定数量 k。
本题来源于http://www.codechef.com/JULY14/problems/GERALD09

限制:
1<=n,米<16
1<=k <=m*n*m*n
|S|=4
时间限制=0.1秒

假设:如果两个子矩阵的维度不同，或者至少对应位置的一对字符不匹配，则这两个子矩阵是不同的。

我的方法:我们可以从随机网格开始，然后循环，同时找到可接受的解决方案，在每次迭代中，我们可以根据当前状态增加/减少随机性(但我们可以停留在局部最佳状态)。

但问题是我不知道计算子网格中不同子矩阵数量的有效方法。我尝试使用散列法进行计数，速度非常快( O(n² m²)*生成/搜索子网格哈希值的成本)。但是由于散列值的冲突，这种方法没有给出准确的答案，即使在使用@Vaughn Cato 的评论更正它之后，我也可以进行 15-25 次迭代以找到最佳状态，但这还不够。

最近了解到模拟退火可以用来解决这类问题。
http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6
我正在寻找任何有效的方法来解决这个优化问题。

提前致谢。

最佳答案

我认为他们会在某个时候发表一篇社论，但对于这个特定问题，这里有一个可能的想法:

我在本地为特定 n 生成了所有可能数量的子矩阵和 m . 对于 n=m=3我只有 11来自 81可能性。对于 n=3,m=4我只有 19不可能144值。更重要的是，当我生成值时，我获得了所有 19一开始的可能选项 - 在 263000 之后可能的矩阵 16M我已经有了。 (我是按字典序生成的)

因此，我认为，一种可能的解决方案可能是预先计算尽可能多的 K 的不同值。对于给定的 n 可以实现和 m , 保存随机生成器的种子或以其他方式保存你需要的 O(1)每个 n-m-k 的字符三元组，对于特定的测试用例，只需检查两个相邻值 - 首先是 k比给定的更大和更小。

此外，由于可能的数量 K值不大，可以用其他方式生成它们:给定 K 的所有可能值对于 nxm表，连同适当的表，我们只能通过下一行中的值回溯，并尝试获得具有所有不同值的所有可能矩阵 K对于 nx(m+1) .

关于c++ - 网格中的高效方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24759386/

上一篇：c++ - omp 最大减少与索引的存储

下一篇：c# - 在类里面达到类功能？

相关文章：

c++ - 为什么 C++ 编译器允许 extern 关键字与定义相结合？

c# - 版本控制算法

.net - 为什么 LINQ to objects 中的 Skip() 没有优化？

algorithm - rabin karp算法中 "h"代表什么？

python - 优化python文件比较脚本

machine-learning - Scikit-learn:在 GridSearchCV 中评分