论文部分内容阅读
自然界中到处都存在着对称性,对于具有对称性的信息,在存储时可根据它的特征进行压缩存储。比如,如果平面图形在二维坐标系中是对称的,则可以只存储一半(不考虑对角线)的信息就可以表示出这个图形,即可以存储为一个上(或下)三角矩阵。类似的如果三维坐标系是对称的,就可以只存储1/6(不考虑对角线)的信息,至于怎么存储却并不像二维对称那样简单。在现实世界中,我们能够观察到的也就是三维,加上时间也才四维,但是在很多领域,经常需要处理三维及三维以上的信息,有时候这些多维信息,在维与维之间存在着对称性。如果能够像上(下)三角矩阵剥离二维对称一样去剥离多维信息中的对称性,将可以极大地减少信息量,进而降低存储空间和处理时间。本文针对上述问题,如果“多维空间”各维间具有对称性,则其冗余程度是非常大的,较为系统的介绍了消除其冗余性的方法,即称为“多维对称空间压缩存储”的方法,并且设计了“遍历多维对称空间正对角面”的几种高效的方法。首先,比较详细的分析了“多维空间”的对称性,通过坐标映射的方式设计了多维对称空间的压缩存储方法;然后分别设计了针对规整对称空间正对角面,规整对称空间,非对称空间,非规整对称空间的压缩存储方法;最后,还设计了“规整对称空间正对角面遍历”的方法。此外,本文还将所设计的“多维对称空间的压缩存储方法”应用在小规模的多目标0-1背包问题中,并经过实验验证了它的正确性与有效性。实验结果表明,所设计的压缩存储方法是很有效的。所设计的“多维对称空间的压缩存储方法”是一个非常有用的算法工具,可以极大的减少某些特定问题的内存需要,进而大大减少时间耗费。