写点什么

超超超超级详细的多边形游戏问题分析(动态规划)

用户头像
若尘
关注
发布于: 2021 年 06 月 04 日
超超超超级详细的多边形游戏问题分析(动态规划)

多边形游戏

问题简介



  • 首先呢,介绍一下多边形游戏是个什么东东

  • 多边形游戏是一个单人玩的游戏,开始时有一个由 n 个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从 1 到 n 编号。

  • 游戏步骤:

  • 将一条边删除

  • 选择一条边 E 及由 E 连接的 2 个顶点 V1 和 V2

  • 用一个新的顶点取代边 E 以及由 E 连接着的 2 个顶点 V1 和 V2。将由顶点 V1 和 V2 的整数值通过边 E 上的运算得到的结果赋予新顶点

  • 重复以上步骤,直到所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值


我们的问题是: 根据给定的多边形,计算最高分和最底分

问题分析



  • 最优子结构性质

  • 这里呢,它是满足最优子结构性质的,我们不做过多的解释,直接看它的求解方法

  • 递归求解

  • 首先,我们在 p(i, j)在 op[i+s]处断开, 最大值记为 maxf(i,j,s),最小值记为 minf(i,j,s)

  • 因为只有加法和乘法,加法比较简单。对于乘法,可能存在负数,所以我们要对所有可能的结果做讨论,为了计算方便,我们可以定义如下表示 a=m[i,i+s,0]        b=m[i,i+s,1]c=m[i+s,j-s,0]      d=m[i+s,j-s,1]

  • 当 op[i+s]=‘+’m[i,j,0]=a+c         m[i,j,1]=b+d

  • 当 op[i+s]=‘*’m[i,j,0]=min{ac,ad,bc,bd} m[i,j,1]=max{ac,ad,bc,bd}

  • 因此可有如下公式


  • 至于 s 的断开位置,可以取 1 到 j - 1, 如下



接下来,就是超超超超级详细的解题步骤

超详细解题步骤

这里,我们举了这样一个栗子

详细步骤如下


m(1,1,1) = 9m(1,1,0) = 9m(2,1,1) = -4m(2,1,0) = -4m(3,1,1) = 9m(3,1,0) = 9m(4,1,1) = 10m(4,1,0) = 10m(5,1,1) = -10m(5,1,0) = -10




m(1,2) = m(1,1)op(2)m(2,1)op(2) = "+"m(1,2,1) = m(1,1,1) + m(2,1,1) = 5m(1,2,0) = m(1,1,0) + m(2,1,0) = 5


m(2,2) = m(2,1)op(3)m(3,1)op(3) = "+"m(2,2,1) = m(2,1,1) + m(3,1,1) = 5m(2,2,0) = m(2,1,0) + m(3,1,0) = 5


m(3,2) = m(3,1)op(4)m(4,1)op(4) = "+"m(3,2,1) = m(3,1,1) + m(4,1,1) = 19m(3,2,0) = m(3,1,0) + m(4,1,0) = 19


m(4,2) = m(4,1)op(5)m(5,1)op(5) = "*"m(4,2,1) = max{m(4,1,1)*m(5,1,1), m(4,1,1)*m(5,1,0), m(4,1,0)*m(5,1,1), m(4,1,0)*m(5,1,0)} = -100m(4,2,0) = min{m(4,1,1)*m(5,1,1), m(4,1,1)*m(5,1,0), m(4,1,0)*m(5,1,1), m(4,1,0)*m(5,1,0)} = -100


m(5,2) = m(5,1)op(1)m(1,1)m(5,2,1) = m(5,1,1) + m(1,1,1) = -1m(5,2,0) = m(5,1,0) + m(1,1,0) = -1





op(2) = "+"op(3) = "+"m(1,3,1) = max{m(1,1,1)+m{2,2,1}, m(1,2,1)+m(3,1,1)} = 14 (m(1,1,1)+m(2,2,1))m(1,3,0) = min{m(1,1,0)+m{2,2,0}, m(1,2,0)+m(3,1,0)} = 14 (m(1,1,0)+m(2,2,0))



op(3) = "+"op(4) = "+"m(2,3,1) = max{m(2,1,1)+m(3,2,1), m(2,2,1)+m(4,1,1)} = 15 (m(2,1,1)+m(3,2,1))m(2,3,0) = min{m(2,1,0)+m(3,2,0), m(2,2,0)+m(4,1,0)} = 15 (m(2,1,0)+m(3,2,0))



op(4) = "+"op(5) = "*"m(3,3,1) = max{m(3,1,1)+m(4,2,1), max{m(3,2,1)*m(5,1,1), m(3,2,1)*m(5,1,0), m(3,2,0)*m(5,1,1), m(3,2,0)*m(5,1,0)}} = -91 (m(3,1,1)+m(4,2,1))m(3,3,0) = min{m(3,1,0)+m(4,2,0), min{m(3,2,1)*m(5,1,1), m(3,2,1)*m(5,1,0), m(3,2,0)*m(5,1,1), m(3,2,0)*m(5,1,0)}} = -190 (m(3,2,1)*m(5,1,1))



op(5) = "*"op(1) = "+"m(4,3,1) = max{max{m(4,1,1)*m(5,2,1), m(4,1,1)*m(5,2,0), m(4,1,0)*m(5,2,1), m(4,1,0)*m(5,2,0)}, m(4,2,1)+m(1,1,1)} = -10 (m(4,1,1)*m(5,2,1))m(4,3,0) = min{min{m(4,1,1)*m(5,2,1), m(4,1,1)*m(5,2,0), m(4,1,0)*m(5,2,1), m(4,1,0)*m(5,2,0)}, m(4,2,0)+m(1,1,0)} = -91 (m(4,2,0)+m(1,1,0))



op(1) = "+"op(2) = "+"m(5,3,1) = max{m(5,1,1)+m(1,2,1), m(5,2,1)+m(2,1,1)} = -5 (m(5,1,1)+m(1,2,1))m(5,3,0) = min{m(5,1,0)+m(1,2,0), m(5,2,0)+m(2,1,0)} = -5 (m(5,1,0)+m(1,2,0))





op(2) = "+"op(3) = "+"op(4) = "+"m(1,4,1) = max{m(1,1,1)+m(2,3,1), m(1,2,1)+m(3,2,1), m(1,3,1)+m(4,1,1)} = 24 (m(1,1,1)+m(1,2,1))m(1,4,0) = min{m(1,1,0)+m(2,3,0), m(1,2,0)+m(3,2,0), m(1,3,0)+m(4,1,0)} = 24 (m(1,1,0)+m(2,3,0))



op(3) = "+"op(4) = "+"op(5) = "*"m(2,4,1) = max{m(2,1,1)+m(3,3,1), m(2,2,1)+m(4,2,1), max{m(2,3,1)*m(5,1,1), m(2,3,1)*m(5,1,0), m(2,3,0)*m(5,1,1), m(2,3,0)*m(5,1,0)}} = -95 (m(2,1,1)+m(3,3,1))m(2,4,0) = min{m(2,1,0)+m(3,3,0), m(2,2,0)+m(4,2,0), min{m(2,3,1)*m(5,1,1), m(2,3,1)*m(5,1,0), m(2,3,0)*m(5,1,1), m(2,3,0)*m(5,1,0)}} = -194 (m(2,1,0)+m(3,3,0))



op(4) = "+"op(5) = "*"op(1) = "+"m(3,4,1) = max{m(3,1,1)+m(4,3,1), max{m(3,2,1)*m(5,2,1), m(3,2,1)*m(5,2,0), m(3,2,0)*m(5,2,1), m(3,2,0)*m(5,2,0)}, m(3,3,1)+m(1,1,1)} = -1 (m(3,1,1)+m(4,3,1))m(3,4,0) = min{m(3,1,0)+m(4,3,0), min{m(3,2,1)*m(5,2,1), m(3,2,1)*m(5,2,0), m(3,2,0)*m(5,2,1), m(3,2,0)*m(5,2,0)}, m(3,3,0)+m(1,1,0)} = -181 (m(3,3,0)+m(1,1,0))



op(5) = "*"op(1) = "+"op(2) = "+"m(4,4,1) = max{max{m(4,1,1)*m(5,3,1), m(4,1,1)*m(5,3,0), m(4,1,0)*m(5,3,1), m(4,1,0)*m(5,3,0)}, m(4,2,1)+m(1,2,1), m(4,3,1)+m(2,1,1)} = -14 (m(4,3,1)+m(2,1,1))m(4,4,0) = min{min{m(4,1,1)*m(5,3,1), m(4,1,1)*m(5,3,0), m(4,1,0)*m(5,3,1), m(4,1,0)*m(5,3,0)}, m(4,2,0)+m(1,2,0), m(4,3,0)+m(2,1,0)} = -95 (m(4,2,0)+m(1,2,0))



op(1) = "+"op(2) = "+"op(3) = "+"m(5,4,1) = max{m(5,1,1)+m(1,3,1), m(5,2,1)+m(2,2,1), m(5,3,1)+m(3,1,1)} = 4 (m(5,1,1)+m(1,3,1))m(5,4,0) = min{m(5,1,0)+m(1,3,0), m(5,2,0)+m(2,2,0), m(5,3,0)+m(3,1,0)} = 4 (m(5,1,0)+m(1,3,0))





op(2) = "+"op(3) = "+"op(4) = "+"op(5) = "*"m(1,5,1) = max{m(1,1,1)+m(2,4,1), m(1,2,1)+m(3,3,1), m(1,3,1)+m(4,2,1), max{m(1,4,1)*m(5,1,1), m(1,4,1)*m(5,1,0), m(1,4,0)*m(5,1,1), m(1,4,0)*m(5,1,0)}} = -86 (m(1,1,1)+m(2,4,1))m(1,5,0) = min{m(1,1,0)+m(2,4,0), m(1,2,0)+m(3,3,0), m(1,3,0)+m(4,2,0), min{m(1,4,1)*m(5,1,1), m(1,4,1)*m(5,1,0), m(1,4,0)*m(5,1,1), m(1,4,0)*m(5,1,0)}} = -240 (m(1,4,1)*m(5,1,1))



op(3) = "+"op(4) = "+"op(5) = "*"op(1) = "+"m(2,5,1) = max{m(2,1,1)+m(3,4,1), m(2,2,1)+m(4,3,1), max{m(2,3,1)*m(5,2,1), m(2,3,1)*m(5,2,0), m(2,3,0)*m(5,2,1), m(2,3,0)*m(5,2,0)}, m(2,4,1)+m(1,1,1)} = -5 (m(2,1,1)+m(3,4,1))m(2,5,0) = min{m(2,1,0)+m(3,4,0), m(2,2,0)+m(4,3,0), min{m(2,3,1)*m(5,2,1), m(2,3,1)*m(5,2,0), m(2,3,0)*m(5,2,1), m(2,3,0)*m(5,2,0)}, m(2,4,0)+m(1,1,0)} = -185 (m(2,1,0)+m(3,4,0))



op(4) = "+"op(5) = "*"op(1) = "+"op(2) = "+"m(3,5,1) = max{m(3,1,1)+m(4,4,1), max{m(3,2,1)*m(5,3,1), m(3,2,1)*m(5,3,0), m(3,2,0)*m(5,3,1), m(3,2,0)*m(5,3,0)}, m(3,3,1)+m(1,2,1), m(3,4,1)+m(2,1,1)} = -5 (m(3,1,1)+m(4,4,1))m(3,5,0) = min{m(3,1,0)+m(4,4,0), min{m(3,2,1)*m(5,3,1), m(3,2,1)*m(5,3,0), m(3,2,0)*m(5,3,1), m(3,2,0)*m(5,3,0)}, m(3,3,0)+m(1,2,0), m(3,4,0)+m(2,1,0)} = -185 (m(3,3,0)+m(1,2,0))



op(5) = "*"op(1) = "+"op(2) = "+"op(3) = "+"m(4,5,1) = max{max{m(4,1,1)*m(5,4,1), m(4,1,1)*m(5,4,0), m(4,1,0)*m(5,4,1), m(4,1,0)*m(5,4,0)}, m(4,2,1)+m(1,3,1), m(4,3,1)+m(2,2,1), m(4,4,1)+m(3,1,1)} = 40 (m(4,1,1)*m(5,4,1))m(4,5,0) = min{min{m(4,1,1)*m(5,4,1), m(4,1,1)*m(5,4,0), m(4,1,0)*m(5,4,1), m(4,1,0)*m(5,4,0)}, m(4,2,0)+m(1,3,0), m(4,3,0)+m(2,2,0), m(4,4,0)+m(3,1,0)} = -86 (m(4,2,0)+m(1,3,0))



op(1) = "+"op(2) = "+"op(3) = "+"op(4) = "+"m(5,5,1) = max{m(5,1,1)+m(1,4,1), m(5,2,2)+m(2,3,1), m(5,3,1)+m(3,2,1), m(5,4,1)+m(4,1,1)} = 14 (m(5,1,1)+m(1,4,1))m(5,5,0) = min{m(5,1,0)+m(1,4,0), m(5,2,0)+m(2,3,0), m(5,3,0)+m(3,2,0), m(5,4,0)+m(4,1,0)} = 14 (m(5,1,0)+m(1,4,0))


至此,终于计算完毕,那么:max = max{m(1,5,1), m(2,5,1), m(3,5,1), m(4,5,1), m(5,5,1)} = 40max = min{m(1,5,0), m(2,5,0), m(3,5,0), m(4,5,0), m(5,5,0)} = -240



最后,是 Java 代码的实现过程

Java 代码实现

package PolygonGame;
public class PolygonGame {
static int n; // 边和点个数 static int minf, maxf; static int[] v; // 点集 static char[] op; // 边集 static int[][][] m; // 存放最终计算结果 static int[] result; // 存放最大值和最小值 public static void main(String[] args) { n = 4; // 我的案例是: + -7 + 4 * 2 * 5 v = new int[] {Integer.MIN_VALUE, -7, 4, 2, 5}; op = new char[] {' ', '+', '+', '*', '*'}; m = new int[n + 1][n + 1][2]; for (int i = 1; i <= n; i++) { // m[i][j][1] 表示起点为i,长度为j的最大值 m[i][1][1] = v[i]; // m[i][j][0] 表示起点为i,长度为j的最小值 m[i][1][0] = v[i]; } polyMax(); System.out.println("最大值: " + result[0] + "\n最小值: " + result[1]); } /** * * @param i: 链的起点 * @param s: 断开位置 * @param j: 链的长度 */ public static void minMax(int i, int s, int j) { int[] e = new int[n + 1]; // 在op(i+s) 处进行分割 int a = m[i][s][0], // 左半部分最小值 b = m[i][s][1], // 左半部分最大值 r = (i + s - 1) % n + 1, // 取余,防止溢出 c = m[r][j - s][0], // 右半部分最小值 d = m[r][j - s][1]; // 右半部分最大值 if(op[r] == '+') { // 对符号进行判断,加号和乘号的处理方式不同 minf = a + c; maxf = b + d; } else { // 为乘号 // maxf=max{ac, ad, bc, bd} // minf=min{ac, ad, bc, bd} e[1] = a * c; e[2] = a * d; e[3] = b * c; e[4] = b * d; minf = e[1]; maxf = e[1]; for (int k = 2; k < 5; k++) { // 查找最大最小值 if (minf > e[k]) minf = e[k]; if (maxf < e[k]) maxf = e[k]; } } } public static void polyMax() { for(int j = 2; j <= n; j++) // 总长度遍历 for(int i = 1; i <= n; i++) for(int s = 1; s < j; s++) { // 断开位置 // 求m[i][j][1]和m[i][j][0] minMax(i, s, j); if(m[i][j][0] > minf) m[i][j][0] = minf; if(m[i][j][1] < maxf) m[i][j][1] = maxf; } result = new int[2]; result[0] = m[1][n][1]; result[1] = m[1][n][0]; for(int i = 1; i <= n; i++) { if (result[0] < m[i][n][1]) result[0] = m[i][n][1]; if (result[1] > m[i][n][0]) result[1] = m[i][n][0]; } }}
复制代码


最大值: 33最小值: -35
复制代码


好了,到此结束。欢迎大家关注我😀

发布于: 2021 年 06 月 04 日阅读数: 22
用户头像

若尘

关注

还未添加个人签名 2021.01.11 加入

还未添加个人简介

评论

发布
暂无评论
超超超超级详细的多边形游戏问题分析(动态规划)