精华内容
下载资源
问答
  • 状态空间

    千次阅读 2015-05-25 15:27:52
    1. 定义 状态变量(state variables)是指在系统中所含变量个数最少的变量,也就是决定系统状态的最小数目的变量的有序集合,有时也称为状态向量(state vector),例如表示天体运动...状态空间(State Space)是系
    1. 定义
    状态变量(state variables)是指在系统中所含变量个数最少的变量,也就是决定系统状态的最小数目的变量的有序集合,有时也称为状态向量(state vector),例如表示天体运动状态的位置和速度的变量。状态变量表示系统某一时刻的值,在t=0时刻的值称为系统的初始状态变量。
    在动态态系统数学公式
     是状态变量或者向量。
    状态空间(State Space)是系统的全部可能状态的集合。状态空间表示法即为一种将物理系统表示为一组输入、输出及状态的数学模式,而输入、输出及状态之间的关系可用许多一阶微分方程来描述[维基百科]。
       如果系统的外输入为已知,那么利用状态向量(空间)的现时值就能完全确定系统在未来各时刻的运动状态,通过状态变量描述能建立系统内部状态变量与外部输入变量和输出变量之间的关系。以状态和操作符为基础,从某个初始状态开始,每次加一个操作符,递增地建立起操作符的试验序列,直到达到目标状态为止,建立状态空间模型(state space models)。状态空间模型在现代控制、经济、空间科学等多领域得到广泛[1] [2]。
     反映状态变量与输入变量间因果关系的数学描述称为状态方程,而输出变量与状态变量和输入变量间的变换关系则由量测方程来描述[3]。


    2. 状态空间模型的R软件包
    R软件是一款开源统计软件,在统计、经济等领域中有广泛的应用。相关状态空间模型软件包有KFAS、MARSS、dlm等。
    (1)KFAS软件包
    KFAS软件包具有高斯、泊松和二项式状态空间模型的模拟,卡尔曼滤波,平滑,预报等功能[4]。
    (2)MARSS
    MARSS软件包提供多元状态空间自回归模型的最大似然参数估计功能[5],用于研究线性统计动态系统。MARSS模型包含一个处理模型(Process model)和一个观测模型(Observation Model),处理模型是一个多元一阶自回归过程,数学形式为:
    观测方程为:
     
    (3)dlm
    软件包dlm具备线性状态模型的贝叶斯估计、极大似然估计、卡尔曼滤波与平滑等功能[6] [7],对应的动态线性模型为[8]:

    参考文献
    1.Hyndman, R.J., et al., Forecasting with Exponential Smoothing: The State Space Approach. 2008: Springer.
    2.Commandeur, J.J.F. and S.J. Koopman, An Introduction to State Space Time Series Analysis. 2007: OUP Oxford.
    3.Grewal, M.S. and A.P. Andrews, Kalman Filtering: Theory and Practice Using MATLAB. 2011: Wiley.
    4.Durbin, J. and S.J. Koopman, Time Series Analysis by State Space Methods: Second Edition. 2012: OUP Oxford.
    5.Holmes, E.E., E.J. Ward, and K. Wills, MARSS: Multivariate Autoregressive State-space Models for Analyzing Time-series Data. R Journal, 2012. 4(1): p. 11-19.
    6.Petris, G. and S. Petrone, State Space Models in R. Journal of Statistical Software, 2011. 41(4): p. 1-25.
    7.Petris, G., S. Petrone, and P. Campagnoli, Dynamic Linear Models with R. 2009: Springer.
    8.Petris, G., An R Package for Dynamic Linear Models. Journal of Statistical Software, 2010. 36(12): p. 1-16.
    展开全文
  • 状态空间模型

    万次阅读 2016-02-03 17:50:30
    一、状态空间模型简述 状态空间模型是动态时域模型,以隐含着的时间为自变量。状态空间模型包括两个模型: 一是状态方程模型,反映动态系统在输入变量作用下在某时刻所转移到的状态; 二是输出或量测方程模型,它将...
    
    一、状态空间模型简述
    状态空间模型是动态时域模型,以隐含着的时间为自变量。状态空间模型包括两个模型:

    一是状态方程模型,反映动态系统在输入变量作用下在某时刻所转移到的状态;
    二是输出或量测方程模型,它将系统在某时刻的输出和系统的状态及输入变量联系起来。


    状态空间模型分类

      状态空间模型按所受影响因素的不同分为:
    (1)确定性状态空间模型
    (2)随机性状态空间模型

      状态空间模型按数值形式分为:
    (1)离散空间状态模型
    (2)连续空间状态模型

    状态空间模型按所描述的动态系统可以分为:
    (1)线性的与非线性的
    (2)时变的与时不变的

    5.jpg (105.47 KB, 下载次数: 15)

    下载附件

    2015-6-11 14:22 上传



    二、系统的状态空间
    离散事件随机性系统的概念是系统理论中最基本的概念。

    离散事件随机性系统的状态,是指系统内部的可能运动状态和可能储能状态。系统在k=k0时刻的状态,是在k<k0时以系统内部储能的积累结果,并在k=k0时以系统要素储能的方式表现出来,还将影响系统在k>k0时的外部行为。


    用随机向量序列来描述系统在任一时刻的状态向量,称为状态向量法,也称为状态空间法。状态向量表示为:

    6.jpg (10.91 KB, 下载次数: 15)

    下载附件

    2015-6-11 14:24 上传



    其中

    7.jpg (6.88 KB, 下载次数: 14)

    下载附件

    2015-6-11 14:24 上传

    (k=1,2,1…,n)为第i个状态向量。


    三、系统的输入输出

    输入输出状态概念

    引入状态向量是为了对系统内部结构进行数学描述,但在许多情况下,系统的状态是无法直接量测到的,有时甚至全部不能量测到。在实际工作中,能量测到的量之势系统的输入与输出。

    输入输出变量表示
    系统的输入也是随时间而变的一组变量,表示为:

    8.jpg (9.92 KB, 下载次数: 13)

    下载附件

    2015-6-11 14:26 上传



    称为输入向量,其分量

    9.jpg (8.07 KB, 下载次数: 12)

    下载附件

    2015-6-11 14:27 上传

    (i=1,2,…,r)称为输入变量。

    系统所受的随机干扰也是随时间而变的一组变量,表示为

    10.jpg (11.01 KB, 下载次数: 15)

    下载附件

    2015-6-11 16:02 上传

    称为系统的动态模型噪声,它是系统的一种特殊输入向量。

    系统的输出也是随时间而变的一组变量,表示为:

    11.jpg (9.29 KB, 下载次数: 11)

    下载附件

    2015-6-11 16:31 上传

    称为输出向量,其分量     (i=1,2,…,m)称为输入变量。

    量测系统也会受到随机噪声的污染,表示为:

    12.jpg (8.93 KB, 下载次数: 15)

    下载附件

    2015-6-11 16:32 上传


    称为系统的量测噪声。



    四、状态空间模型


    状态空间模型定义
    状态空间模型是描述动态系统的完整模型,它表达了由于输入引起系统内部状态的变化,并由此使输出发生的变化。


    状态空间模型的不同形式
    如,线性时不变模型的状态方程可表示为:

    13.jpg (5.84 KB, 下载次数: 10)

    下载附件

    2015-6-11 16:34 上传


    输出方程为:

    14.jpg (3.36 KB, 下载次数: 12)

    下载附件

    2015-6-11 16:34 上传




    五、状态空间模型的建立

    • 例 1   
    某养鱼场为了反映池塘鱼种的变化,请你帮助建立状态空间模型。

    解答:
    (1)取状态向量X(k)为k时刻3个鱼种的数量:

    15.jpg (19.19 KB, 下载次数: 13)

    下载附件

    2015-6-11 16:39 上传

    输入向量为:

    16.jpg (25.87 KB, 下载次数: 14)

    下载附件

    2015-6-11 16:39 上传



    (2)状态转移矩阵

    17.jpg (8.44 KB, 下载次数: 15)

    下载附件

    2015-6-11 16:40 上传

    式中: p1,p2,p3为鲫鱼、青鱼和鲤鱼的生长率,这里为p1=0.1,p2=0.13,p3=0.08。

    (3)输入矩阵仍定为常阵

    18.jpg (8.26 KB, 下载次数: 11)

    下载附件

    2015-6-11 16:40 上传



    (4)输出矩阵或预测矩阵C为3×3维单位阵,这样输出向量或量测向量就等同于状态向量,状态空间模型:

    19.jpg (7.91 KB, 下载次数: 13)

    下载附件

    2015-6-11 16:42 上传


    即:

    20.jpg (33.42 KB, 下载次数: 12)

    下载附件

    2015-6-11 16:42 上传



    21.jpg (4.77 KB, 下载次数: 14)

    下载附件

    2015-6-11 16:42 上传



    22.jpg (13.19 KB, 下载次数: 11)

    下载附件

    2015-6-11 16:42 上传





    Kalman滤波简介

    Kalman滤波是一种线性滤波与预测方法,原文为:A New Approach to Linear Filtering and Prediction Problems。文章推导很复杂,看了一半就看不下去了,既然不能透彻理解其原理,但总可以通过实验来理解其具体的使用方法。


    Kalman滤波分为2个步骤,预测(predict)和校正(correct)。预测是基于上一时刻状态估计当前时刻状态,而校正则是综合当前时刻的估计状态与观测状态,估计出最优的状态。预测与校正的过程如下:


    预测:

    1.png (6.58 KB, 下载次数: 12)

    下载附件

    2015-6-11 13:48 上传

    校正:

    2.png (11.75 KB, 下载次数: 15)

    下载附件

    2015-6-11 13:48 上传


    公式1是状态预测,公式2是误差矩阵预测,公式3是kalman增益计算,公式4是状态校正,其输出即是最终的kalman滤波结果,公式5是误差矩阵更新。各变量说明如下表:


    4.jpg (120.25 KB, 下载次数: 12)

    下载附件

    2015-6-11 13:48 上传


    算法实现与分析

    Kalman滤波最复杂的计算应该就是公式3中的矩阵求逆,考虑到实现的方便性,采用matlab来简单实现,本文主要是分析kalman滤波中各个变量的作用和对滤波结果的影响。具体代码如下:


    [C] 纯文本查看 复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    function filter = Kalman(filter)
      %predict
      predict_x = filter.A * filter.x + filter.B * filter.u;
      filter.P = filter.A * filter.P * filter.A' + filter.Q;
      %correct
      filter.K = filter.P * filter.H' / (filter.H * filter.P * filter.H' + filter.R);
      filter.x = predict_x + filter.K * (filter.z - filter.H * predict_x);
      filter.P = filter.P - filter.K * filter.H * filter.P;
    end


    在matlab中,kalman滤波实际上就是上面那5个公式,而难点却是在测试代码中针对不同问题各个变量的初始化上,下面来逐个分析。


    1.建立模型,明确观测量,系统状态以及其转移方程(下面这段公式太多,通过word写好后截图)


    3.png (121.08 KB, 下载次数: 13)

    下载附件

    2015-6-11 13:48 上传


    2.初始化噪声协方差矩阵

    经过上面一步,只有PQRK四个矩阵还未确定了。显然增益矩阵K是不需要初始化的,P是误差矩阵,初始化可以是一个随机的矩阵或者0,只要经过几次的处理基本上就能调整到正常的水平,因此也就只会影响前面几次的滤波结果。


    Q和R分别是预测和观测状态协方差矩阵,一般可以简单认为系统状态各维之间(即上面的a和b)相互独立,那么Q和R就可以设置为对角阵。而这两个对角线元素的大小将直接影响着滤波结果,若Q的元素远大于R的元素,则预测噪声大,从而更相信观测值,这样可能使得kalman滤波结果与观测值基本一致;反之,则更相信预测,kalman滤波结果会表现得比较规整和平滑;若二者接近,则滤波结果介于前面两者之间,根据实验效果看也缺乏实际使用价值。


    以上几个矩阵确定后,对于状态x,由于0时刻我们没有任何关于该系统的知识,可以使用0时刻的测量值z0来初始x0,预测从k=1开始;也可以初始化-1时刻的状态,当然这个状态实际是未知的,也就可随机取。2种方式都可以,但使用0时刻测量值来初始化状态,可以使得前面几次预测更准确。


    3.实验分析


    首先使用下面代码生成一组数据存在z.mat中:

    [C] 纯文本查看 复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    interval = pi/18;
    t = 1:interval:100*pi;
    len = size(t, 2);
    a = t + 4 * (rand(1,len)-0.5);
    b = t .* sin(t/10) +  10 * (rand(1,len)-0.5);
    z = [a; b];
    save('z.mat','z');
    plot(z(1,:),z(2,:),'o')


    可以看出其近似为一条振幅不断增大的正弦曲线叠加一个随机噪声。绘制出来如下:

    4.png (23.9 KB, 下载次数: 10)

    下载附件

    2015-6-11 13:48 上传


    如果使用上面推导的恒定状态系统模型,代码与实验结果如下:

    [C] 纯文本查看 复制代码
    01
    02
    03
    04
    05
    06
    07
    08
    09
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    clear
    close all
    clc
    dim_observe = 2;          %观测值维数
    n = dim_observe;  %状态维数,观测状态每个维度都有1个速度,故需乘2
    filter.A = eye(n);%[1,0,1,0;0,1,0,1;0,0,1,0;0,0,0,1];
    filter.B = 0;
    filter.u = 0;
    filter.P = eye(n);
    filter.K = zeros(n);
    filter.H = eye(n);%[1,0,0,0;0,1,0,0];
    cQ = 1e-8;
    cR = 1e-2;
    filter.Q = eye(n) * cQ;        %这里简单设置Q和R对角线元素都相等,设为不等亦可
    filter.R = eye(dim_observe) * cR;
    filter.x = zeros(n,1); %初始状态x0
    load('z.mat');
    figure(1),subplot(2,2,1),
    t = 1;
    out = [];
    for i=1:size(z,2)
      filter.z = z(:,i);
      filter = Kalman(filter);
      plot(filter.x(1),filter.x(2),  'r*');hold on       
      plot(filter.z(1),filter.z(2),  'bo');        hold on
      out=[out filter.x];
    %         pause(.5)
    end
    figure(1),
    str = sprintf('cQ = %e, cR = %e', cQ, cR);
    title(str)
    %画局部放大
    subplot(2,2,2),
    plot(out(1,:),out(2,:),  'r*');hold on       
    plot(z(1,:),z(2,:),  'bo');        hold on
    axis([120 170 80 200])


    5.png (32.82 KB, 下载次数: 13)

    下载附件

    2015-6-11 13:48 上传


    可以看出滤波结果完全滞后于测量数据,其根本原因在于建立的模型存在问题。


    如果采用上面推导的物体运动模型则只需要修改部分代码,主要是矩阵A和H,以及其他矩阵对应的维数,具体如下:

    [C] 纯文本查看 复制代码
    1
    2
    3
    4
    5
    6
    7
    8
    dim_observe = 2;      %观测值维数
    n = 2 * dim_observe;  %状态维数,观测状态每个维度都有1个速度,故需乘2
    filter.A = [1,0,1,0;0,1,0,1;0,0,1,0;0,0,0,1];
    filter.B = 0;
    filter.u = 0;
    filter.P = eye(n);
    filter.K = zeros(n);
    filter.H = [1,0,0,0;0,1,0,0];


    运行结果如下图,蓝色为观测数据,红色为kalman滤波数据,右侧为局部放大图。可以看出经过滤波后的数据相当平滑,这里Q和R中元素的量级分别为cQ和cR,下图结果可以看到cR比cQ多了6个数量级。

    6.png (39.06 KB, 下载次数: 14)

    下载附件

    2015-6-11 13:48 上传

    (1)


    增加几组结果用于对比分析,对于的cQ和cR见图的标题。

    7.png (39.18 KB, 下载次数: 14)

    下载附件

    2015-6-11 13:48 上传

    (2)


    8.png (40.65 KB, 下载次数: 13)

    下载附件

    2015-6-11 13:48 上传

    (3)


    9.png (41.63 KB, 下载次数: 14)

    下载附件

    2015-6-11 13:48 上传

    (4)


    10.png (41.2 KB, 下载次数: 13)

    下载附件

    2015-6-11 13:48 上传

    (5)


    11.png (41.14 KB, 下载次数: 11)

    下载附件

    2015-6-11 13:48 上传

    (6)


    首先看图1和2,cR与cQ大小均相差了3个数量级,而二者的比值相同,则kalman滤波结果相同。


    再看图2~图6,cR/cQ在不断减小,kalman滤波结果的平滑性也在不断降低,到图5和6中,滤波结果完全和观测值相同,说明此时kalman滤波已经完全相信观测值了。原因在于cR/cQ过小,系统认为预测噪声的方差很大,不值得信赖,而观测值的噪声方差小,可信度高。


    总结

    根据上面的实验结果,可以看出Kalman滤波应用中的几个问题:


    1.模型建立的正确性从根本上决定了滤波效果的正确性。


    上面使用物体静止模型进行滤波,结果完全不对,而使用匀速运动模型则能达到较好的效果。从根本上讲,上面的数据也不是匀速运动的,为何结果会基本正确?看看第一个使用静止模型的滤波结果,虽然我们假定了物体是静止的,但由于观测数据的作用,kalman滤波结果也会有相应的运动而不是完全静止,也就是说滤波器在不停地修正这个状态,而在匀速运动模型中,物体的速度我们认为不变,但同样地kalman滤波器也会不停地修正这个速度,滤波器中计算的速度实质的偏离了真实速度的,因此最终也会有相应的偏差,不过这个偏差在我们容许范围内,也就可以大胆使用了。


    如果能确定物体是匀变速直线运动,使用相应带加速度的模型会得到更准确的效果。但是越严格的模型其适用范围也相应越小。


    2.影响滤波结果平滑性的因素是cR/cQ,这个值反映了我们对于预测和观测值的信任程度;其值越大则越相信预测结果,滤波结果平滑性好;反之则越相信观测结果,滤波结果越偏向于观测值。一般我们使用kalman滤波器是为了能平滑数据的波动,因此应尽量保证cR/cQ稍大,上面的测试结果该值在1e4以上数据较为平滑。



    
    展开全文
  • 状态空间搜索

    千次阅读 2017-08-11 10:49:09
    它通过在状态空间中的初始状态出发,按照一定的顺序和条件对空间中的状态进行遍历,最终找到目标状态。一般的状态空间搜索方法有枚举、深度/广度优先搜索、启发式搜索等等,由于枚举法相对比较易懂,这里不再加以...

    http://www.lencomputer.com/xk2008/lesson19/search_algorithm.htm

    状态空间搜索是程序设计中的最基本方法之一。它通过在状态空间中的初始状态出发,按照一定的顺序和条件对空间中的状态进行遍历,最终找到目标状态。一般的状态空间搜索方法有枚举、深度/广度优先搜索、启发式搜索等等,由于枚举法相对比较易懂,这里不再加以介绍;同时介于篇幅的限制,我们在这一讲也不打算单独启发式搜索。于是,本讲的主要内容就是介绍深度/广度优先搜索以及一些常见的优化技巧。

    大多数程序员最先学习的搜索方法恐怕就是深度优先搜索(DFS)了,它那直接的思考方式很容易被人们所理解并接受。基于堆栈技术的回溯法就是DFS的一个很成功的应用,而我们所熟悉的“八皇后问题”便是回溯法中最为经典的问题。来看一看DFS是如何在状态空间中搜索的吧:
    这里写图片描述

    在图1-1的状态空间图中,如果我们选择每次先扩展最左边的结点,再扩展右边的结点,那么我们的搜索顺序就是1-> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 12 -> 13 -> 7 -> 14 -> 15。

    DFS回溯法的递归实现框架大致如下:

    void Dfs(int a)
    {
        //设置出口
        for(循环枚举可能值)
        {
            //修改一些参量值。
            Dfs(a + 1);
          //恢复之前修改的参量值。
        }
    }

    1. 普通深度优先搜索

    与广度优先搜索(BFS)相比,DFS的一个最大好处就是它所需要的空间开销非常小,因为它只需要记录当前的状态即可。于是,在处理需要遍历大量结点的问题时,DFS就体现出了它在空间复杂度方面的优势。当然,在另一些问题,比如处理形如“目标结点较浅”类型的问题时,相对DFS来说,BFS的时间优势就会相当明显。

    来看一个DFS的例子吧:

    [例 1-1, POJ 1167] 公交车问题

    一男子于12:00来到一个公交车站,他记录下了12:00-12:59所有公交车的到站情况。现在我们假设:
    1) 同一条线路的公交车到站是有规律的,也就是每隔一个固定时间就会有一辆车到站。
    2) 公交车的到站是以分钟为最小计量单位的。
    3) 每一条线路的车至少到站两次。
    4) 经过该车站的公交车线路≤17条。
    5) 不同线路的公交车可以同时到达该车站。
    6) 不同线路的公交车到该车站的时刻和时间间隔均可以相同。

    现在问,根据该男子的记录,最少有多少条公交车线路经过该车站?

    [分析]

    此题是明显的搜索题,且DFS较为合适。由于每条线路只需要第一和第二辆车到达的时刻,就可以完全确定,因此我们可以依次考虑12:00-12:59的车辆到达情况。假设某一个时刻有一辆车到达本站,那么它有两种可能:

    1) 它是一条新线路的第一辆车;2) 它是已有某条线路的第二辆车。

    如果是情况1),那么我们需将它作一下标记。如果是情况2),那么我们就枚举该线路的第一辆车在何时刻到达,有了此时刻,那么就可以完全确定这条线路,随后我们可以把这一条线路从记录中删除。再根据题干中提到的那么约束条件,我们就可以写出程序了。

    2. 迭代加深搜索(Iterative Deepening Search)

    尽管DFS对空间复杂度的要求很低,但它也有着不少问题。其中很突出的一点就是,DFS在处理一些“目标结点较浅”的问题时,往往效率不够高。比如图1-1中,如果目标状态为3结点,那么它将在第9步才找到。假如这棵状态树更深一些,或者它是无限长的,那么DFS就很有可能在有限时间内找不到解。而事实上我们看到,目标状态3其实离初始状态1非常接近。

    因此这种情况下,我们需要对DFS进行一定的改进。最直接的想法就是,为它设定一个深度限制d,使得我们只在深度d范围内搜索。这样如果目标结点在该范围内,那么就很轻易的找到了解。而只要我们让d从1开始逐渐递增,那么就可以在有限步内找到目标结点。这就是迭代加深搜索思想(IDS)(图1-2)。

    这里写图片描述

    在IDS方法中,很多结点都被重复搜索了多次。这对它的效率有一定的影响。分析一下,假设每个结点的子结点个数为b,那么可以看到,每加深一层(由第i层增加到第i+1层),新扩展出的结点数为bi+1,而之前的结点数为1+b+b2+…+bi=bi+1-1,差不多有一半结点被重复了。不过尽管如此,可以看到它的时间复杂度比DFS只是增加了常数倍,从数量级上来看是一样的。

    广度优先搜索(BFS)也是最为常用的搜索方法之一。与DFS相比,BFS最大的不同是它的搜索顺序是按照逐层扩展的,对于图1-1来说,BFS依次扩展出的结点为1->2->3->…->15,因此它所用来存储的数据结构是队列而不是堆栈。BFS的实现框架大致如下:

    void BFS()
    {
       while(队列可扩展且尚未找到目标状态)
        {
           //从队首依次取出队列中未扩展的结点进行扩展,并将新结点加入队尾。
        }
    }

    1. 普通广度优先搜索

    对于求“最短步数”一类的问题,一般BFS会比DFS快一些。原因就在于DFS经常会纠缠于那些找不到目标结点的分支中。来看一看下面这个经典的例子:

    [例2-1, POJ 1077] 八数码问题

    给定一个3*3的格子,里面已经填上了数字1-8以及一个空格,问是否能够通过空格移动数字,使得最终能得到如下图案:

    这里写图片描述

    [分析]

    如果盲目移动数字,那么很容易就会出现重复的情况。因此我们需要判重。那么如何记录一个图案状态呢?如果我们将图上的9个格子中的数(空格看成9)线性地连起来,那么这样一个排列就能唯一地确定一个图。接下来我们只需给出一个排列的序号即可:

    对于一个序列:a1a2…a9,可以依次考虑数字ai(1≤i≤9)后有几个数字小于它,设ai后有bi个数比它小,那么ai贡献的权值为bi*(9-i)!,最后计算 ,就得到了它的序号。这个方法很直接也好理解,就不再解释了。由于9个数的排列有9!种方法,因此我们需要大小为9!的数组来判重。

    接下来就是用什么搜索方法的问题了。可以看到,虽然题目里没有明确说求最短的移动方法,但是相对来说,如果我们能找到最短的移动方法,那么自然算法的速度相对会快一些。所以这里我们可以使用BFS(当然带判重DFS也是可以的)来解题。队列的初始状态就是初始图案上数字的线性排列,比如图2-1(a)中就是973851624,我们需要得到的目标状态是123456789。通过BFS的基本框架,实现算法应该是较为容易的。

    这里给出一个小技巧,如果题目是多Case的,那么可以作预处理,即把初始状态设为123456789,用一遍BFS算出所有可达状态是如何到达的,然后根据给定的输入数据,将原先的移动过程颠倒,就得到我们所需要的答案。这样多个Case只需一遍BFS,而不是多遍BFS就能解决了。

    2. 双向广度优先搜索

    对于一棵搜索状态树,如果每个结点的子结点数目很多,那么状态数每加深一层,就会扩展出指数倍的状态树。因此,我们希望能对状态数目做适当的控制。双向广搜就是这样一种方法,假如我们知道初始状态S和目标状态T,也知道由初始到目标最多需要经过的步数K,那么我们可以这样做:

    先用BFS对S扩展出深度≤[k/2]的所有结点,假如没有找到T,那么再对T用BFS反向扩展出深度≤k-[k/2]的所有结点,这些结点中必然与之前的某些结点有重复,考察这些结点,我们就能够找到一条最短路径。用图表示如下:

    这里写图片描述

    可以看出,双向广搜的最大好处就是可以少扩展出指数倍的无用结点,为搜索节省了大量的空间和时间。

    第三部分 搜索的优化技巧

    1.改变搜索顺序

    搜索顺序的确立对于搜索的效率是很重要的,如果我们每次都选择先扩展更接近目标状态的结点,那么就会更快的找到最优解,并为剪枝提供依据。因此,搜索顺序的改变往能起到意想不到的效果。事实上搜索顺序的不同也是BFS和DFS之间最大的区别之一。这一节我们没有对A*算法做介绍,事实上,A*算法就是一种典型的通过调整搜索顺序来更快找到解的方法。它利用一个评价函数来决定子结点的优先级,然后按优先级从高到低的顺序依次进行遍历。这显然比盲目搜索法要好得多。

    2.增加剪枝策略

    剪枝是搜索中最基本,也是最重要的技巧之一。有时一条好的剪枝可以去掉一棵搜索状态树中大部分的无用结点。剪枝策略的好坏,决定了搜索法的最终效率。有时,一个问题可以采用几种不同的搜索方法,这时,我们就会选择其中具有最好剪枝手段的那个方法。用一个例子来的剪枝技巧吧:

    例3,POJ 1011] 合并木棒

    我们有n(n≤64)根小木棍,每根长度均不大于50。现在需要将它们拼接成长度相同的若干长木棍,使得这些长木棍最短。

    [分析]

    此题也是很明显的搜索题。最直接的思路就是从小到大枚举每个拼成后的木棍长(d),之所以要从小到大,是因为按题意,最小的长度才是我们要找的解,因此,按从小到大的顺序找到的第一个满足题意的长度d就是该问题的解。假设所有木棍总长为t,那么一共就要拼d/t根木棍。随后我们用小木棍将这d/t根木棍一根一根地拼完即可。当然,由于数据量不算小,如果直接做很难在规定时间内出解,故我们需要有一些好的剪枝技巧:

    1) 让我们先对木棍长从大到小排个序,之所以从大到小,是因为直观上,先拼上长木棍,接下来用短木棍补充似乎更容易成功拼完。如果先费了一番功夫拼短木棍,最后发现接上剩下的任何一根长木棍都已超过当前枚举的长度d,那么就浪费了之前的搜索。

    2)枚举的长度d也有要求,首先d应该不小于最长的小木棍长度,不大于木棍总长t。其次d必须是t的约数。这个剪枝很容易想到,也对减小搜索量非常有帮助。

    接下来就可以进行搜索了,可以用一个函数
    bool solve(int rest, int start, int step)进行DFS,其中rest表示正在拼的当前木棍还需要多少长度,start表示当前可以从第几根开始拼,Step表示当前还剩下多少根小木棍。
    搜索中同样可以找到好些剪枝策略。

    3) 我们从start到n枚举小木棍编号i,如果此时rest=len(i),那么显然把这根木棍拼上是最好的选择了,也不需要枚举i+1…n号木棍了。

    4) 如果len(i)…len(j)都具有相同的长度,那么试探完i后应该跳过这些相同长度的小木棍,直接枚举第(j+1)号小木棍。

    5) 如果当前挑选的小木棍是目前正在拼的木棍的首根木棍,即rest == d, 那么试完i后我们没有必要再去试i+1,而是直接跳回递归上一层。因为对于一个合理的分配,小木棍i一定属于某一根待拼木棍,而当前木棍还没有开始拼,既然是这样,那么就可以认为它属于当前木棍。如果拼上它后,没有能够形成满足条件的解。那么也就没有必要继续尝试了,因为在上一层的木棍分配上肯定已经出现了错误。

    可以看出,以上说的这些剪枝条件很多都不能直接能想到,需要仔细分析搜索过程后才能得出。剪枝策略是多种多样的,不同的问题对应有的不同策略。同时,由于每次都需要一些适当的判断,剪枝也会相应地付出一些代价。有些剪枝的“成本”甚至超过了它所带来的益处,这显然是不可取的。那些能够补偿策略本身所花费代价的剪枝,才能称得上是好的剪枝。

    展开全文
  • 连续状态空间表达式 转换为:离散的状态空间表达式 计算数学模型一般是连续的,但是编程去控制这个系统时,只能周期性地去控制它(控制周期为△t),这样预测系统下一周期的状态,最好用离散表达式。 假设某连续...

    连续状态空间表达式 转换为:离散的状态空间表达式

    计算数学模型一般是连续的,但是编程去控制这个系统时,只能周期性地去控制它(控制周期为△t),这样预测系统下一周期的状态,最好用离散表达式。

    假设某连续系统的状态表达式为:

    把上式改为离散形式,可得:

    把上式整理为离散表达式的标准形式:

     

    展开全文
  • 状态空间表示

    2020-11-01 11:36:53
    搜索(Search),设法在庞大状态空间图中找到目标。   主要分为两类性质的搜索:   基本搜索,是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索;启发式搜索(Heuristic Search)...
  • 搜索(Search),设法在庞大状态空间图中找到目标。 主要分为两类性质的搜索: 基本搜索,是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索; 启发式搜索(Heuristic Search):其特点...
  • 理解状态空间

    千次阅读 2014-10-08 11:46:49
    个人理解(刚开始研究,仅供参考): 1.现实世界,每个事物都有很多状态,通常理解的空间都是以xyz为坐标轴,这种空间是“以距离为...2.通常理解的空间,都是有厨师状态,有原点(0,0,0)的,而状态空间没有初始条件,
  • 什么是状态空间

    千次阅读 2020-06-08 22:33:55
    1 状态空间法 在经典控制理论中,在建立数学模型时是通过传递函数进行的,在这个过程中,只考虑输入和输出之间的关系,所以会将系统变成一个黑盒子,里面的内容被浓缩了。 而在现代控制理论中,会首先从系统中抽取...
  • 状态空间方程的等价问题 判断两组状态空间方程是否等价 等价的两组状态空间方程具有以下四个特征: 相同的特征多项式 相同的一组特征值 相同的传递矩阵 相同的维数 注:以上四个特征只能用于判断不等价,不能...
  • 我们知道在多变量系统解耦的过程中需要将状态空间中的状态变量反馈回去从而达到解耦的目的。但是Simulink中的状态空间模块是没有这个功能的,因此我们可以采用搭建相同参数系统,然后让输出方程输出状态向量即可。 ...
  • 状态空间描述的概念

    千次阅读 2019-02-23 13:51:22
    状态空间:以状态变量为坐标轴组成的n维正交空间 状态方程:在状态空间中建立的描述系统性能的数学模型 列写状态方程就是把一个高阶微分方程化为所确定的状态变量相应的一阶微分方程组,然后用向量矩阵形式表示。 ...
  • 状态和状态空间

    2019-10-14 11:18:37
    状态: 动态系统的状态粗略地说就是指系统的过去、现在和将来的运动状况。 精确的说,状态需要一组数据来说明。 如图1所示小车的运动,这个系统的状态就是车子每一时刻的位置和速度。 状态变量: 系统的状态变量...
  • 系统的状态和状态空间 系统的外部描述 :外部描述常被称作为输出—输入描述 系统的内部描述 :状态空间描述是系统内部描述的基本形式,需要由两个数学方程表征—— 状态方程和输出方程 外部描述和内部描述的...
  • 一、状态: 动态系统的状态粗略地说就是指系统的过去、现在和将来的运动状况。精确地说,状态需要一组必要而充分的数据说明。 对于运动的小车,系统的状态可以为位置和速度,对于电机可以为转速。 二、系统变量 ...
  • 今天老师留了一道关于状态空间变量响应的题,于是想用simulink仿真,一开始使用state-space模块,但是发现它只能输出y,没办法显示状态变量的变化情况。然而状态变量之间的关系都可以表示为一阶微分方程组,因此我们...
  • 传递函数与状态空间

    千次阅读 2019-09-21 23:31:37
       传递函数与状态空间之间可相互转换,可以使用的matlab函数有 [A,B,C,D] = tf2ss(NUM,DEN) [NUM,DEN] = ss2tf(A,B,C,D,iu)    传递函数的形式唯一,但状态空间的形式不唯一,可以有多种。 1、一阶惯性...
  • 状态空间模型中实际参数估计

    千次阅读 2020-05-27 19:23:05
    状态空间模型中实际参数估计状态扩增法线性状态空间模型的参数估计利用高斯滤波与平滑的参数估计(非线性模型)基于粒子滤波与平滑的参数估计参数的 Rao-Blackwell 化 (参数估计所有内容) 状态扩增法 线性状态空间...
  • 状态空间方程MATLAB语句

    千次阅读 2020-11-12 16:29:56
    1.连续系统 ...(3)将给定形式的状态空间方程变换成模态标准型 sysG=ss(A,B,C,D); [sysGm,TI]=canon(sysG,'modal'); [Am,Bm,Cm,Dm]=ssdata(sysGm);//系统极点为Am对角线上的元素,部分分式展开式的
  • simulink 状态空间加反馈报错

    千次阅读 2020-04-18 17:57:10
    状态空间模型(可控)通过状态反馈或输出反馈可以自由配置极点和特征向量,得到理想的运动状态,通过计算得到的反馈增益矩阵K便可构建simulink模型,但常常报错,原因如下: 上图展示的是simulink模型,是通过...
  • MATLAB:对于状态空间方程的系统辨识 本文介绍了如何利用MATLAB辨识状态空间方程中的未知参数。 假设我们的被控系统的表达如下: X˙=[01K1K2]X+BU \dot{{X}}= \left[\begin{matrix} 0 & 1\\ K_1 & K_2 \end...
  • 传递函数化为状态空间表达式

    千次阅读 2020-08-30 22:31:44
    G(s)=N(s)D(s)G(s)=\frac{N(s)}{D(s)}G(s)=D(s)N(s)​ 的串联分解形式 可控标准型 可观测标准型      实例 G(s)=N(s)D(s)G(s)=\frac{N(s)}{D(s)}G(s)=D(s)N(s)...状态空间表达式 其中:    ...
  • 人工智能--状态空间问题求解方法

    千次阅读 2019-06-08 00:21:33
    文章目录状态空间问题表示状态操作状态空间状态空间问题的求解例子二阶梵塔问题MC问题(修道士与野人问题) 状态空间法是人工智能中最基本的问题求解方法,它所采用的问题表示方法称为状态空间表示法。 状态空间法的...
  • 状态空间模型的等价性

    千次阅读 2020-05-19 08:46:40
    考虑状态转移方程和观测方程均为非线性的状态空间模型: xt=f(xt−1)+vtyt=g(xt)+et x_t = f(x_{t-1}) + v_t \\ y_t = g(x_t) + e_t xt​=f(xt−1​)+vt​yt​=g(xt​)+et​ 其等价于只有状态转移方程为非线性的形式...
  • 状态空间方程的建立 基本概念: 状态:动力学系统的状态定义为信息的集合 状态变量:确定动力学系统状态的最小一组变量 状态向量:由n个状态变量组成的向量 状态空间:以状态变量位坐标构成的空间 状态方程:描述...
  • 状态空间模型是概率图生成模型,它假设序列观察数据背后由隐状态支撑,或者说隐状态生成了观察。隐状态符合一阶马尔科夫链假设,也就是说,除了前一时刻隐状态外,当前时刻隐状态独立于过去其它所有时刻的隐状态。如...
  • 连续状态空间离散化的matlab实现

    万次阅读 2019-03-18 15:57:59
    假设一个连续状态空间等式为:(x)=Ax+Bu 忽略输出方程,因为离散后的输出方程与连续时一样 在matlab中,[G,H]=c2d(A,B,Ts),Ts是采样周期 得到离散化状态空间等式:x(k+1)=Gx(k) + Hu(k) ...
  • 介绍了从传递函数求状态空间模型的基本方法、线性叠加法、串联法、并联法,从状态空间模型求传递函数的方法,传递函数和状态空间模型的对偶性。
  • 状态空间表达的必要性 经典控制理论将控制系统当作一个黑匣子,而现代控制理论引入反映系统内部状态变化的状态变量构建系统输入和输出的关系 2.1. 状态空间表示法的定义 这里的ici_cic​是不必要的,因为可以由...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 31,933
精华内容 12,773
关键字:

状态空间