用C++编写程序 动态规划

//==

#include <iostream>

using namespace std

#include <cmath>

//--

struct Coordinate //顶点

{

float x

float y

}

//--

float Module(Coordinate a,Coordinate b) //求两点的模值

{

float module=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)

return (float)sqrt(module)

}

//--

float W(Coordinate a,Coordinate b,Coordinate c) //权函数

{

return Module(a,b)+Module(b,c)+Module(a,c)

}

//--

void Triangle_Dissect(Coordinate v[11],float m[10][10],int s[10][10],int n) //最优剖分

{

for(int i=1i<ni++)

{

m[i][i]=0

}

for(int l=2l<=n-1l++)

{

for(i=1i<=n-li++)

{

int j=i+l-1

m[i][j]=m[i+1][j]+W(v[i-1],v[i],v[j])

s[i][j]=i

for(int k=ik<=j-1k++)

{

float q=m[i][k]+m[k+1][j]+W(v[i-1],v[k],v[j])

if(q<m[i][j])

{

m[i][j]=q

s[i][j]=k

}

}

}

}

}

//--

bool judge(Coordinate a,Coordinate b,Coordinate v[11],int n) //判断能否构成凸多边形

{

float t[11]

int j=0

int k=0

for(int i=0i<ni++)

{

if(a.x==b.x)

t[i]=v[i].x-a.x

else if(a.y==b.y)

t[i]=v[i].y-a.y

else

t[i]=(v[i].y-a.y)/(b.y-a.y)-(v[i].x-a.x)/(b.x-a.x)

}

for(i=0i<ni++)

{

if(t[i]>0)

j++

if(t[i]<0)

k++

}

if(j==n-2||k==n-2)

return true

else

return false

}

//--

bool input(Coordinate v[11],int n) //输入顶点坐标，并判断能否构成凸多边形旁衡

{

for(int i=0i<ni++)

{

cout<<"输入顶点v"<<i<<"坐贺穗标"

cin>>v[i].x>>v[i].y

}

int t[11]

for(i=0i<ni++)

{

if(i==n-1)

t[i]=judge(v[i],v[0],v,n)

else

t[i]=judge(v[i],v[i+1],v,n)

}

int j=0

for(i=0i<ni++)

{

if(t[i]>0)

j++

}

if(j==n)

return true

else

return false

}

//--

void outputm(float a[10][10],int n) //输出数组m中保存的数据

{

for(int i=1i<ni++)

{

for(int j=1j<nj++)

{

if(j<i)

{

cout.width(16)

cout<<"*"

}

else

{

cout.width(16)

cout<<运拍做a[i][j]

}

}

cout<<endl

}

}

//--

void outputs(int a[10][10],int n) //输出数组s中保存的数据

{

for(int i=1i<ni++)

{

for(int j=1j<nj++)

{

if(j<=i)

{

cout.width(12)

cout<<"*"

}

else

{

cout.width(12)

cout<<a[i][j]

}

}

cout<<endl

}

}

//--

void Triangle_Print(int i,int j,int s[10][10]) //输出最优剖分出的全部三角形

{

if(i==j)

return

Triangle_Print(i,s[i][j],s)

Triangle_Print(s[i][j]+1,j,s)

cout<<"三角形:v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl

}

//--

void main()

{

int n

Coordinate v[11]

float m[10][10]

int s[10][10]

cout<<"输入顶点个数，限定10个"<<endl

cin>>n

if(n>10)

cout<<"输入有误"<<endl

else

{

cout<<"输入各顶点坐标"<<endl

if(input(v,n))

{

Triangle_Dissect(v,m,s,n)

cout<<endl<<"数组m中记录的数据为:"<<endl

outputm(m,n)

cout<<"数组s中记录的数据为:"<<endl

outputs(s,n)

cout<<"最优凸多边形三角剖分为："<<endl

Triangle_Print(1,n-1,s)

}

else

cout<<"不能构成凸多边形"<<endl

}

}

//===

呵呵 这类问题好难 写了一整天啊 学到了很多 还是有收获的

自适应动态规划(Adaptive/Approximate Dynamic Programming，ADP)，又叫近似动态规划，是人工智能和控制领域发展而交汇形成的新兴学科。ADP方法主要包括三种基本类型：启发式动态规划(Heuristic Dynamic Programming，HDP)，双启发式动态规划(Dual Heuristic Programming，DHP)和全局双启发式动态规划(Globalized Dual heuristic Programming，GDHP)。这三种类型都包含三个模块，如果每个模块都用神经网络来代替，这样我们也称这三个模块为三个网络，即评价网络(Critic Network)、模型网络(Model Network)和执行网络(Action Network)。如果我们省略了模型网络，使得执行网络直接与评价网络链隐相连接，这样的结构称棚灶厅为它们的动作依赖(Action-Dependent)形式，即ADHDP，ADDHP，ADGDHP。 ADP一般包括三个部分：动态系统(dynamic system)、评价执行函数(critic performance index function) 环节、执行/控制(action/control)环节，每个环节均可由神经网络来代替。其中动态系统（或称为被控对象）对应于建立的模型，执行/控制环节用来近似最优控制策略，评价执行函数环节是基于Bellman最优性原理进行参数更新，评价网络和执行网络的组合成了一个智能体。执行/控制作用于动态系统, 评价执行函数由动态系统产生奖励或是惩罚作用来影响。执行/控制环节输出控制动作，评价执行函数的输出是基于贝尔曼最优性原理的代价函数值，即以输出代价函数值最小为目标调整执行/控制环节使其输出动作近似最优。动态预测是一种透过运动矢辩余量来描述一张2D图片是如何转换成另外一张2D图片的程序。在视频处理时，图片指的就是邻近的画格。这些运动矢量可以想成是3D空间(2D+时域)投影到2D的结果。对一张图片而言，可以给每一个像素创建一个独特的运动矢量，也可以将邻近的像素聚集成一个区块，并只计算每一个区块的运动矢量。运动矢量的数学模型可以是单纯的平移也可以含括例如3D空间的的转动和缩放等几何运动方式来更妥当地模拟真实摄影机的动态。动态预测和光流法常常被互相混用。它同时也与图像配准和立体匹配有关。事实上上述几种词汇都是在找寻两张图片或视频画格间相对应的点。两图片或画格间相对应的点“通常”是该场景中的同一个点。然而，在作动态预测之前，我们必须定义相似性的比较标准。也就是说，我们需要一个尺度来测量两个点之间的相似程度。在相关领域的研究中，被定义了各种比较标准，像是SAD、MSE，随不同应用和优化需要常常会使用不同的比较标准。

1、描述优解的结构特征。

2、递归地定义一个最优解的值。

3、自底向上计算一个最优解的值。

4、从已计算的信息中构造一个最优解。

一、基本概念

动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

二、基本思想与策略

基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

三、适用的情况

能采用动态规划求解的问题的一般要具有3个性质：

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

---