(Leet Code) Minimax 系列问题题解 | PY的个人博客
何为Mnimax，它是用在决策轮、博弈论和概率论中的一条决策规则。它被用来最小化最坏情况下的可能损失(wiki)。
上面的概念描述可能看起来令人费解，我们可以使用一个抽象的游戏来理解它：
现在有n堆金子排列成一条直线，每堆都有其对应的价值p[i]。现在两个人来分金子，每次只能从余下的金子中取一堆，并且这一堆只能位于最左边或最右边。现在两人按照这个规则交替取金子，并且两个人都经量想让自己最终获得更多的金子。
上面这个游戏其实是一个Zero-sum game，在zero-sum游戏中，游戏参与方各自的收益是冲突的，某个参与者收益的增加必然导致其他参与者收益的减少。所有游戏参与者的收益和损失的和永远为一个固定的值(通常可以看做是0)。
那么这个游戏和Minimax有什么关系了，我们这样来分析，假设参与分金子的两个人是A和B。令P[i][j]表示当还剩下[i-j]这几堆金子时，第一个取的人能获得的最大收益。sum[i][j]表示[i-j]金子的价值总和。可以得到如下的公式：
Read full article from (Leet Code) Minimax 系列问题题解 | PY的个人博客
No comments:
Post a Comment