| 摘要: |
| 算法的效率在很大程度上依赖于实际采用的数据结构.对无用数据的处理不仅会带来空间存储上的浪费,而且也会进一步造成时间上的浪费.因此,消除信息冗余一直是算法研究的一个重点.在当前实时领域(尤其是在基于稠密/连续时间语义)的算法研究中,该问题十分突出.从信息之间的依赖关系入手,分析了在对连续时间进行有穷表示和操作中存在的问题,通过改进"范式化"处理过程,给出了进行冗余信息消除的一种方法以及其正确性证明,并通过实验测试了改进的效率. |
| 关键词: 实时 时间自动机 数据结构 冗余信息消除 最短路径算法 优化 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.69833020, 60203028 (国家自然科学基金) |
|
| Dense Time Representation and Redundancy Elimination |
|
CHEN Jing
|
| Abstract: |
| The efficiency of an algorithm depends greatly on the data structure adopted in practice, while the processing of useless data can cause not only much waste of memory but also much waste of time. Hence to eliminate redundant information is one of the main focuses in the research of algorithms, and the issue has received extensive attention in real-time field (especially those based on dense/continuous time semantics) for many years. After investigating existing problems in finite representation and operations, and by analyzing the dependence relation in information, a method is presented for eliminating redundant information in representation of dense time, which is developed based on an modification of the procedure of ‘Normalization’. The correctness of the method is proved and the efficiency is tested by experiences. |
| Key words: real-time timed automata data structure redundancy elimination shortest path finding algorithm optimization |
