15-谜问题(15-puzzle)的可达性判定

定义了15-谜问题的6个动作规则，在此基础上证明了15-谜问题解的存在性判定的充分必要条件，其充分性的证明过程是一个构造性证明方法，提供了求解15-谜问题的一个解的可实现算法；同时，对此结论进行了扩展，对于给定的一初始格局和任一目标格局，证明了初始格局可达目标格局的的充分必要条件，其结论有助于构造问题的状态空间与限界函数。这两个结论从理论上完全解决了15-谜问题，对获得最优算法提供了理论基础。
关 键 词 15-谜问题; 格局; 可达性; 算法

Abstract Based on multiple-input-multiple-output (MIMO) scattering wireless fading channel model, a dynamic receiving and transmitting model for MIMO wireless channels is proposed in this paper, which is used for analyzing impact of mobility of transceiver antennas on spatial correlation and capacity of MIMO wireless channels. The conclusion is reached, which these effects are determined by the original positions of transceiver antennas and by their velocity. The simulation results validate this impact and show that there exists an optimum angular spread that forces spatial correlation, which decreases with increasing antenna spacing and does not consistently decrease with increasing angular spread, to reach minimum.
Key words 15-puzzle; pattern; reachability; algorithm