动态规划-多边形游戏

发表于： 分类于：
字数： 1515 阅读：≈ 4分钟 浏览：

算法思想：动态规划

实际问题：多边形游戏

编写语言：Java

前言

多边形游戏问题是矩阵连乘的最优计算次序问题与凸多边形最优三角剖分问题的推广。我在解决凸多边形最优三角剖分问题时偶然间看到了这个结论，便跳过了该问题，直接解决其推广的问题，即多边形游戏问题。对于凸多边形最优三角剖分问题有兴趣的读者，可以自行百度。

问题描述

有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符。每条边被赋予一个运算符+或*。所有边依次用整数1到n编号。 游戏规则：

  1. 删去一条边
  2. 后续步骤按以下方式操作：
  • 选择一条边E及边E的两个顶点v1和v2
  • 用一个新的顶点v取代边E及由E连接着的2个顶点，将2个顶点上的数值由E上的运算符获得结果，病赋值给新的顶点v。最后，所有的边都被删除，游戏结束，得到游戏分数(最后顶点上的整数值)

问题：对于给定的多边形，计算最高得分

关键特征

设给定的多边形的顶点和边的顺时针序列为 op[1], v[1], op[2], v[2], …, op[n], v[n]。其中 op[i] 表示第 i 边所对应的运算符，v[i] 表示第 i 个顶点上的数值，1 <= i <= n。

在所给定的多边形中，从顶点 i 开始，长度为 j(链中有 j 个顶点) 的顺时针链 p(i, j) 可表示为 v[i], op[i + 1], …, v[i + j - 1]。如果这条链的最后一次合并运算发生在 op[i + s] 处，则可在 op[i + s] 处将链分为两个子链 p(i, s) 和 p(i + s, j - s)。

设 m1 是子链 p(i, s) 内部合并得到的值，设 a 和 b 是子链 p(i, s) 内部合并可能得到的最小值和最大值；设 m2 是子链 p(i + s, j - s) 内部合并得到的值，设 c 和 d 是子链 p(i + s, j - s) 内部合并可能得到的最小值和最大值。则有：a <= m1 <= b, c <= m2 <= d。而两个子链合并得到的结果 m = (m1)op i + s 。分析运算符的情况可得：

  1. 当op[i + s] = ‘+‘时，显然有 a + c <= m <= b + d。即链 p(i, j) 合并的最优性可由子链 p(i, s) 和 p(i + s, j - s) 的最优性推出。且最大值对应子链的最大值，最小值对应子链的最小值。
  2. 当op[i + s] = ‘*‘时，考虑到 v[i] 可以取负整数，显然有 min{ac, ad, bc, bd} <= m <= max{ac, ad, bc, bd}，亦可由子链的最有性推出原链的最优性。

综上，可得多边形游戏问题满足最优子结构性质

递归结构

设 m[i, j, 0] 是链 p(i, j) 合并的最小值，m[i, j, 1] 是链 p(i, j) 合并的最大值，并设最优合并在 op[i+s] 处，为方便起见，记：a=m[i, i+s, 0], b=m[i, i+s, 1], c=m[i+s, j-s, 0], d=[i+s, j-s, 1]，则关系式满足：

  • 当 op[i+s]=’+’, min(i, j, s) = a+c, max(i, j, s) = b+d
  • 当 op[i+s]=’*’, min(i, j, s) = min(ac, ad, bc, bd), max(i, j, s) = max(ac, ad, bc, bd)

由此可知 m[i, j, 0]=min(min(i, j, s)), m[i, j, 1]=max(max(i, j, s))，其中 1 <= s <= j - 1，这是个循环求值的过程。

Java代码 

//本代码所用示例为：+ -7 + 4 * 2 * 5
public class PolygonGame
{
    static int n; //边和点个数
    static int minf, maxf;
    static int[] v; //点集
    static char[] op; //边集
    static int[][][] m; //存储最终计算结果

    public static void main(String[] args)
    {
        n = 4;
        //以下所有数组下标为0的都不使用
        //构造出的多边形的最终结果：+ -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][0]：表示链的起点为i，长度为j时的结果最小值
            m[i][1][0] = v[i];
            //m[i][j][1]：表示链的起点为i，长度为j时的结果最大值
            m[i][1][1] = v[i];
        }
        int result = polyMax();
        System.out.println(result);
    }

    /**
      * 参数含义：
      * i：链的起点
      * s：断开位置
      * j：链长度
      *
    */
    public static void minMax(int i,int s,int j)
    {
        int[] e = new int[n + 1];
        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
        {
            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 int polyMax()
    {
        for(int j = 2; j <= n; j++) //链的长度
            //链的起点，多边形是封闭的，不会存在什么问题
            for(int i = 1; i <= n; i++)
                for(int s = 1; s < j; s++) //断开的位置
                {
                    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;
                }
        int temp = m[1][n][1];
        for(int i = 1; i <= n; i++)
            if(temp < m[i][n][1])
            {
                temp = m[i][n][1];
            }
        return temp;
    }
}

运行结果

结果示例