triangulation.cpp

动态规划算法中的三角剖分

#include<iostream.h>
#include"math.h"
#include"make2db.h"
#include"fstream.h"

double **v,**cc;
int **kay;

double dist(int i,int j)
{
	double dx=v[j][0]-v[i][0];
	double dy=v[j][1]-v[i][1];
	return sqrt(dx*dx+dy*dy);
}

double w(int i,int j,int k)
{
	return (dist(i,j)+dist(j,k)+dist(i,k));
}

double triangulation(int i,int j)
{
	if(cc[i][j]>0)
		return cc[i][j];
	if(i==j)
		return 0;
	cc[i][j]=triangulation(i+1,j)+w(i-1,i,j);
	kay[i][j]=i;
	for(int l=i+1;l<j;l++){
		double u=triangulation(i,l)+triangulation(l+1,j)+w(i-1,l,j);
		if(u<cc[i][j]){
			cc[i][j]=u;
			kay[i][j]=l;
		}
	}
	return cc[i][j];
}

void traceback(int i,int j)
{
	if(i==j)
		return;
	if(kay[i][j]==i)
		traceback(i+1,j);
	else{
		traceback(i,kay[i][j]);
		traceback(kay[i][j]+1,j);
	}
	cout<<"v"<<i-1<<"v"<<kay[i][j]<<"v"<<j<<ends<<","<<ends;
}

void main(void)
{
	int n;
	ifstream fin("data.txt");
	fin>>n;
	make2DArray(cc,n,n);
	make2DArray(kay,n,n);
	make2DArray(v,n,2);
	for(int i=0;i<n;i++)
		fin>>v[i][0]>>v[i][1];
	for(int k=0;k<n;k++)
		for(int j=0;j<n;j++)
			cc[k][j]=0;
		for(int s=0;s<n;s++)
			for(int t=0;t<n;t++)
				kay[s][t]=0;
			triangulation(1,n-1);
			cout<<"最优划分的费用是:"<<cc[1][n-1]<<endl;
			traceback(1,n-1);
			cout<<endl;
			remove2DArray(cc,n);
			remove2DArray(kay,n);
			remove2DArray(v,n);
}