学位论文 > 优秀研究生学位论文题录展示

分析多时序Petri网的自动机模型

作　者: 孙宇新
导　师: 谢里阳
学　校: 东北大学
专　业: 机械设计及理论
关键词: 多时序Petri网自动机模型数据结构与算法图论与离散算法
分类号: TP301.1
类　型: 硕士论文
年　份: 2008年
下　载: 26次
引　用: 0次
阅　读: 论文下载

内容摘要

Petri网以研究系统模型的组织结构和动态行为为目标,着眼于系统中可能发生的各种状态变化以及变化之间的关系。Petri网可以用简单的图形元素表示系统变化发生的条件,以及变化发生后的系统状态。随着分析问题的深入和系统复杂度的提高,大量的因素引入Petri网系统中。网系统增加的因素包括条件、时间等等。其中时间因素对网系统的影响很大,在时间因素的作用下网系统的运行方式,基础特性以及运行情况也发生了变化。因而,求解多时序Petri网的各种特性变得较为困难。同时,原有求解Petri网系统的方法都是通过网系统的转置矩阵。根据不同的特性,建立与转制矩阵相关的表达式与矩阵方程。通过对方程和表达式的求解来得到相应问题域的答案。但这样的求解方式是建立在矩阵计算基础之上的。我们都知道矩阵的计算需要进行大量的乘法,同时矩阵中存在大量的元素其数值为零。这样的矩阵运算中存在很多不必要的乘零运算。特别是随着问题规模的扩大,必然带来矩阵维数的增加,这些乘零运算就更加降低系统的效率。这样利用矩阵方程来求解Petri网的方式的效率将越来越低,计算机实现的效率也大幅度的降低。回避矩阵计算是提高计算分析性能的有效方法。我们可以从网系统的结构出发,利用图论与离散算法的特性构建分析网系统的算法逻辑。把矩阵计算转变为围绕特定数据结构与逻辑算法的工作过程,并用相应的形式语言定义这些结构与逻辑,建立分析多时序Petri网的自动机模型。利用针对不同问题的Petri网的系统,对实际的问题加以求解。

全文目录

摘要  5-6
Abstract  6-10
第1章引言  10-12
  1.1 研究背景  10-11
  1.2 研究现状  11-12
第2章 Petri网与自动机  12-19
  2.1 Petri网简述  12-15
    2.1.1 Petri网的形式描述  12-14
    2.1.2 Petri网系统的扩展  14-15
  2.2 形式语言与自动机的简介  15-17
    2.2.1 形式语言与自动机  16
    2.2.2 文法与自动机的对应  16-17
  2.3 图与树  17-19
    2.3.1 图的定义  17-18
    2.3.2 树的定义  18-19
第3章可达集与不变量  19-35
  3.1 Petri网的可达集  19-28
    3.1.1 变迁的实施条件  19-20
    3.1.2 可达树和可达图的构造  20
    3.1.3 构建分析可达集的自动机  20-28
  3.2 Petri网的不变量  28-35
    3.2.1 不变量的定义  28-29
    3.2.2 求解不变量的自动机模型  29-35
第4章竞争策略的自动机模型  35-45
  4.1 竞争策略的综述  35-36
  4.2 竞争策略的具体实现  36-39
    4.2.1 基于优先级策略的实现  36-38
    4.2.2 基于变迁实施时间策略的实现  38-39
  4.3 多策略相互作用下的自动机模拟  39-45
    4.3.1 变迁执行环境中的若干条件  39-40
    4.3.2 局部环境中变迁状态的划分与运行逻辑  40-42
    4.3.3 多策略作用的自动机模型与形式化定义  42-45
第5章分析SPN网的自动机模型  45-64
  5.1 SPN网简介  45-47
    5.1.1 SPN网的性质  45-46
    5.1.2 SPN网的定义  46
    5.1.3 SPN网的同构性  46-47
  5.2 SPN网的有界性  47-51
  5.3 解决随机转换系统的同构问题  51-58
    5.3.1 随机转换系统的同构  51-52
    5.3.2 分析随机转换系统同构的自动机  52-58
  5.4 状态转移最短路径问题  58-64
    5.4.1 求解最短路径算法  58-59
    5.4.2 求解最短路径的自动机模型  59-64
第6章网系统的分解与压缩  64-70
  6.1 网系统的分解与压缩  64-66
    6.1.1 接近无关的分解  64-65
    6.1.2 时间数量级的分解  65-66
  6.2 时间数量级分解的自动机  66-70
    6.2.1 时间数量级分解的算法逻辑  66-67
    6.2.2 自动机的运行逻辑  67-70
第7章自动机模型的应用  70-76
  7.1 柔性制造系统中的应用  70-73
    7.1.1 柔性制造系统的设计  71-72
    7.1.2 不变量的分析  72-73
  7.2 网络传输中的应用  73-76
    7.2.1 分析网络路由的延时问题  73-74
    7.2.2 求解最短路径问题  74-76
第8章结论与展望  76-78
  8.1 结论  76-77
  8.2 展望  77-78
参考文献  78-82
致谢  82

分析多时序Petri网的自动机模型

内容摘要

全文目录

相似论文