如其他帖子所指出的,NxN可以O(n^3)使用2-d kadane算法及时查找矩阵中的最大和子矩形.但是,如果矩阵稀疏,特别是O(n)非零条目,是O(n^3)时候可以打败？
如果它有帮助,对于我感兴趣的当前应用程序,只需要一个解决方案就足以在矩阵的每一行和每一列中假定最多一个非零值.然而,在我未来的应用程序中,这个假设可能不合适(只是稀疏性会持续),无论如何,我的数学直觉是可能存在简单利用稀疏性的良好解决方案,并且不会进一步利用矩阵的事实.对角线和置换矩阵的乘积.
所以有德州扑克电脑游戏,你可以玩8个对手,据说这些电脑游戏中的一些可以告诉你,如果你的对手都是随机的,你的获胜概率.如果有人不知道,在德州扑克中,每个玩家获得2张私人牌,然后最终在中间发出5张公共牌(前3个,然后是1个,然后是1个),获胜者是能够玩牌的玩家.他们可以使用他们的2张私人卡和5张社区卡的任意组合制作最好的5张牌扑克牌.在奥马哈,每位玩家获得4张私人牌,还有5张公共牌,而获胜者是能够使用2张私人牌和3张公共牌制作最佳5张牌扑克牌的玩家.
所以,在德州扑克中,对于任何一个玩家的私人手牌,有超过10 ^ 24种方式可以处理8个对手的私人手牌和5张社区牌.那么假设你的8个对手是随机的,他们如何计算/估计你在开始时获胜的概率呢？在奥马哈,情况甚至更糟,尽管我从未见过奥马哈电脑游戏实际上可以让你对8个随机对手的手牌.但无论如何,是否有任何编程技巧可以完成这些获胜概率计算(或者说,在3或4位小数点内正确),比蛮力更快？我希望有人可以在这里回答谁在编写这样一个程序之前运行得足够快,因此为什么我在这里问.而且我希望答案不涉及随机抽样估计,因为总是有一个很小的可能性.