算法篇-4-动态规划-凸多边形最优三角剖分&图像压缩最优分段&电路布线_有n个顶点的凸多边形三角剖分的方法数

本系列所有代码https://github.com/YIWANFENG/Algorithm-github

凸多边形最优三角剖分

多边形有一系列首尾相连的直线段组成，多边形的三角剖分是指将多边形分割成互不相交的三角形的弦的集合。（若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。在有n个顶点的凸多边形的三角剖分中，恰有n-3条弦和n-2个三角形。）

给定凸多边形P={V0,V1,V2,V3....Vn-1},以及定义在由凸多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角部分，使得该三角剖分所对应的权，及三角剖分中诸三角形上权之和为最小。

假设w(ViVjVk) =|ViVj|+|VjVk|+|VkVi|,|ViVj|表示Vi到Vj的距离，那么此W对应的为求最小弦长三角剖分。

如图：

 

{//补充关于语法树，可不了解

凸多边形{V0，V1，...Vn-1}的三角剖分可用语法树表示，

V0V6外其他边全是语法树的一个叶节点。V0V6是树根所在。

三角形V0V3V6,凸多边形{V0，V1，...V3}与{V3，V4,...V6}。而弦V0V3与V3V6为根的两个儿子，以V0V3与V3V6为根的子树表示凸多边形{V0，V1，...V3}与{V3，V4,...V6}的三角剖分。}

 

 

 

三角形剖分多边形，反过来想其实就是有条件的用三角形组成该多边形，正过来想是将一整个多边形通过有条件加弦使其变为多个小的多边形，进而化为多个三角形。条件即与权值函数有关。原多边形的权值等于子多边形的权值加上该划分三角形的权值。

而当选取某点连线加弦时，可能会遇到多边形的退化，例如:V0V6为基础，第三点为V5，这样形成了的是多边形{V5, V4, V3, V2, V1, V0}与退化多边形{V6，V5}与三角形V0V6V5。我们将该退化的多边形权值记为0。那么：

定义t[i][j]，1<=i<j<=n为凸子多边形{Vi-1,Vi,....,Vj}的最优三角剖分所对应的权函数值。

设退化的多边形{Vi-1,Vi}具有权值0.那么我们要的结果是凸(n+1)边形的最优权值t[1][n]

自底向上分析易得

t[1][1] = 0,t[2][2] =0,....t[n][n] = 0;

t[1][2] = t[1][1]+t[2][3] + w(V0,V1,V3)

 依据题目要求选取，我们在这里取最小

....

 

所以可得公式

Code:

int weight(int i,intj,int k) {
       //根据题意决定
       //这里我随便
       return abs(k+k-i-j);
}
 
void MinWeightTri(int n,int t[][N+1],int s[][N+1])
{
       //计算n+1边形关于weight的最优划分
       //t[i][j] {Vi..Vj}多边形权值
       //s[i][j] 划分使用的顶点
       for(int i=1;i<=n;i++) t[i][i]=0;     //退化多边形设置
       for(int r=2;r<=n;r++) {                       //每斜行
              for(inti=1;i<=n-r+1;++i) {         
                     int j = i+r-1;
                     t[i][j]=t[i][i]+t[i+1][j]+weight(i-1,i,j);
                     s[i][j]=i;
                     for(int k=i+1;k<i+r-1;++k) {//该层最优
                            intu=t[i][k]+t[k+1][j]+weight(i-1,k,j);
                            if(u<t[i][j]){
                                   t[i][j]=u;
                                   s[i][j]=k;
                            }
                     }    
              }
       }    
}
 
void Traceback(int i,intj,int s[][N+1]) {
       //输出选择的构成三角的顶点
       if(i==j) return ;
       Traceback(i,s[i][j],s);
       cout<<s[i][j]<<" ";
}

图像压缩最优分段

计算机中常用像素灰度值序列{p1,p2,p3,p4...pn}表示图像。Pi,1<=i<=n,表示像素点i的灰度值，通常灰度值的范围是0-255，需用八位表示。

 

图像变位压缩将存储格式将所给的像素点序列{p1,p2,p3,p4...pn}分割成m个连续段S1,S2,Sm。第i个像素段Si(1<=i<=m)有L[i]个像素，且该段中每像素只用b[i位表示，

设t[i] = ,（前i段共需多少位存储）

则第i个像素段Si={Pt[i]+1,...,Pt[i]+l[i]},1<=i<=m.

设hi表示第i段的像素存储其色彩所占位数时每个需要的最大位数。则256色是8位，也就是说每个像素存其占位不大于3位。（1像素等于几个位表示其色阶+几个位表示其色阶占用了几位），限制每段不超过256个元素。则每一段需要存储空间为L[i]*b[i]+11

（11=8位’2^8=256,标志此段含多少个’ + 3位’2^3=8，表示每像素数据占几位’）

求如何分段才可使图像占用空间最小。

 

假设我们已经分好了前i个像素的最优分段，记为S[i],那么加上第i+1个像素的最优分段是何样的呢。

再假设第i+1个像素加上时最后面的最优分段为S[i+1]={Pk,...Pi+1},((i+1)-255)<=k<=I+1 ,因为每段最多256个。所以每加一像素可以来测试256种情况看这些哪种最优分段即可。

 

Code:

 
int Length(int i) {
       //求该像素占用几位空间
       int k=1;
       i/=2;
       while(i>0) {
              k++;
              i/=2;
       }
       return k;
}
void Compress(int n,intp[],int s[],int L[],int b[],int bseg[])
{
       //n像素数，p[]每个像素的值
       //s以i为最后元素的所有分段的元素占用位数
       //L[i]以i为最后元素的分段与之前分段的元素数
       //b[]每像素占用的位数 
       //bseg[]以i为最后元素的分段像素最大占用位数
        
       int Lmax = 256,header=11;
       s[0]=0;
       for(int i=1;i<=n;i++) {
              b[i]=Length(p[i]);
              int bmax = b[i];
              s[i]=s[i-1]+bmax;
              L[i]=1;
              for(intj=2;j<=i&&j<=Lmax;++j){
                     if(bmax<b[i-j+1]) bmax = b[i-j+1];
                     if(s[i]>s[i-j]+j*bmax) {
                            s[i]=s[i-j]+j*bmax;
                            L[i]=j;
                            bseg[i]= bmax;
                     }
              }
              s[i]+=header;        
       }    
}
 
void Traceback(int n,int&i,int s[],int L[])
{
       if(n==0) return ;
       Traceback(n-L[n],i,s,L);
       s[i++]=n-L[n]; //传出每分段开始位置
       //cout<<s[i-1]<<endl;
}
void Print(int s[],intL[],int bseg[],int n)
{
       cout<<"理想值是"<<s[n]<<endl;
       int m =0;
       Traceback(n,m,s,L);
       s[m]=n;
       cout<<"分成"<<m<<"段\n";
       for(int j=1;j<=m;j++) {
              L[j]=L[s[j]];
              bseg[j]=bseg[s[j]];
       }
       for(int j=1;j<=m;j++) {
              cout<<"分段大小："<<L[j]<<"该段每元素占位 "<<bseg[j]<<endl;
       }
}

 电路布线

在一块电路板的上、下两端分别有n个接线柱。根据电路设计，要求用导线(i,π(i)) 将上端接线柱i与下端接线柱π(i)相连，如下图。其中，π(i),1≤ i ≤n,是｛1,2,…,n｝的一个排列。导线(I, π(i))称为该电路板上的第i条连线。对于任何1 ≤ i ≤ j ≤n,第i条连线和第j条连线相交的充要条件是π(i)>π(j).

 在制作电路板时，要求将这n条连线分布到若干绝缘层上。在同一层上的连线不相交。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets = ｛i，π(i)，1 ≤ i ≤ n｝的最大不相交子集。

 

参考：http://blog.csdn.net/liufeng_king/article/details/8671407

记N(i,j) ={t|(t, π(t)) ∈ Nets,t ≤ i, π(t) ≤ j }. N(i,j)的最大不相交子集为MNS（i,j）Size(i,j)=|MNS(i,j)|。

总结来说：

设size[i][j]为上端接线柱i与下端接线柱j前的最大不相交子集，则：

1. 若i与j不相连，则i与j前的最大不相交子集等于i与j - 1前或i - 1与j前的最大不相交子集的最大值，即size[i][j] = max(size[i][j - 1], size [i - 1][j])

2. 若i与j相连，则i与j前的最大不相交子集等于i -1与j - 1前的最大不相交子集加1，

即size [i][j] =size [i - 1][j - 1] + 1

 

Code:

void MNS(int C[],intn,int **size)
{
       //C[i] = Pi(i) i对应的下接线柱
       //n 上接线柱个数
       //size[][] 保存最大不相交子集的元素数 
       for(int j=0;j<C[1];j++)
              size[1][j]=0;
 
       for(int j=C[1]; j<=n; j++)
              size[1][j]=1;
 
       for(int i=2; i<n; i++)     {
              for(int j=0;j<C[i]; j++)
                     size[i][j]=size[i-1][j];//当i<c[i]的情形
              for(int j=C[i];j<=n; j++)
                     //当j>=c[i]时，考虑(i，c[i])是否属于MNS(i,j)的两种情况
                     size[i][j]=size[i-1][j]>(size[i-1][C[i]-1]+1)?size[i-1][j]:(size[i-1][C[i]-1]+1);
       }
       size[n][n]=max(size[n-1][n],size[n-1][C[n]-1]+1);
}
 
void Traceback(intC[],int **size,int n,int Net[],int& m)
{
       //C[i] = Pi(i) i对应的下接线柱
       //n 上接线柱个数
       //size[][] 保存最大不相交子集的元素数
       //Net 结果
       // m 连线数
       int j=n;
       m=0;
       for(int i=n;i>1;i--) {
              if(size[i][j]!=size[i-1][j]){ //此时，(i,c[i])是最大不相交子集的一条边
                     Net[m++]=i;
                     j=C[i]-1;//更新扩展连线柱区间
              }
       }
       if(j>=C[1]) {  //处理i=1的情形
              Net[m++]=1;
       }
}